# 11/15 競プロ講習会バチャ ヒント/解説

## ヒント集

---
### 1 Anyway Takahashi

:::spoiler **クリックで展開**
競技プログラミング講習会へようこそ！
プログラミング言語を用いた入出力で困っている場合、下の解説のサンプルコードを参考にするか、講師に質問してください。
:::

---
### 2 "atcoder".substr()

:::spoiler **クリックで展開**
for文を用いて文字列を順番に見ていきます。鹿本p.65などを参考にしてください。
何番目の文字を見ているか?を整数の変数として持っておくのがポイントです。
:::

---
### 3 Qual B

:::spoiler **クリックで展開**
for文を用いて文字列を順番に見ていきます。鹿本p.65などを参考にしてください。
すでに何人採用しているかを表す整数の変数をカウンターとして用いるのがポイントです。
:::

---
### 4 Modulo Number

:::spoiler **クリックで展開**
「整数のあまり」を用います。鹿本p.52を参考にしてください。
998244353は大きすぎるので、12の倍数で考えてみましょう。
N=15としたとき、(N-x)が12の倍数であるなら、xはいくつでしょうか?
時計との関連も考えると面白いです。
:::

---
### 5 Submask

:::spoiler **クリックで展開**
再帰的に計算します。鹿本p.246を参考にしてください。
まず、for文を64重にして使った解法を考えてみると再帰の理解に役立つかもしれません。
(もっともそれだと計算時間が間に合わないのですが)
:::

---
### 6 Buy an Integer

初見だと感動するテクニック。

:::spoiler **ヒント1**
$X$ 円で整数 $N$ を買えますか？（Yes or No）という判定問題であれば、すぐに解くことができます。
:::

:::spoiler **ヒント2**
整数 $N$ が買えるなら、整数 $N-1$ も買うことができます。また、整数 $N$ が買えなければ、整数 $N+1$ も買えません。これは値段が単調増加であることからわかります。
また所持金は有限なので、どこかに「$N$ は買えるが $N+1$ は買えない」という"境界"が存在するはずです。
:::

:::spoiler **ヒント3**
購入する整数について二分探索をします。
:::

---
### 7 GCD on Blackborad

難しい問題の部分問題としても出てくる典型です。

:::spoiler **ヒント1**
「$A_i$ を変更する」と決めたときに、全体の最大公約数が最大でいくつになるか考えましょう。
:::

:::spoiler **ヒント2**
変更する値を全探索する方針を考えましょう。
:::

:::spoiler **ヒント3**
「全体から 1 つ抜く」は「両側から計算」が定石です。
またはデータ構造に載せても OK。
:::

---
### 8 阿弥陀

:::spoiler **ヒント1**
あみだくじ複数個分をまとめたときの移動先を計算します。
例えば、あみだくじ13個分の移動は、
あみだくじ8個分の移動→あみだくじ4個分の移動→あみだくじ2個分の移動
と表現できます。
どのようにまとめれば効率よく計算できるでしょうか。
:::

:::spoiler **ヒント2**
例えば、
あみだくじ2個分の移動はあみだくじ1個分の移動を2回、
あみだくじ4個分の移動はあみだくじ2個分の移動を2回、
あみだくじ8個分の移動はあみだくじ4個分の移動を2回、で計算できます。
この手法は「ダブリング」とも呼ばれています。
以下のページも参考にしてください。
https://algo-logic.info/doubling/
:::

---
### 9 Removing Robots

方針によって簡単だったり難しかったりする問題です。

:::spoiler **ヒント1**
座標の昇順にロボットの番号をつけ直します。こうすることで、ロボット $i$ を起動したとき、それによって起動されるロボット全体は区間になります。この区間が求まれば、場合の数は DP で計算できます。
:::

:::spoiler **ヒント2**
ロボット $i$ を起動したときに連鎖的に起動されるロボットのうち、番号が最大（=座標が最大）のロボットが求まればよいです。
:::

:::spoiler **ヒント3**
データ構造で高速化します。
:::

:::spoiler **ヒントEx**
別の方角から考察をすすめると、木DPの問題になります。こちらのほうが実装が軽いです。
:::

---
### 10 Swaps

:::spoiler **ヒント1**
「ある2要素をswapする」という操作を繰り返した時、
その操作はもとの数列の並び替えとみなすことができます。
どのような並べ替えなら可能でしょうか?
:::

:::spoiler **ヒント2**
「swapをN-2回まで行える」
という条件が重要です。
実際に、N=3やN=4の場合について、
どのような並べ替えなら可能か実験してみましょう。
:::

---
### 11 1D Reversi Builder

難しいですが、まだ順当に考えると解ける問題です。

:::spoiler **ヒント1**
実際のゲームの経過を手元でいろいろ試して、盤面として有りうるものの集合を考えましょう
:::

:::spoiler **ヒント2**
端の色の組み合わせに注目しましょう。同色の場合は？異なる色の場合は？
特に後者の場合の最適戦略を考えましょう。
:::

:::spoiler **ヒント3**
コーナーケースに注意！！ (〇〇が等しい場合です)
:::

---
### 12 3 Letters

非人間的な難しさかも。1500点に相応しい難易度です。
解説を読み漁った後、じっくり考えてなんとか理解できる位の難易度でした。

:::spoiler **ヒント1**
不変量を考えましょう。
:::

:::spoiler **ヒント2**
端の処理が圧倒的に難しいです。何とか不変量に組み込みましょう。
:::

:::spoiler **ヒント3**

01010 を隣接項swapを繰り返して 10100 にしたい時の操作回数は…

まず累積和
01010 -> 01122
10100 -> 11222

その後、差分の絶対値の総和を取ればいいです

 01122
-11222
=10100 -> 2

:::

## 解説（ネタバレ注意！！）

---
### 1 Anyway Takahashi

:::spoiler **クリックで展開**
競技プログラミングの問題は、
・何らかの入力を受け取り、
・入力された変数を用いて計算し、
・出力をする
という段階に分けることができます。
プログラミング言語における必要な操作やアルゴリズムは、本やネット上の他の人の実装を参考にすることで手っ取り早く身につけられます。
以下に示すサンプルコードも参考にしてください。

サンプルコード(C++)
https://atcoder.jp/contests/abc269/submissions/47592131

サンプルコード(python)
https://atcoder.jp/contests/abc269/submissions/47592349

サンプルコード(python)

a,b,c,d = map(int,input().split())
print ( (a+b)*(c-d) )
print ("Takahashi")

:::

---
### 2 "atcoder".substr()

:::spoiler **クリックで展開**
for文を用いて文字列を順番に見ていきます。鹿本p.65などを参考にしてください。
「何文字目か」を表す変数をfor文を用いて動かすことで、文字列を左から順番に見るという操作が可能です。
与えられたL, Rをもとに、i文字目を見ているときは $L \leq i \leq R$ である場合にその文字を出力すればよいです。
なお、c++のstd::substr(), もしくはpythonのスライスを用いるとより簡潔に記述できます。

サンプルコード(C++)
https://atcoder.jp/contests/abc264/submissions/47592070

サンプルコード(python)
https://atcoder.jp/contests/abc264/submissions/47592618

サンプルコード(python)

L,R = map(int,input().split())
print ("atcoder"[L-1:R])

:::

---
### 3 Qual B

:::spoiler **クリックで展開**
for文を用いて文字列を順番に見ていきます。鹿本p.65などを参考にしてください。
あらかじめすでに採用した人数のカウンターをもっておき、左から順に見ていきます。
決勝への参加を希望している人について、まだK人採用していなければ'o'を出力し、採用した人数のカウンターを1増やします。
決勝への参加を希望していない人や、すでにK人採用したあとの人については'x'を出力すれば良いです。

サンプルコード(C++)
https://atcoder.jp/contests/abc290/submissions/47591953

サンプルコード(python)
https://atcoder.jp/contests/abc290/submissions/47592976

サンプルコード(python)

N,K = map(int,input().split())
S = list(input())

for i in range(N):
  if S[i] == "o":
    if K > 0:
      K -= 1
    else:
      S[i] = "x"
print ("".join(S))

:::

---
### 4 Modulo Number

:::spoiler **クリックで展開**
「整数のあまり」を用います。鹿本p.52を参考にしてください。
N-xが998244353の倍数であることとは、
Nを998244353で割ったあまりがxを998244353で割ったあまりによって打ち消されること、すなわちNとxをそれぞれ998244353で割ったあまりが等しいことと同じです。
特に、xは0以上98244353未満であるため、
「xはNを998244353で割ったあまりである」と言い換えることができます。
C++の場合、あまりを求める演算子の仕様に注意してください。

サンプルコード(C++)
https://atcoder.jp/contests/abc266/submissions/47591846

サンプルコード(python)
https://atcoder.jp/contests/abc266/submissions/47593118

サンプルコード(python)

print (int(input()) % 998244353)

:::

---
### 5 Submask

:::spoiler **クリックで展開**
再起的に計算します。鹿本p.246を参考にしてください。
Nの各bitごとにその位が0であれば0とし、1であれば0である場合と1である場合の両方について探索すればよいです。

こんな凄い方法も有ります
https://ark4rk.hatenablog.com/entry/2018/03/07/230257

サンプルコード(C++)
https://atcoder.jp/contests/abc269/submissions/47591731

サンプルコード(python)
https://atcoder.jp/contests/abc269/submissions/47593454

サンプルコード(python/凄い方法)

S = int(input())

ans = []
T = S

while True:
    ans.append(T)
    if T == 0:
        break
    T = (T-1) & S

ans.reverse()
print (*ans,sep="\n")

:::

---
### 6 Buy an Integer

:::spoiler **クリックで展開**
値段が単調増加であることから、「整数 $N$ を買うことはできるが、整数 $N+1$ は買うことができない」となる整数 $N$ が存在するはずです。この $N$ が求める答えとなります。
二分探索の要領で探します。はじめ $h:= 10^9+1,\ l := 0$ と初期化して、次のようにループを回します。ただし <code>val(mid)</code> は「整数 mid の値段」を表しています。

Python 風擬似コード

h = 10**9 + 1
l = 0
while h-l > 1:
    mid = (h+l) // 2
    if val(mid) <= X:
        l = mid
    else:
        h = mid

この反復は $h = l+1$ となるまで繰り返されます。

そして実は、反復の終了時 $l=N,\ h=N+1$ となっています。なぜならば、反復の開始から終了まで「整数 $l$ は購入することできる」「整数 $h$ は購入することができない」という条件が常に満たされるからです。
よって反復後の $l$ の値を出力すれば答えとなります。

計算量の話をします。この探索では、$h$ と $l$ の差が反復 $1$ 回につき半分になっていることがわかります。すると、この反復はおおよそ $\lceil \log_2 10^9 \rceil = 30$ 回だけ繰り返されることになります。$1$ 回の反復にかかる計算量も（<code>val(mid)</code> の実装にもよりますが）基本的に大きくならないので、この方針で正解することができます。
:::

---
### 7 GCD on Blackboard

:::spoiler **クリックで展開**
$A_i$ を変更すると決めたとき、最大で答えをいくつにできるかが高速に求まればよいです。

全体から $A_i$ のみを抜いたときの最大公約数を $g_i$、つまり $g_i := \mathrm{gcd}(A_1, \ldots, A_{i-1}, A_{i+1},\ldots, A_N)$ とおきます。このとき、$A_i$ を変更したときの答えの最大値が $g_i$ を超えることはありません。逆に、$A_i$ を $g_i$ に変更することで、答えを $g_i$ にすることができます。

上の議論から、すべての $i$ について $g_i$ を求め、その最大値を求めればよいことになります。当然愚直に計算すると TLE となるので、工夫して計算する必要があります。ここでは $2$ つの方法を紹介します。以下、$M := \max_i A_i$ とおきます。

1. 両側から前計算する

配列 $L, R$ をそれぞれ

$$L_i := \mathrm{gcd}(A_1, A_2, \ldots, A_i)$$

$$R_i := \mathrm{gcd}(A_i, A_{i+1}, \ldots, A_N)$$

と定義します。これは $L_i = \mathrm{gcd}(A_i, L_{i-1})$、$R_i = \mathrm{gcd}(A_i, R_{i+1})$ という式を用いて $\mathrm{O}(N + \log M)$ 時間で計算できます。
このとき $g_i = \mathrm{gcd}(L_{i-1}, R_{i+1})$ が成り立ちます。これは $\mathrm{O}(\log M)$ 時間で計算できるので、全体ですべての $g_i$ を $\mathrm{O}(N\log M)$ 時間で計算できます。

2. データ構造を用いる

$g_i := \mathrm{gcd}(A_1, \ldots, A_{i-1}, A_{i+1},\ldots, A_N)$ だったので、$g_i$ は $2$ つの区間 $[1, i-1],\ [i+1, N]$の $\mathrm{gcd}$ がわかれば計算できることになります。
この問題で考えている整数の集合と $\mathrm{gcd}$ という演算の組は「モノイド」の公理を満たします。よって、Segment Tree に載せることができます。（このあたりの議論が難しいと感じる場合、頻出な Segment Tree に載る構造を覚えてしまうのも手です。）
Segment Tree を用いて $g_i$ を計算する場合の計算量は $\mathrm{O}(N\log N + N\log M)$ です。

:::

---
### 8 阿弥陀

:::spoiler **クリックで展開**
ダブリングを用います。
以下のページも参考にしてください。
https://algo-logic.info/doubling/
与えられたあみだくじを $2^k$ 個つなげたものはそのあみだくじを $2^{(k-1)}$ 個つなげたものの2つ分として考えることができます。
したがって、前もってあみだくじを 1, 2, 4, 8, ... 個つなげたものについて、その位置ごとの行き先を計算しておき、
与えられた$D$を二進数における表現をもちいて2の冪乗の和に分解し、対応するあみだくじをつなげれば、あみだくじを$D$個つなげたものの位置ごとの行き先が得られます。
:::

---
### 9 Removing Robots

:::spoiler **クリックで展開**
ロボットの番号を座標の昇順に振り直します。つまり、$X_1\leq X_2\leq \ldots\leq X_N$ とします。

このとき、各 $i$ に対して「ロボット $i$ を起動するとロボット $i+1, i+2, \ldots, R_i$ が起動される」となる $R_i$ が存在します。ただし $i\leq R_i\leq N$ であり、$R_i = i$ の場合、ロボット $i$ が起動したときに接触するロボットが存在しないことを表します。

まず、すべての $i$ に対する $R_i$ の値を求めます。これは、自分が「直に」接触できるロボットのうち、最も遠くのロボットを起動できるものが特定できればよく、$i$ の降順に Segment Tree などを用いることで計算できます。

次に、問題の答えを求める DP を行います。
$\mathrm{dp}_i :=$ 番号 $i$ から番号 $N$ のロボットまでを考えた時の答え、と定義して $i$ の降順に求めましょう。便宜上 $\mathrm{dp}_{N+1} = 1$ とします。

ロボット $i$ を起動しない場合、場合の数は $\mathrm{dp}_{i+1}$ と等しくなります。一方ロボット $i$ を起動する場合、ロボット $i,i+1,\ldots,R_i$ はすべて起動されることになるので、場合の数は $\mathrm{dp}_{R_i+1}$ と等しくなります。

答えは $\mathrm{dp}_1$ です。DP の値は線形時間で計算できるので、ネックは最初のソートと $R_i$ を Segment Tree で求める部分であり、全体の計算量は $\mathrm{O}(N\log N)$ です。

なお $R_i$ の値を陽に求めずとも、接触関係を上手にグラフに落とし込むことでソート以外線形（Segment Tree などがいらない）で解くこともできます。ユーザ解説に書いたので、そちらも参照してください。もしくは解説放送でも同様の方針を解説しています。
:::

---
### 10 Swaps

:::spoiler **クリックで展開**
N-2回までの要素のSwapの作用である置換が表現できるとき、これはその置換が巡回置換でないことと同値です。
<details>
<summary> 巡回置換とは? </summary>
ある要素から、その要素の最終的な行き先にむけて矢印を引いた時、その矢印が全体で大きな一つの輪になるものをいいます。</br>
たとえば、(1,2,3,4)→(2,1,4,3)という置換は(1→2→1)と(3→4→3)という二つの流れ(これはサイクルと呼ばれます。)に分解されるので巡回置換ではありません。</br>
一方、(1,2,3,4)→(3,1,4,2)という置換は(1→3→4→2→1)という一つの大きなサイクルのみを持つため、これは巡回置換です。</br>
厳密な表現は、数学書を参照してください。
</details>

<details>
<summary> 証明 </summary>
・<b>巡回置換が生成できないこと</b></br>
上の「巡回置換とは?」の項にて説明したサイクルの個数を用います。</br>
最初、すなわち恒等置換において、サイクルの個数はN個あります。(要素が一つのサイクルも存在することに注意してください。)</br>
ある置換を作用させたとき、置換された2つの要素が属していないサイクルはまったく変わらないことから、サイクルの個数は減るとしても高々1つのみです。</br>
したがって、N-2回までの操作でサイクルは高々N-2個までしか減らないため、N個から1個までサイクルを減らす必要のある巡回置換は生成できません。</br>
・<b>巡回置換でないならすべて生成できること</b></br>
長さKの巡回置換がちょうどK-1回のswapの作用で表現できることは数学的帰納法より簡単に示すことができます。</br>
いま、巡回置換でないすべての置換はいくつかのより小さい巡回置換の並列として捉えられるため、それぞれのミニ巡回置換の構成を考えれば、もとの置換のサイクルの総数をCとして、N-C回の操作によって生成することができます。特に、巡回置換でない場合、すなわちCが2以上の場合について考えれば、題意が示されます。 証了</br>

</details>

さて、巡回置換でないようなAの置換について、 $A_{i} \leq B_{i}$ を満たすものを考えましょう。
あらかじめBをソートし、 $B_{i} \leq B_{i+1}$ がすべての $i \leq N-1$について成り立っているとしても一般性を失いません。
いま、Aをソートした列について考えます。この列が $A_{i} \leq B_{i}$ を満たさない時、実はどのようなAの並べ替えも満たすことができません。なぜなら、ある $j$ について $B_{j} \lt A_{j}$ が成り立っているとき、
(i) Aがソートされているということから $A_{k} \leq B_{j} \lt A_{j}$ を成り立たせるようなkは高々j-1個しか存在しない
(ii) Bがソートされているということから、$A_{m} \leq B_{m} \leq B_{j}$ が $1 \leq m \leq j$ をみたすj個のmについて成り立つ必要がある
上の2つは矛盾します。

以上より、Aをソートした列が条件を満たさない場合、答えは"No"です。
Aをソートした列が条件を満たす場合、Aのソートが巡回置換とならないなら答えは"Yes"です。
Aをソートした列が条件を満たすが、それが巡回置換となる場合、ある隣接する二項を入れ替えることで無理やり巡回でない置換を作り出します。
ある隣接する二項を入れ替えても条件を満たす場合答えは"Yes"であり、
どの隣接する二項を入れ替えても条件を満たさない場合、答えは"No"です。

:::

---
### 11 1D Reversi Builder

:::spoiler **クリックで展開**

丁寧な公式解説です。
https://atcoder.jp/contests/arc109/editorial/370

:::

---
### 12 　3 Letters

:::spoiler **クリックで展開**

参考: https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2021/0307_agc052

公式解説を見ても??? だったので、思いつき方まで考察してみる。

まず、ABCを 012に対応させる。
次に、文字列操作なので不変量を考えてみる。

端を除くと、できる操作は ABA → ACA みたいに、同じ文字に挟まれているときだけ。

mod3での隣接項の差分を考えてみると、
ABA は 1,2
ACA は 2,1
である。そのため、操作は差分配列上のswap操作と考えることができる。
(※若しくは、値が1だけ隣に移動する操作と見ることもできる)

多少はシンプルになったものの、端の処理が大変である。

ABAC --(数字に変換)--> [0,1,0,2]

これの隣接差配列を考える。
{1,2,2} となる。

さて、これだと初項の情報が落ちてしまっている。
そこで、先頭に初項の値を追加してみよう。これを<>列で表す。

{1,2,2} -> <0,1,2,2> である。(A=0なので)

では、初項をCに変更した時、この列はどうなるか？
CBAC->[2,1,0,2]->{2,2,2}-> <2,2,2,2>

ここで、<> 列の最初の値は mod3で正しいならばなんでもokというルールを追加。
CBAC->[2,1,0,2]->{2,2,2}-> <-1,2,2,2> も可とする。
すると、値の移動(ある値を1減らして、隣を1増やす)として表せるようになる。

さらに、後ろにも値を追加。これはなんでもいい
<-1,2,2,2,?> みたいな感じになる。これを最終的な<>列と定義する。

この時、最終的な<>列　→　元の列　は単射である。
最終的な<>列上で値を移動する操作は、元の列上の validな操作に対して単射。
後は、最終的な<>列上での最短経路を考えればok

とりあえず、総和は一緒でないといけない。
これは、一番後ろに付け足す値で調節する。

初項の値を決めると、累積和列の差分のabsの総和が最小の操作数である。

後は、初稿の値を決めたい。
これは単調性があるので三分探索をすればいい

ACコード
https://atcoder.jp/contests/agc052/submissions/47408877

:::

---