ABC 6,8問体制(126..最新)のD問題をだいたい解いたので、そこから得た教訓をまとめていきます。

トップページへ

コードはこちら

マスを頂点をみなして、あるマスから他のマスへの最短距離を求める。126-Dと同様にBFSで求まる。木ではないので、既知の最短距離ではないマスは移動しない(移動すると無限ループになる)。

コードはこちら

組み合わせ総数と累積和を上手く貯える。

$A_1 ... A_n$ から $k$ 個選ぶ方法として

• 両端を選んで残り $k-2$ 個選ぶ
• 先頭(1番目)と最後の前(n-1番目)を選んで最後(n番目)は選ばない。他を $k-2$ 個選ぶ。
• 先頭(1番目)と最後の前の前(n-2番目)を選んでそれ以後は選ばない。他を $k-2$ 個選ぶ。

... という方法を考える。要するに最初と最後の要素の添え字の差(幅-1)が $n-1, n-2, ... , k-1$ になるように選ぶ。それぞれの選び方は ${n-2} \choose {k-2}$ 通りで、最初と最後の要素の添え字の差と定数 $k$ で決まる。ここで ${{n-1} \choose {k}} = {n \choose {k}} * (n-k) / n \quad for \quad n>0$ を使うことで、選び方の数を逐次的に求めることができる。

最初と最後の要素の添え字の差が $w-1$ と決まっているとき、 $f(X)$ は $(a_w-a_1) + (a_{w+1}-a_2) + ... + (a_{n}-a_{n-w+1})$ であり、符号をまとめると $(a_w + a_{w+1} + ... + a_{n}) - (a_1 + ... + a_{n-w+1})$ である。まとめて足す部分とまとめて引く部分については、累積和を使うことでそれぞれ $O(1)$ で求まる。

よって添え字の幅が $O(N)$ なので全体の計算量も $O(N)$ になる。

コードはこちら

二点を通る最小の円または三点を通る最小の円のうち、どちらか小さい方である。ある円の中心と半径を決めたときに、他の頂点が収まっているかどうかは総当たりで分かる。

二点を通る最小の円については、中点を円の中心にすればよい。座標をあらかじめ2倍し、距離の二乗で比較すると、計算誤差が無くなる。

三点を通る最小の円については、外接円の中心を公式で求める。分母が0のときを特別扱いする。中心の座標は整数にならないので、中心から他の座標の距離を比較するときは許容誤差を持たせる。

コードはこちら

Nが200000と読んで、いろいろ探索するより数え上げた方が早く実装できる、と勘づく。

先頭と末尾の組は9x9=81通りしかないので、 $1..N$ を81通りに分類すればよい。K進数の最上位の桁は、Kで繰り返し割ってK未満になったときの数である。

コードはこちら

手抜きも時に重要。

$A_{1..N}$ の最小公倍数(LCM)を求めて、LCM/AをBにすればいい。 std::lcm() を使うとオーバーフローするので、 $A_{1..N}$ を素因数分解して得られるそれぞれの素数の出現回数を求める。一度でも出現する素数について最大出現回数を累乗し、それらを掛けたものをLCMにする。

ここで $B_i$ を真面目に求めようとして、LCMを構成する素数の個数から $A_i$ を構成する素数の個数を引いて残った素数を全部かけるとTLEする。単に $LCM / A_i = B_i$ で問題ない。

コードはこちら

上手く状態遷移をまとめれば、状態数が指数になるのを防げる。

モンスターをどういう順番で攻撃しても、体力が0になるまでの体力の減り方は同じ、ということが重要である。よって体力の減り方の経路は一通りだけ(2で繰り返し割る)で、ある体力のモンスターが何体あるかだけ数えれば攻撃回数になる。

コードはこちら

Greedyだと思ったらDPだった。

ということでDPで解く。このとき、 $i$ 番目までの魔法を使い(というか $i$ 番目の魔法を初めて繰り返し使うことにして)、 $h$ のダメージを与えた時( $h$ 以上は一律 $h$ )とする、 $dp[i+1][j+A]$ に配るのは $dp[i+1][j] + B$ である。 $j$ を内ループに置くと魔法を無制限に使えることを表現できる。品物を一個だけ加えるナップザックDPの $dp[i][j] + B$ から引くと上手くいかない。

コードはこちら

遅延評価いもす法

解き方は複数あるが、遅延評価いもす法が分かりやすい。モンスターの座標 $1..N$ におけるダメージをいもす法で更新していく。左にいるモンスターから最小回数で順に倒すgreedyということは分かったが、回数がバイナリ1/0でないことをすっかり忘れていた。

コードはこちら

期待値の加法性を使う。

隣接するK個のサイコロとあるので、サイコロK個の期待値は、サイコロを1個加えてK+1個になったら、最後に加えたサイコロの期待値を減らす。期待値の加法性からこれが成り立つ。移動平均の求め方と一緒である。

コードはこちら

桁を上から見るか、下から見るか。

下の桁から見るのが正解である。もしかしたら上の桁から見ても解けるのかもしれないが、私には解けなかった。公式解説を見ると再帰で解けると解るが、もう少し読み解くと以下のようになる。数字列 $abcd...$ があり、非0の数字が $abcd$ に $k$ 個要るとき、

• $k=0$ なら $a=b=c=d=0$ の1通り
• $k<4$ つまり $k$ が $abcd$ より短すぎるなら0通り

を特別扱いする。次に下の桁 $...$ への繰り下がり $inCarry$ が起きるかどうかを引数で受け取っておく。最下位桁については $inCarry=0$ である。

• $d=0$ かつ $inCarry=1$ なら、下の桁 $...$ への繰り下がりがあり、かつ上の桁 $c$ からの繰り下がりが必ず起きる( $outCarry=1$ )。それ以外で、上の桁からの繰り下がりが起きるかどうかは状況次第である( $outCarry=0$ )。
• $inCarry=1$ なら $d$ を1引く。つまり $d:=(d+9) mod 10$ にする。

ここで $d$ の値について考察し、上の桁への再帰を考える。

• $d$ があるこの桁は0ということにして、 $k$ を消費しない。この組み合わせの数は、末尾を削除した数字の並び、繰り下がり、非0の数字の数がそれぞれ $(abc, outCarry, k)$ の場合について求めたものである(なので再帰的定義である)。
• $d>0$ ならこの桁は非0の値 $1..d$ のいずれかにして、 $k$ を1消費する。この組み合わせの数は、同様に $(abc, outCarry, k-1)$ の場合について求めたものを $d$ 倍した値である。
• $d<9$ ならこの桁は非0の値 $d+1..9$ のいずれかにして、 $k$ を1消費する。この組み合わせの数は、同様に $(abc, 1, k-1)$ の場合について求めたものを $9-d$ 倍した値である。上の桁から繰り下がりがないと、 $d$ より大きな数字をこの桁に設定できない。

再帰呼び出しで引数で何度も呼び出すことに備えてメモ化するとよい。再帰とメモ化するためのキーは、 $N$ の桁を表現する数字の部分列そのものではなく、文字列の先頭からの長さでよい。再帰呼び出しは $N$ の最下位桁から順に取り除くからである。つまり再帰呼び出しの引数とメモ化のキーを(入力 $N$ から上位何桁取るか、繰り下がり、非0の数字の数)にする。

コードはこちら

勘で解いた。

向きを直交座標系(列はXが増える方向に右、行はYが増える方向に上)とする。矩形領域 $(r1,c1)-(r2,c2)$ に入る直前にたどり着くまで何通り数え、矩形領域に入り(これは一通り)、矩形領域内を移動する方法を数える。

矩形領域 $(r1,c1)-(r2,c2)$ に下から入るとき、 $(r1-1,x) : c1 \leq x \leq c2$ にたどり着いて、 $(r1,x)$ で矩形領域に入る。これは ${r1-1+x} \choose {x}$ 通りである。

$(r1,x)$ から矩形領域内を移動する方法を数える。矩形領域の高さ $h = r2 - r1 + 1$ とする。矩形領域に初めて入ってから $i = 0..(c2-c1+1)$ 列ちょうど移動する方法が何通りか $C[i]$ を数える。 $i = 0$ なら $h$ 通りである。未証明だが $C[i+1] = C[i] (h+1) / (i+1)$ が成り立つ。

累積和 $\sum_{j=0}^i C[i]$ を取ると、矩形領域に初めて入ってから $i$ 列以内移動する方法が何通りか分かる。ここに矩形領域に入るまで何通りか掛ける。これらの和が答えである。左から入る方法も同様に求める。

$1..2 \times 10^6$ の階乗と、 $1..2 \times 10^6$ 逆数をあらかじめ求めて計算を高速化する。

実は二次元累積和で解けるらしいが、どうやって高速化するのかわからない。

コードはこちら

困ったら二分探索。

二数を書けた結果が、正、ゼロ、負の三通りに分けて、 $k$ を超える積が何個あるか尺取り法で数え上げる。緻密な実装が問われる。

コードはこちら

154-Eと似ている。

基本的には154-Eと同様なのだが、入力が大きいのでDFSは使えず、BFSするとTLEした。なので単純にメモ化しながらループする。メモ化するのは、(下から何桁目までに、下の桁から繰上りがあったかどうか) のとき使う紙幣の最小枚数 $DP[0..N][0..1]$ である。

154-Eの繰り下がりと同様に、ある桁 $d$ 、下の桁から繰上りがあったかどうか $inCarry=0 or 1$ があったとき、上の桁から繰り下げるかどうか $outCarry=0 or 1$ を固定して、

• $d:=d+inCarry$ について
• $d<10$ ならその場で $d$ 枚紙幣を払い
• $d>0$ なら上の桁から借りてお釣りをもらうことにして $10-d$ 枚紙幣を払う

最上位桁が繰り上がったときを考慮する必要がある(そうしないと91の答えが3でなく2になってしまう)。このためには、 $min(DP[N][inCarry]) += inCarry$ とすればよい。答えは $min(DP[N][0..1])$ である。

コードはこちら

二項定理に対する基本的な知識が問われる。それとダブリングの使いどころである。

Nから0..N通り選ぶ組み合わせの総和は $2^N-1$ 通りである。なぜなら $1..N$ 番目の要素を選ぶか選ばないかを、全要素について独立に数え上げることと同じだからである。1引くのは何も選ばないケースを除くためだ。

nが $10^9$ と大きいので $2^n$ を繰り返し求めると終わらない。 $2^{i+j} = 2^i * 2^j$ なので $i$ と $j$ を2のべき乗について求めると巨大なnでも $2^n : mod : 1000000007$ が求まる。 $2^{0..32} : mod : 1000000007$ はダブリングで求める。コードスニペットを書いてテストしておくとよいだろう。

ここまできたら $2^n - {}_n C_a - {}_n C_b$ が答えである。

コードはこちら

k個のお菓子をn人に分ける。

自力では解けず、こちらの解説を用いた。この解説通り実装すればよい。

解説中、 $n-i$ 個の部屋に1人以上、合計で $n$ 人を入れる組み合わせの総数は、 $n$ 人を $n-i$ 部屋に一人ずつ入れて、残り $i$ 人を $n-i$ 部屋に入れる組み合わせの数である。これは $i$ 人と $n-i-1$ 個の仕切りについて、人と仕切りを区別しない順列組み合わせの数 ${{i+n-i-1} \choose {i}}$ = ${{n-1} \choose {i}}$ = ${{n-1} \choose {n-i-1}}$ である。

${n \choose {n-i}}$ = $n!/(i!*(n-i)!)$ = ${n \choose {n-(i-1)}} * (n-i+1) / i$ を用いて組み合わせの総数を逐次的に求めないとTLEする。

コードはこちら

Union-find木を知っていると解ける、知らないと解けないか実装が大変な問題である。

友達の友達は友達という推移関係は、友達関係をグラフで表現した時の連結成分である。なのでそれぞれの連結成分の頂点数から、既に友達である関係の数と、 同じ連結成分で ブロックしている関係の数を引く。異なる連結成分でブロックしている関係は、友達の友達は友達という推移関係は成り立たないので引かない。

コードはこちら

力業すぎる。

type 2クエリからセグメント木を連想する。文字は英小文字しかないのだから、26本のセグメント木を作り、ある区間にa,b, ..., z があるかどうか更新して調べればよい。type 1 クエリで変更前の文字が何であったかは、 $S$ を直接更新すれば分かる。

コードはこちら

コレクションを反転するのはコストが高いが、反転したとみなすのフラグ1個書き換えるだけである。手元の列に対して、

• 手元の列が反転していないときに先頭に追加するのは、列の先頭に追加する
• 手元の列が反転していないときに末尾に追加するのは、列の末尾に追加する
• 手元の列が反転しているときに先頭に追加するのは、列の末尾に追加する
• 手元の列が反転しているときに末尾に追加するのは、列の先頭に追加する

反転しているか否か、先頭と末尾のどちらに追加するか if文で4通りに分けてもいいし、xorを取って2通りにまとめてもよい。

コードはこちら

全部の組み合わせの個数を挙げてから、ある種の組み合わせの個数を引く。

整数 $x$ が書かれたボールが $m$ 個あるなら、ボールの選び方は $((m+1) * m) / 2$ 通りである。整数 $x$ から個数 $m$ への連想配列にしておけば $x$ の値域について悩まなくて済む。

後はボールが一個 ($A_1 .. A_N$) 減ったら、その分ボールの選び方が減るのでその値を計算する。

コードはこちら

制約をよく見る。

$H \leq 10$ から、鉄則本をA72を思い出す。横方向(行方向)に沿って切る方法は $2^{H-1}$ しかないので総当たりできそうである。後は縦方向(列方向)の切り方をgreedyに求める。

例外処理として、 $K$ が小さいときはすべての列を幅1で切っても制約を満たさない可能性がある(例えば $K=1$ ですべてのマスが1のとき)。そのような横方向の切り方は見つけ次第除外する。後は一列ずつ $i=1..W$ 列の右側で切れるかどうか試して、

• 切れ端に含まれる 1が $K$ 個を超えたら、 $i$ 列の右側ではなく左側で切る。 $i$ 列を起点に調べなおす。
• そうでなければ切らずに、 $i+1$ 列の右側で切れるかどうか調べる。

横方向+縦方向に切った回数の最小値が答えである。

コードはこちら

入力サイズから計算量を見切ることが大事である。

頂点の位置を、Xより右、X-Y間、Yより左に場合分けして解くととてもめんどくさい。BFSで距離を求めると簡単である。こういうときは $N$ が二千しかないことから、各頂点を出発点として総当たりでTLEしないと予想できる。

辺の長さが固定のときにBFSで距離を求める方法は既出なので省略する。

コードはこちら

std::vector::resize() を使う

問題文から X<A, Y<B なので場合分けを減らせる。無色のリンゴを補充しなければならない状況はなく、置き換えるだけでよいことが分かる。リンゴを色別に、美味しさの降順にソートして、赤いリンゴは元々 $X$ 個だったと考えると楽である。 std::vector::resize() は余分な要素を切り捨てるので便利である。

置き換えるなら最もおいしくない赤と緑のリンゴを、最も美味しいリンゴに置き換えればよいだろう。これは尺取り法でできる。赤と緑のリンゴをすべて置き換え終わったらもうできることはない(もっと美味しい無色のリンゴに置き換えたはずだから)ので、尺取り法のインデックスに気を付ける。

コードはこちら

これも 160-Dと同様に、入力サイズから計算量を見切ることが大事である。

再帰とメモ化で取りうる組み合わせを累計するとめんどくさそうである。しかし10進数5桁しかないのだから、上の桁に下の桁(0には0と1、9には8と9、それ以外の $i$ は $i-1, i, i+1$ をくっつけても全探索できる。

コードはこちら

ゴールから見た方が簡単である。

まず $N = i \times K+1$ を満たす数は $K$ ずつ減算して1になる。次に $N = K^{i}(K \times j+1)$ を満たす数は $K$ ずつ除算して1になる。よって $i = 2.. \sqrt{N}$ を決め打ちして、 $i$ で割れるだけ割って残った数を $i$ で割った余りが1なら、 $i$ は $K$ の候補になる。私の実装はこのように $N$ から減らしたが、解説にあるように1から $i$ を構成する方が考えやすい。

念のため $K$ の候補に $N-1$ の約数と $N$ を加えてから1を除いた。 std::set で重複を除いている。

コードはこちら

これも 160-D, 161-Dと同様に、入力サイズから計算量を見切ることが大事である。配列の添え字がはみ出さないように全探索すればよい。

コードはこちら

素因数分解か約数列挙して包除原理だろうと思ったが、具体的な解法まで時間が掛かった。

前処理として、 $1..K$ それぞれの約数を列挙する。これは約数の側を $i = 1..K$ に固定して、 $i$ の倍数は約数 $i$ を持つと計算する。

$A_1$ を $1..K$ に固定して全探索する。

整数 $B$ の約数を小さい順に $S_B = [1,...,B]$ とする。 $A_1 = B$ のときにある数 $D \in S_B$ があって $GCD(A) = D$ となるのは、 $A_{2..N}$ がすべて $D$ の倍数であり、なおかつ $GCD(A)$ が $D$ 以外の $D$ の倍数にならないときである。これを包除原理で求める。

$S_B$ の降順に調べる。 $A_{2..N}$ がすべて $B$ の倍数になる組み合わせは、 $1..K$ にある $B$ の倍数の任意の組み合わせなので、 $(\lfloor K/B \rfloor)^{N-1}$ 通りである。これを $C_B[B]$ とする。

$S_B$ について、 $D \in S_B , D \ne B$ について考える。 $A_{2..N}$ がすべて $D$ の倍数になる組み合わせは、 $(\lfloor K/D \rfloor)^{N-1}$ 通りである。ここから、 $GCD(A) = F &gt; D$ になる組み合わせを引く。これは $F \in S, F mod D = 0$ なる $F$ について $C_B[E]$ 通りを引く。

$S$ の降順に $C_B[]$ を求め、答えに $\sum_{i \in S} i C_B[i]$ を足す。

コードはこちら

巨大な数 $10^{100}$ が意味するのは、数を何個足したかが和から区別できることである。この習慣を覚えておく。

それさえわかれば、 $0..N$ から $K$ 個選んだときに、和として表現できる数とできない数を求めればよい。

• 和の最小値は何も選ばない0、最大値は全部選ぶ $sum(i=0..{N})$ である。
• $s = sum(i=0..{K-1})$ が最小値なので、それより小さい数 $S$ 個は和になりえない。
• 足す数をそれぞれ $N-i$ とすれば左右反転して、 $sum(i=0..{N})$ までの $S$ 個は和になりえない。
• それ以外の和は表現可能である(和にする数の集合に対して、ある数とそれより1多い数を交換すればよい。このような数は必ずみつかる)

コードはこちら

• 鉄則本の「8.6 文字列のハッシュ」問題 A56を知っていると解ける
• 累積和から部分列の総和を取る方法が使える

文字列から部分文字列を取っていくときに、部分文字列から得られるハッシュのような情報を得る。ある数が2019で割れるかどうかは、2019のすべての素因数(3と673)で割れるかどうかと同じである。つまり3で割った余りと673で割った余りを、文字列の末尾から先頭に向かって取っていく。説明の都合上、文字列を std::reverse で逆順にして最も下の桁を文字列の先頭とする。

...abcdef と桁がたくさんある整数のうち、下位1,2,3...桁を673で割った余り(mod 673)について考える。3で割った余りも同様である。

• f mod 673は、実際に割れば分かる
• ef mod 673は、(e*10 + (f mod 673)) mod 673
• def mod 673で割った余りは、(d*100 + (ef mod 673)) mod 673
• cdef mod 673で割った余りは、(c*1000 + (def mod 673)) mod 673

こうして最上位の桁まで、最も下の桁から連続する桁を673で割った余りを計算できる。10, 100, ... と $10^n$ を673で割った余りも併せて計算しておく。

次に下の桁から順に0に置き換えていく。

• 最初は何も置き換えない。このときf, ef, def, ... を673で割り切れるかどうかは既に調べてある
• 最下位の桁を0に置き換える。例えばcdefをcde0に置き換える。cde0が673で割り切れるかどうかは、 $(cdef - f) : mod : 637 \equiv 0$ つまり $f$ を673で割った余りと $cdef$ を673で割った余りが等しいということである。ここで f mod 7 を固定して、f mod 7 と等しい f, ef, def, ... を数えれば、題意の総数の一部が求まる。
• 一般的には、下の桁から連続する $i (\geq 0)$ 個の0を置き換える。下i桁 mod 7 と等しい f, ef, def, ... を数えれば、題意の総数が求まる。下i桁の値は初期値を0とし、 $i$ を更新するごとに $10^{i}$ * i桁目の数字 mod 673 を足す。
• f, ef, def, ... mod 673 と f, ef, def, ... mod 3 から、 f, ef, def, ... mod 2019 が求まる。これは $i$ と関係ないので、mod 2019をキーとして該当する余りの出現回数を一度数えて連想配列に保存しておく。

この考え方は、部分列の総和を求めるのに累積和を使う方法とよく似ている。和を余りに置き換えただけなので。

Mod 3とmod 673はACLを使うと書きやすい。

#include <atcoder/all>
using ModInt3 = atcoder::static_modint<3>;
using ModInt673 = atcoder::static_modint<673>;

コードはこちら

$N$ が小さいのでDFSの全探索で行ける。

コードはこちら

直観的には、Aを増やすほどBで割った余りが溜まっていって、Bになると余りが0に戻る、ということである。 $A &lt; B$ だと戻らないので入力条件に気を付ける。

コードはこちら

方針は立ったが実装に手間取った。

参加者を固定して、対戦場が動くと考える。同じ参加者と二度対戦しないという条件を考えるとき、参加者が動くのも対戦場が動くのも相対的には同じである。

ある対戦場の割り当て $(L,R)$ とする。 $(R - L) mod N$ および $(L - R) mod N$ となる対戦場が一意なら題意を満たす。ここで周回を考慮して $mod$ は非負の最小な数とする。

$N$ が奇数なら、 $M$ を偶数として、 $M = 2,4,...,\lfloor N/2 \rfloor$ にする。 $-M$ については　$N-M mod N$ が奇数なのでやはり一意性がある。このような対戦場は $L + R = N-1$ になる組を列挙すればできる。

$N$ が偶数なら、 $M = 1,3,...,\lceil M/2 \rceil$ な対戦場、 $M = 2,4,...,M/2$ な対戦場を作る。前者は $L + R = 1 + \lceil M/2 \rceil$ になる組を列挙すればできる。後者は $L + R = 2 + M/2$ になる組を列挙し、 $\lceil M/2 \rceil$ 足してずらす。

コードはこちら

三次以上の多項式の問題は、n条根を取ると変数の取る領域がそれほど大きくないので総当たりできる。

$A^5-B^5 = (A-B)(A^4+A^3B+A^2B^2+AB^3+B^4)$ なので、 $X$ の約数を求めて総当たりすればいい。 $A-B$ は約数を総当たりし $A$ を決め打ちして総当たりすればいい。 $X^5-(X-1)^5 &gt; 5X^4$ なので、 $A$ は下限が0、上限は ${5*x}^{1/4}$ もあれば十分だろう。

約数を求めるは頻出なのでコードスニペットを書いておく。平方数の約数を二度数えてしまいがちである。

コードはこちら

絶対値は順序を固定すれば外せる。

組み合わせを列挙するので、一般性を失わず $A_i, A_j$ (i<j) なペアだけ考えればよい。定式化すると以下のように大変だが、手を動かすと何となくわかってくる。

題意から $A_1 + A_2 = 1, A_1 + A_3 = 2, ...$ と解る。これを $A_1, A_2, ...$ について数えあげると $O(N^2)$ なのでTLEするが、 $A_1$ を $A_2$ に取り換える方法がありそうである。

実際できるのである。 $A_i + A_j = j-i \Leftrightarrow A_j - j = -(A_i + i)$ である。よって $A_j - j : for : j=1..N$ が何個あるか求めて連想配列にいれておき、 $-(A_i + i) : for : i..N$ がいくつあるか連想配列で引いて総和を求めると答えが出る。

コードはこちら

文字 $x \in {A,B,C}$ に対応する値を $V_x$ とする。

$xy$ の操作で $x = 0, y = 0$ だと詰むので、詰みを回避する。ともかく 00 にしなければよく、一手先読みをすればいい。直近の操作を $xy$ , 次の操作を $pq$ とする。

$xy$ と $pq$ のうち一つだけが一致するとする。制約から、少なくとも一つは一致し、二つとも一致する場合もある。代表として $x = p$ とするが、他も同様である。 $V_x = 1 \land V_q = 0$ なら、今の操作で $V_x = 0$ にすると詰むので、 $V_x$ を1増やし、 $V_y$ を1減らす。

それ以外の状況では、 $V_x &lt; V_y$ なら $V_x$ を1増やし、 $V_y$ を1減らす。そうでなければ $V_x$ を1減らし、 $V_y$ を1増やす。

こうしてすべての操作を決めた後に再生して、 $V$ が負になったら No 、ならなければ操作を出力する。

不変量だと思ったらやはり不変量だった。和が 1,2,3以上で区別できた。一手先読みであるのは上記と同じ考察である。

コードはこちら

動的計画法できなさそう、という見切りが必要。

同じ色が並んでいるブロックが残り $0 \leq i \leq K$ 組というのはメモ化できなさそうである。そこで発想を変える。 $N$ 個のブロックがあり、同じ色が並んでいるブロックが $i$ 組あるなら ${N-1} \choose {i}$ 箇所ある。

これをすべての $i$ について求める。同じ色が並んでいるブロックがなければ、色は $M*(M-1)^{N-1}$ 通りある。同じ色が並んでいるブロックが $i$ 組あるならブロックを圧縮する、つまり $N-i$ 個のブロックがあると考えて、同じ色が並んでいるブロックが ${N-1-i} \choose {i}$ 箇所ある。156-Eと同様、組み合わせの数は逐次的に求める。

コードはこちら

部屋1から他の部屋の距離をBFSで求める。方法は既出の通り。

コードはこちら

2時間近くかかったが、久しぶりに青diffを解けた。

$A_i \cdot A_j + B_i \cdot B_j = 0$ が内積だということはすぐわかる。 $(A_i, B_i) = (0,0)$ ならどんな $(A_j, B_j)$ との内積も0になるので原点を特別扱いすることも分かる。しかしそこからが長考だった。

自明な答えとして、イワシは一匹なら答えは1である。

原点なイワシ $(A_i, B_i) = (0,0)$ をいったん無視して、 $(A_i, B_i) \ne (0,0)$ なるベクトルを既約のベクトルにして、ある向きのベクトルが何種類あるか数えられるようにする。これは $(A_i, B_i)$ を $gcd(|A_i|, |B_i|)$ で割る。割ったものに対して、以下の通り数えて連想配列 std::map<std::pair<Num, Num>, Num> に収める。ここで0種類増やす、つまり連想配列のエントリだけ作っておくと後の処理が楽である。

• 既約なベクトル $(A_i, B_i)$ を1種類増やす
• 対称なベクトル $(-A_i, -B_i)$ を0種類増やす
• 直交するベクトル $(-B_i, A_i)$ $(B_i, -A_i)$ を0種類増やす

次に登場したベクトル $(A_i, B_i)$ を種類ごとに std::vector<std::pair<Num, Num>> に追加する。ここで $(A_i, B_i)$ が出現したら $(-A_i, -B_i), (-B_i, A_i), (B_i, -A_i)$ も既に出現したことにすると、対称または直交するベクトルをまとめて一回だけ追加できる。追加したかどうかは std::set<std::pair<Num, Num>> で管理する。

ベクトル $(A_i, B_i)$ の種類ごとに、イワシをどう組み合わせられるか考える。 $(A_i, B_i)$ および $(-A_i, -B_i)$ から $P_i (\geq 0)$ 匹、直交する $(-B_i, A_i)$ および $(B_i, -A_i)$ から $Q_i (\geq 0)$ 匹選べるとする。直交するイワシは選べないが直交しないイワシは選べるので、選べる組み合わせは $C_i = 2^{P_i} + 2^{Q_i} - 1$ 通りである。

ベクトル $(A_i, B_i)$ の種類が異なるイワシは直交しないので、独立に組み合わせられる。よって選べる組み合わせは $\prod_i C_i : (A_i, B_i) \ne (0,0)$ である。

ここで重要なこととして、原点なイワシ $(A_i, B_i) = (0,0)$ が $K$ 匹いたら、それぞれ一匹ずつクーラーボックスに入れることができる。これを忘れるとWAする。よって答えは $\prod_i C_i : (A_i, B_i) \ne (0,0) + K$ である。

1260 ms掛かっているのを見ると、ベクトルの種類を数え上げるにはもう少し洗練された方法がありそうだ。

コードはこちら

素因数分解して、素数pで1回、2回、3回... 割ってみる。素因数とその数をコードスニペットを書いておく。

コードはこちら

二分探索ではなかった。

$lower..upper$ の範囲の中央値はいかようにも作れる。では $lower$ と $upper$ を二分探索で求めるコードを書くと異常にややこしい。実は $lower$ は $A$ の中央値、 $upper$ は $B$ の中央値である。プログラミングというより数学の問題である。

小数が出ると厄介なので、入力値を二倍して答える前に半分にする。 $lower$ が奇数なら取りうる中央値は1個多い( $upper$ も同様)。

コードはこちら

任意の組み合わせを数え上げるのに、ソートしても一般性を失わないだろうか。

小さな数でそれより大きな数を割ることはできない。よって昇順にソートして、自分より大きな数で割り切れるかどうか確かめる。そのまま実装すると $O(N^2)$ になってしまうので、約数が既に出現したかどうか調べる。

なお同じ値の数が複数ある場合は互いに割り切れるので、答えの回数には含めない。

コードはこちら

力業すぎる。

C++の速度でゴリ押すなら、幼稚園をキー、園児のレートを値とする std::map<Num, std::multiset<Num>> を作ればよい。min(全幼稚園のmaxレート)は、全幼稚園を載せたセグメント木で管理する。関数を std::max , 元(モノイド)を inf にしておけば、2秒を切ってACできる。1-based indexで通すなら入力を読み込むときもそうする。

コードはこちら

要素が何個あるかは気にしない。

なので $B_i$ が何個あるかを連想配列で管理する。クエリごとに、 $B_i$ がn個あるなら、 $C_i$ をn個追加して $B_i$ をn個削除する。

コードはこちら

E問題が10分以下で解けることもある。

めったにないE問題茶diffである。XORパリティと言えばわかる。自分以外の数字のXORを取るということは、数字の各桁について、自分以外の数字で1が出た回数が奇数回なら1、偶数回なら0を意味する。

$a_{1..N}$ を XORしてパリティを求める。1 XOR 1 = 0から、数字の各桁についてある $a_{1..N}$ は1回だけ数えるのと同じである(Nは偶数なので)。つまり数字の各桁について、 $a_{1..N}$ での出現回数が奇数回なら1、偶数回なら0を意味する。

ということで数字の各桁について、 $a_{1..N}$ での出現回数が奇数回(1)で、 $a_1=a_{2..N}$ での出現回数が奇数回(1)なら、 $a_1=0$ である。同様によく考えると、求める答えはパリティと $a_i$ のXORである。

コードはこちら

Aをから何冊読むか決めたら、Bから最大何冊読むかは一意に決まるので、尺取り法で求まる。

コードはこちら

縦の物を横にする。

ある数に約数が何個あるかを調べるのは大変である。しかし $1..N$ に約数 $i$ が何個あるかは、 $\lfloor N/i \rfloor$ 個とすぐわかる。縦横を入れ替えるだけですんなり解ける(私自身はこの解法を思いつかなかったが)。

コードはこちら

あれこれ悩むより、手を動かして試した方が早い。

最後の一人は誰かにとって心地よさは与えないので、フレンドリーさが最大の人から降順到着するのがよいと分かる。どこに入れるかであるが、Nが十分大きいとき、フレンドリーさが上位二名の間に入れればそこの心地よさが最小になる。つまり N, N-1, N-1, N-2, N-2, ... となる。

コードはこちら

方針はすぐ立ったが詰めが要る、最近のARCらしい問題である。

絶対の大きい方から $K$ 個取る。この集合を $S$ とし、残りを $U$ とする。

$S$ の積が非負ならそのまま答えである。そうでなければ $S$ の要素を一つ $U$ の要素一つと取り換えて積を非負にすることを考える。

• $S$ の正の数で最も絶対値が大きいものを(もしあれば) $P_s$ とする
• $S$ の負の数で最も絶対値が大きいものを(もしあれば) $N_s$ とする
• $U$ の正の数で最も絶対値が大きいものを(もしあれば) $P_u$ とする
• $U$ の負の数で最も絶対値が大きいものを(もしあれば) $N_u$ とする

1. $P_s, N_s, P_U, N_u$ がすべてあるなら、 $P_u / N_s &gt; N_u / P_s$ なら $P_u, N_s$ を交換する。そうでなければ $N_u, P_s$ を交換する。交換後の $S$ の積が答えである。
2. $(P_s, N_s)$ または $(P_U, N_u)$ の組の一方だけあるなら、その組の値を交換する。交換後の $S$ の積が答えである。
3. それ以外なら絶対値の小さい方から $A$ を $K$ 個選んで掛けたものが答えである。特に $A$ に0があるなら答えは0である。

分数を比較するときは、互いの分母を掛けて整数にして比較する。

コードはこちら

$K$ が小さいので、実際に求めれば分かる。

コードはこちら

選択肢が二つあるが、片方があればもう片方は要らないということがある。

RWの並びはよいがWRの並びはよくないので、WRを減らせばいい。ならばRだけ左にずらっと並べて、Wだけ右にずらっと並ぶよう、Wを右に寄せればいいと分かる。つまり最左のWと最右のR入れ替えればよく、この回数を求める。これは尺取り法でできるので O(N)で解ける。

石を入れ替えれば災いは1または2減るするかもしれないが、石の色を変えても1しか減らないので、石の色を変える意味はない。

コードはこちら

二分探索である。

丸太の最大長を決め打ち、 $K$ 回以内で切れるか測ればよい。長さ $L$ の丸太を $i$ 回切るなら明らかに $i$ 等分が最適なので(何を思ったか $2^i$ 回切って数十分使ってしまった)、何回切る必要があるかは $\lceil L/i \rceil$ 回である。

なのだが、探索幅の下限を $1e-6$ にしないと、WAかTLEになる。整数演算だけで解こうしたが上手くいかなかった。だがやはり整数で解かないと解が安定しないらしい。整数解法はこちらで、区間のleftではなくrightつまり total > k ではない最小の値を返す。二分探索はこれが常にややこしい。

コードはこちら だが、実質的にはある記事 そのものである。

Mo's Algorithm で解く。Mo's Algorithmを知らないとどうにもならない。

コードはこちら

解の方針は立つが、実装が非常に辛い。

まず状態遷移をループ成分に分解する。DFSでもよさそうだが、union-find木の代表元を使うと簡単である。それぞれのループ成分ごとにスコアを求めて、その最大値が答えである。

問題はスコアの求め方である。一周するとスコアが正の値になるなら、できるだけたくさん周回する。そうでそうでなければ一周しなければよい。一周に満たない場合のスコアは起点を終点の組を総当たりして $O(N^2)$ で求まる。

と書くと簡単に見えるが、WAしないように実装するのがものすごく大変である。二周分のスコアの累積和を求めて、すべての起点と長さを総当たりすればいいはずなのだが、それだけではどうしてもWAを取り切れない。

コードはこちら

三次元DP

三次元の動的計画法を作る。行、列、ある行でのアイテム取得回数 0..3 を上から下、左から右にスキャンする。0行0列は価値0のアイテムがあるとみなす、つまり入力アイテムの位置を1-base indexingすると、スタート地点のアイテムを拾うかどうかを例外処理しなくて済む。

左から右にスキャンしてアイテムを拾うとアイテムの数が1増えるが、行を下に移ったときに拾ったアイテムの数が0に戻ることに注意する。

コードはこちら

普通にBFSで解ける。

と、公式解説に書いてある。おそらくその方が実装が簡単なのだろう。私の解き方は少し回りくどいが以下の通りである。

• すべてのマスを、ワープなしで行ける範囲で連結成分分解する。Union-find木を使うとできる。
• 連結成分を頂点、ワープで行ける連結成分を辺とするグラフを構成する。頂点番号は連結成分の代表元( $x+y*1000$ でいい)、ワープで行けるかどうかは各頂点から25通り試せばよい。同一連結成分同士を辺でつながないように注意する。
• このグラフについて、出発点の連結成分から目的地の連結成分までに経由する、最短距離つまり最小の辺の数をBFSで求める。到達不可能なら距離は無限大である。

多重辺を作らないようグラフは std::map<Num, std::set<Num>> にするが、頂点から延びる辺は edges[current] で取り出す。 edges.at(current) だと、辺がないときに例外が飛んでプロセスが終了してしまう。

コードはこちら

縦横を独立に考える。

破壊対象が最も多い行と、破壊対象が最も多い列はそれぞれ独立に考えることができる。よって破壊対象が最多の $rmax$ である行(複数あり得る)と、破壊対象が最多の $cmax$ である列(複数あり得る)が候補になる。これらの行列の交点ぴったりに破壊対象があると、破壊対象が一つ減るので、これら行列の組を全探索する。

実は全探索しても大丈夫である。もし交点に破壊対象がないのであれば答えは $rmax+cmax$ と解るのでその場で終了できる。この探索は最大 $M+1$ 回なので十分早く探索を打ち切ることができる(公式解説より)。

コードはこちら。

グループ分けといえばunion-find木である。

友達の友達は友達という推移関係は連結成分に分解できる。これをバラバラにするには、連結成分の数だけグループを作って、疎な連結成分の人をそれぞれのグループに集めればいい。よって最小のグループ数は最大の連結成分の要素数である。これは気が付かなかった。

当時は自前で実装したUnion-find木を使っていた。今はACLを使っている。

コードはこちら

用語の定義を落ち着いて理解すれば分かる。

$GCD(A,B,C) = GCD(GCD(A,B),C) = GCD(A,GCD(B,C))$ なので、すべての要素のGCDが1より大きければ not coprime である。

Pairwise coprime なら必ず setwise coprime だが逆は成り立たないので、 pairwise coprime ではない例を一つでもみつけたら setwise coprime と出力し、そうでなければ pairwise coprime である。これは $A_{i+1}$ の素因数が $A_1..A_i$ の素因数を含むかどうかで分かる。

コードはこちら

DFS(幅優先探索)はスタックの深さに注意すればきれいに再帰で書ける。

数列は順序が異なれば違うものと数えるので、3以上の数を $S$ から引いて残りを再帰的に求めればよい。 $S$ は2000しかないので、メモ化しておけば計算時間が指数オーダーになるのを防げるし、スタックもあふれない。

コードはこちら

45度回転。

$x+y$ で等高線が引けるのは分かったが、 $x-y$ の等高線は使い道が分からなかった。式変形は公式解説にあり、より詳しい解説が記事にある。

しかし式変形をしなくても直観的に理解する方法がある。xが左、yが上に増える座標系で、x+y等高線は左下-右上関係をとらえ、x-y等高線は右下-左上関係を捉えると思えば、二点のマンハッタン距離は、二点における等高線の差の大きい方と一致する。

コードはこちら

貰うDPで解く。

配るDPでも解けるようだが、貰うDPで解いた。まず区間を $L$ の昇順にソートする。 $i=2..N$ のマスについて、区間を順番に調べて

• 区間の終わり $i - R &lt; 1$ ならおわり
• そうでなければ区間 $\lbrack max(1, i-L), i-R \rbrack$ のマスに行く方法を全部足す

区間にある貰うマスに行く方法を累積和で管理すれば、区間は10以下なので計算量は $O(N)$ になる。答えも累積和の差分で出力する。

なおこの問題は遅延評価セグメント木でも解ける。実装は こちら 。ただしこの問題では $K$ が小さいので、DPで12 ms、遅延評価セグメント木635 ms となり高速化には寄与しない。

コードはこちら

厳密解を求めるより、鳩の巣原理で解く。

余りは $0..M-1$ しかないのだから、同じ余りが二度出たら以後は周期的になる。よって、周期を求めて、

• 周期に入る前
• 周期を繰り返し
• 周期の途中で $n$ に達する

について和を求める。ただし周期に入る前に $n$ に達することがある。

コードはこちら

遅延セグ木で解ける。想定解法は遅延セグ木ではないが、考え方は同じである。

行 $r$ における最左にある白い石の位置を $P[1][r]$ とする。初期値は $N$ である。同様に列 $c$ における最上にある白い石の位置を $P[2][c]$ とする。初期値は $N$ である。

操作 $T, a$ に対して、以下の通り考える。 $T = 1$ と $T = 2$ の操作は互いに対象なので、 $T = 1$ だけ示す。 $T = 2$ は右や上を適宜読み替える。

操作 $T$ において、白い石と挟む相手は $R = P[T][a]$ にある。挟んだ石 $max(0, R - 1)$ は黒くなる。 $i=1..R$ について、最上の白い石は $P[3-T][i] = min(P[3-T][i], a)$ になる。これはapply最小、prod最小のセグメント木で更新できる。

全てのクエリについて処理すると白い石が減って答えが求まる。

コードはこちら

ジムに通うと強さがどう変わるかは今の強さと今通うジムだけで決まり、これまでどう鍛えたかには関係ない。これをマルコフ性という。

なので両方のジムに通ったとして強さが低くなる方を選べばよい。弱いうちは強さをA倍にし、その後はB増やすとよさそうだが、そこまで考察しなくても解ける。

コードはこちら

三角不等式

三角不等式を考えない一般的な巡回路については、 ある都市を訪れたかどうかが $2^N$ 通り、ある都市を訪れたかどうかつまり訪れた都市の集合が決まっているときに、 今いる都市から他の都市への遷移が $N^2$ である。これを収束するまで繰り返すと $(N^3*2^N)$ になってTLEする。

しかし三角不等式が成り立つときは同じ都市を二度訪れる必要はない。入力例2が引っかけである。このときは訪れた都市の数が1,2,...,Nになるように集合を拡張すればいい。つまり(訪れた都市の集合, 今いる都市)をキー、値を最小コストとするDPを行い、すべての都市を訪れて今都市1にいるときの値を答えにする。

コードはこちら

算数的な方法で解ける。Nが大きいので、順列を数え上げるとTLEする。

算数的な方法は、数字をいい感じに組み合わせると、下から3桁目が偶数か奇数かと、下から1,2桁目の組を使って8の倍数になるかどうか調べる。要は000, 008, ..., 192 かどうか調べる。間違い無いがコード量が大きい。

実は下三桁を求める方が簡単である。こちらの記事を参照。

コードはこちら

数学的考察が必要。

解を満たす組は、小さい値から順に二つずつ取る、である。最も大きい値と最も小さい値を組む、ではない。この前提が間違っているとどうにもならない。これが分かれば累積和をつかって計算量を減らせる。

コードはこちら

問題をよく読む必要がある。問われているのは最大瞬間座標であって、 $A_{1..i}$ 一組の動作完了後ではない。

累積和を累積するのは頭がこんがらがるが、コードに落とし込めばそのままである。 $i$ 組目の動作をすると、最大瞬間座標は以下の最大値である。

• 出発点(右側にしか行かない場合)
• $A_i$ だけ進まずに行ける場所(これまでの最大瞬間座標)
• $A_i$ 進むことで初めて行ける最大瞬間座標

この後、位置に累積和と $A_i$ を足し、累積和に $A_i$ を足し、累積した動きの最大瞬間座標が過去最大なら差し替える。

コードはこちら

帰納法。縦横を独立な問題として考える。

縦方向に光が届くかと、横方向に光が届くは独立なので別々に考える。公式解説にある通り、すでに光が当たっているマスはその隣もあっていることを利用して計算量を減らせる。

コードはこちら

いもす法(Imos method)を使う。

NとSとTが大きいので、すべての整数時刻についてお湯の量を求めるとTLEする。だが変化点だけその累積和を求めることで、計算量を $O(N)$ に抑えらえる。

• S, T, P を得て、入りの変化点Sでお湯の量を +P, 出の変化点Tでお湯の量を -P するイベントを作る
• イベントを時刻の昇順に並べ替える
• 同一時刻のイベントについてお湯の量をまとめる
• ある時刻のお湯の量が容量Wを超えてたら供給不能、そうでなければ供給可能である

コードはこちら

引くDPは累積和にもできる。

配るDPを素朴に実装すると $O(N^3)$ になってTLEするので工夫がいる。解説通り、移動方向別に累積和を作ると解ける。漸化式から導けるが、より直観的には左、上、左上方向のどこから一手で飛んでこれるかについての、それぞれの累積和である。

コードはこちら

std::move を使う。

生徒の集団をunion-find木で管理し、集団に属する生徒についてクラスをキー、生徒数を値とする連想配列 std::map<Num, Num> で管理する。生徒aを含む集団と、生徒bを含む集団が新たに合流するときに、union-find木で管理する生徒の集合と、クラス-生徒数の連想配列もマージする。

このときこの連想配列を、union-find木の代表元(root, leader)に持たせ、代表元以外には持たせないようにする。そうすれば誰が連想配列を持っているか迷わなくて済む。union-find木をマージしたときに代表元が変わったら、以前の代表元が持っていた連想配列を新しい代表元に std::move する。

コードはこちら

まず原点に移動する。

原点に移動すれば式はすっきりする。公式解説通りの場合分け通りに実装したはずなのに、ついにACできなかった。

コードはこちら

確率DPと呼ばれる。

期待値の加法性から、分岐点のその先に行く確率を逐次的に求める。DPの更新式は条件付き確率そのもの(A,B,C枚あるときにA,B,Cを一枚引く確率はA:B:C)である。私の解法は出発点(A,B,C枚)から配るDP、公式解説は終着点(いずれかの硬貨が100枚)からメモ化再帰で実装している。

コードはこちら

TLE対策が必要

01-BFSで最短距離を求める、というのはすぐわかるのだが、ワープゾーンがあるマス同士を枝で結ぶとTLEする。ワープゾーンa..zという頂点を一つずつ、計26個作ればいいことは思いつく。しかし実際に実装するのが大変である。解説通り、普通のマスからワープゾーンに距離1、ワープゾーンから普通のマスは距離0にすると上手くいく。ワープゾーンへの距離を持たせて、枝を刈らないとTLEする。

BFSのループ内に上下左右の頂点、障害物と枠外には進めない、ワープゾーンの出入りと直接構成する必要がある。とにかく、ワープゾーンの出入りを枝で表現すると、TLE, RE, MLEとあらゆることが起きうる。

コードはこちら

半分全探索

半分全探索を完全に忘れていた。これは JOI 本選 2008Cとしてあまりにも有名である。 $N \leq 40$ を見たら、鉄則本の目次を眺めるとよいかもしれない。それと $N=1$ を特別扱いするには、空集合を解く時間の候補を0だけにする。

コードはこちら

問題文を制約に落とし込む。

赤いハンコが青いハンコに重なってはいけないが、赤いハンコを押す場所同士が重なってもいい。ということは以下の制約になる。

• 連続する白のマスの最小値が、赤いハンコの長さの最大値 $l$ になる
• 連続する白の $n$ マスに押す回数は、 $\lfloor l/n \rfloor$ である

コードはこちら

編集距離

題意は編集距離、またの名をレーベンシュタイン距離の定義そのものである。

• 削除はそのまま
• 要素を挿入するのは、他方の列から要素を削除するのと同じこと
• 編集後の要素の違いは、要素を置換するコストと同じ

レーベンシュタイン距離の求め方はこちら が参考になる。初期化と更新式を併せて10行程度で書ける。

コードはこちら

セグメント木を使う。

加法 + と同様に XOR もセグメント木に載せられる。自分で実装したセグメント木を使ったが、ACLを使ってもよい。

コードはこちら

絶対値があると上手く値をまとめられないので、絶対値を外す。

$A_i$ を昇順にソートしても、得られる結果は等しい。なぜなら以下が成り立つからだ。

• $i &lt; j$ かつ $A_i &lt; A_j$ ならソートしても $i &lt; j$ なので、 $i,j$ の相対的な位置は同じ。
• $i &lt; j$ かつ $A_i \geq A_j$ なら位置が入れ替わるのでソート前の $|A_j - A_i|$ を足すことに等しいが、絶対値なので値は変わらない

計算量を減らすために累積和を取りたい。要素の差だけに意味があるので、最小値を0にしても同じである。よって $min(A)$ を全部の $A_i$ から引いておく。これですべて非負の値になるので、 $(A_i - A_{i-1}) + (A_{i-1} - A_{i-2}) + ... (A_2 - A_1)$ は $i$ 番目までの累積和になる。

二重 $\sum$ における $j$ の寄与分は、 $(A_j - A_1) \times j$ の長方形を描くと分かる。この長方形の上辺から $A_j - A_1$ に下ろした長さの和が寄与分であり、つまり長方形の面積から $A_1..A_j$ の累積和を引いたものである。

コードはこちら

拡張ユークリッドの互除法

$S+K \times i=0 \quad mod \quad N$ つまり $K \times i=-S \quad mod \quad N$ すなわち $i=-S/K \quad mod \quad N$ を求めればよい。Nが素数ならフェルマーの小定理を使えるが、Nが素数でないときは拡張ユークリッド法を使う。拡張ユークリッド法を直接実装する必要はなく、実はACLを直接使ってよい。

より具体的には以下の通りである。

拡張ユークリッドの互除法を用いて、 $g=gcd(|A|,|B|)$ , $Ny - Kx = g$ なる $x,y$ を求める。 これを基に $Ny - Kx = S$ を満たす最小の正の $x$ と求める。

$S$ が $g$ で割り切れなければ玉座に座ることが永遠にできないので -1 を出力する。そうでなければ、 $Kx - Ny = g$ を満たすある $x$ が存在し、 $N((S/g)y) - K((S/g)x) = S$ である。 $(x,y)$ を一単位動かすということは $(K/g, N/g)$ 動かすことなので、 $(S/g)x$ を $N/g$ で割った余り ($x$ が負なら負の無限大方向にある $N/g$ の倍数に対する余り)が答えである。実装は こちら 。

こちらの 記事 の通り、中国余剰定理で 解く こともできる。

コードはこちら

$X,Y$ を問題文と逆に読んで、横方向を $X$ 、縦方向を $Y$ とする。また 0-based indexingにする。また座標 $X$ にある $Y$ の最小値を $U[X]$ とする(なければ $H$ )。

横方向に進んで上に行けるのは、 $(p,Y) = (p, 0)$ が出現するような $p$ (なければ $W$ ) 未満である。上方向に進んで横に行けるのは、 $(X,q) = (0, q)$ が出現するような $q$ (なければ $H$ ) 未満である。

$X &lt; p$ なら、横方向に進んで上に行ける。どれだけ行けるかというと、 $U[X]$ である。

縦方向に $0..W-1$ 進んで $(X,)$ にどれだけ行けるかというと、 $p+1$ 以上 $q$ 未満で、これまで出現したことのない $Y$ 座標である。出現した $Y$ 座標の数は、 $X$ を更新するごとにセグメント木に載せれば分かる。

コードはこちら

多数決は、得票数ではなく、得票数の差で考える。

得票差は全く演説しないときが最小(最も不利)である。得票数の差を増やす方法を考える。演説すると $A_i * 2 + B_i$ だけ得票数の差が埋まるので、この値が大きい順に演説し、得票差が正の値になったところで終わる。

コードはこちら

実装が大変

おおよその解法はすぐ思いついたが、110分掛かった。諦めない根性も必要である。まずデータ構造を示そう。

• 辺 $1..N-1$ の始終点 std::vector<std::pair<Num, Num>> abset
• 木をDFSして根から葉、左から右に頂点番号を振りなおしたID std::vector<Num> ids
• 頂点より根方向の部分木のうち、頂点番号を振りなおしたIDの最大値(葉なら0) std::vector<Num> max_id
• ID $[L,R]$ に $x$ を加算するという区間の集合 std::vector<std::tuple<Num, Num, Num>> spans
• 上記区間の集合から求めた、IDに対応する整数 std::vector<Num> score

解き方の概要を示す。

1. 木をDFSして根から葉、左から右に頂点番号を振りなおす。
2. クエリは abset を参照する。クエリ2は頂点a,bを逆に読み替えるだけなので std::swap すればよい
3. 頂点from に対応するID $id_{from}$ 、頂点to に対応するID $id_{to}$ があったとする。toがfromより根に近いつまり浅いなら、 $id_{from}$ > $id_{to}$ である。そのようにIDを振ったのである。このとき頂点fromの部分木にしか到達できない。IDでいうと、 $id_{from}$ 以上、部分木の最大頂点( max_id(from) から分かる)以下である。
4. fromがtoより根に近いつまり浅いなら。このとき頂点toの部分木には到達できない。よって到達可能な頂点は、 $id_{from}$ 以下、頂点toの部分木の最大頂点( max_id(to) )より番号の大きな頂点である。
5. クエリに対応して、頂点 $[L,R]$ に $x$ を加算するよう spans に積んでおく
6. すべてのクエリを読んだら、いもす法で区間の値 spans を統合して score にする。こうすると頂点IDに対応する値が求まる。
7. 最後に頂点 $1..N$ に対応するIDをキーとする値を出力する

fromがtoより根に近いつまり浅いときは、部分木に $-x$ を足して全体に $x$ 下駄を履かせれば実装が少し楽になる。常套手段らしい。

コードはこちら

いもす法を使う。

既述の通り時刻ごとのイベントを作り、同一時刻のイベントをまとめる。後はイベントを時刻順にみて、前のイベントからの期間について、1日あたりプライム料金を最大として支払えばよい。

コードはこちら

DAGである。

ということで、in-degreeが0の頂点から順番に最安値を伝搬すればいい。トポロジカルソートを使ったが、元々入力がトポロジカルソート済なのだからもっとすっきりした線形時間の実装があった。

コードはこちら

よくあるメモ化再帰である。2進数 $Y$ を作るために、シフトして1足すのを繰り返す回数は $log2(W)$ であり、この逆操作を考えれば $O(logY)$ の計算量で済みそうである。

$X \geq Y$ なら $X$ を引くことしかできないので、答えは $X - Y$ である。 $X &lt; Y$ なら、 $X, Y$ に $-1, 0, 1$ 足したものを初期値とし、足した数の絶対値をコストに加えてをメモ化再帰 $f(Y,X)$ を実行する。

以下 $X, Y$ は $-1, 0, 1$ 足した後とする。解の候補は $Y - X, f(Y,X), X - 1 + f(Y,1)$ の最小値である。 $f(Y,X)$ を定義する。エッジケースが多いので丁寧に網羅する。

• $Y = X$ なら0である
• $Y &lt; X$ なら $X - Y$ である

以下 $Y - X$ は解の候補である。それ以外の解の候補を挙げて、最小値が答えである。

• $Y,X$ ともに二のべき乗(立っているビットが1個)なら、 $log2(Y/X)$ も候補である
• $Y = 2$ なら、 $1 + f(1, X)$ も候補である
• $Y$ が偶数なら、 $1 + f(Y/2, X)$ も候補である
• $Y$ が奇数なら、 $1 + f(Y - 1, X)$ も候補である
• $Y \geq 5$ なら、 $1 + f(Y + 1, X)$ も候補である。これがないと2 WAsする

公式解説は直接 $Y$ を $X$ にしている。

コードはこちら

ランレングス圧縮を実装する。その上で、ビット操作の意味を考える。

• ビット操作のANDは、出力をTrueにしたいなら、入力をTrueにせよ、と捉える
• ビット操作のORは、入力がなんであれ、出力をTrueにしたいならそうできる、と捉える

$S_i$ がANDなら $x_i$ はTrueしか選択肢が無いので組み合わせの数には影響しない。ORの並びだけみる。連続するORつまりrunにおいて、 $pos$ 個目から $len$ 個ORが連続する場合、

• この run で $y_N$ をTrueにするので、それ以前の $y$ は何でもよい。組み合わせは $(2^{len-1}) * 2^{pos}$ 通り
• このrunではTrueにせず、それ以前の run でTrueにする。このrunについては全Falseの一通りで、組み合わせの数は以前のrunで決まる。

ので、後ろのrunから順に調べて組み合わせを加算していく。

コードはこちら

アフィン変換である。

座標に行列を掛けるとクエリに対する座標変換ができる。これをアフィン変換という。クエリに対応する行列を見ていく。

90度時計回り

$$\begin{pmatrix} 0 & 1 & 0 \\ -1 & 0 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix} $$

90度反時計回り

$$\begin{pmatrix} 0 & -1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix} $$

$x=p$ で上下反転

$$\begin{pmatrix} -1 & 0 & 2p \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix} $$

$y=p$ で上下反転

$$\begin{pmatrix} 1 & 0 & 0 \\ 0 & -1 & 2p \\ 0 & 0 & 1 \\ \end{pmatrix} $$

変換行列 $M_i$ があるとき、 $A_i$ 個目の操作を行った後の駒 $(x,y)$ の座標は $M_i * ... * M_1 * (x, y, 1)^{t}$ で求まる。行列を掛ける向きに注意する(最初に書ける行列が右端)。

コードはこちら

等差数列の公式を因数分解する。

等差数列の公式 $N=(n+1) \times n/2$ を逆に利用して $2 \times N=(n+1) \times n$ とし、 $N$ の約数から $n$ を列挙する。 $n$ を重複して数えないように注意する。約数の数はそれほど多くないので ($log2(N)$ を超えることは無い)、重複が心配なら std::set で集計する。

コードはこちら

典型を忘れていた。

$K$ の制約からDPでナップサック問題だとは思ったが、解き方を思い出せなかった。詰めたもの $S$ 、最後に詰めたもの $L$ を基に新たなものを付けてDPする。解くのに時間を掛けすぎたので、 $N$ と $K$ を取り違えて訳が分からなくなった。

コードはこちら

転倒数と言えばセグメント木

この問題は座標圧縮が要らないので Fenwick Tree でもよい。いずれにせよ $a_0..a_i$ を順にセグメント木に挿入する、つまりセグメント木の $a$ の値を1にすると、 $a_i$ が関係する転倒数は $a_i$ を挿入する直前のセグメント木における $a_i$ より大きな数の和である。

これで $k=0$ のときの転倒数 $sum_0$ が求まる。 $sum_0$ から $sum_1$ を作る方法を考える。これは $sum_0$ において $a_0$ が関係する転倒数を除いて(引いて)から、 $sum_1$ において $a_i$ が関係する転倒数を再測定して加算すると求まる。

コードはこちら

辺ではなく頂点に注目する。

辺に注目すると、凹の部分で上手く値が求まらなくなる。よって頂点が90度曲がる箇所を数える。ある点の周辺4マスについて、白黒のマスの数が1または3ならそこで辺が曲がるとわかる。

コードはこちら

浮動小数で簡単に解けると思ったら、精度に注意する。

X座標が求まればY座標は三角関数から求まるので、Y座標の上下限を引いて(両端が整数の場合に注意する)数える。のだが、浮動小数で実装すると丸め誤差が原因でWAする。問題文をよく読み返すと、

• $|X|,|Y|,|R| \leq 10^5$
• X,Y,R は高々小数第4位まで与えられる

なので、1+52ビット精度の浮動小数では精度が足りない。しかし64-bitではギリギリ精度が足りる。そのため浮動小数を固定小数(整数部x10000+浮動小数部)として扱う。これで10進数18桁(9桁の二乗)を誤差なく扱うことができる。

コードはこちら

久しぶりにダイクストラ法

それぞれの出発点について、ダイクストラ法を使って最短距離を求めればいい。多少工夫がいる。

• 同じ出発点から終着点への道路については、最短経路の道路だけ残して他は捨てる
• ダイクストラ法のキューは、初期状態で出発点の隣を積む。出発点を積むのではない。
• 距離の初期値は、出発点-出発点のループがあればその距離、そうでなければ無限大にする

公式解説では、道路の向きを反転して出発点に向かう距離を求めているが、上記の方法であれば道路を反転したグラフは作らなくてよい。

コードはこちら

答えが整数 $n$ ちょうどであることを確認するのは大変だが、答えが $n$ 以上または以下であることを確認するのは容易、という問題がある。そのときは二分探索すると求まる。

$n$ 進数と決め打ちして $M$ を表記可能かどうかは、実際に $n$ 進数で表記すればよい。 $n$ には単調性がある( $n$ を増やすと小さな数を表現できなくなる)ので、ある $n$ ではMを表記可能、 $n+1$ では表記不可能と解る。下限は $d+1$ なので、答えは $n-(d+1)$ である。

整数の二分探索は、素朴に実装すると区間が2以下のときに無限ループに陥りやすいので、パターンを確立する。

コードはこちら

ダイクストラ法である。

距離の定義を時刻にすれば、そのままダイクストラ法で解ける。BFSで最短距離を求めるときに優先度キューに追加情報を足すように、目的地と移動時間(いわゆる距離)の他に発車間隔をキューに載せればよい。

コードはこちら

$k = 1..N$ を全探索すればよいと分かる。 $k$ を固定して、 $DP[i=1..N][j=0..N][r=0..(k-1)]$ を、 $i$ 個番目までの素材を見て、 $j$ 種類合成したときに、合計値を $k$ で割った余りが $r$ になるような魔力の合計の最大値とする。 $DP[][][] = -\infty$ , $DP[0][0][0]$ としてDPする。

$(X - DP[N][k][X mod k]) mod k$ の最大値が答えである。 $DP[N][k][X mod k]$ が $X$ より大きいときと $-\infty$ のときは値が無いので注意する。

コードはこちら

条件付き確率の定義そのものである。ある数字が表に書かれたカードで出尽くした場合を考慮する。

コードはこちら

確率の加法性から明らか。

コードはこちら

Binary Indexed Tree (Fenwick Tree) を使ってみた。あるいは縦の物を横にする。

公式解説によれば $O(N)$ 解法がある。だが $O(N*log(N))$ は容認されるので、 $1..k$ が連続して出現する要素をBITで管理して、この $k$ を二分探索すると求まる。セグメント木を使うとTLEする。注意点として、BITに $A_i$ があるかないか(1か0か)を載せるので同じ数を何個載せたかは別途管理することと、BITに0を載せられないので(1-based indexing)、0は特別扱いする必要がある。

$O(N)$ 解法は縦の物を横にする、つまりmexになりうる数は連続するM個の中に出ないことを、 $A_i$ の位置から求める。

コードはこちら

$N, M, Q$ が小さいのでgreedyでいけそう。

実際価値が大きい荷物を、その荷物が入る最小の箱に収めればよい。そうでなくて、同じ価値のものをもっと大きな箱に入れるのも、同じ大きさに価値が低い荷物に入れるのも意味がない(交換すればいい)。クエリ間に依存関係はなく、 std::multiset で箱を管理して荷物の入った箱を取り除けばいい。

コードはこちら

逆から考える。以下すべて演算を $mod7$ で考える。

最初に状態遷移表を作る。 $10P + S = Q$ を、数 $P$ を10倍して一番下の桁を $S$ にしたら $Q$ になる、ということを求める。この逆引きとして、 $S$ を与えて $Q$ になるとき元は $P$ だった、という表 $R[S,Q]$ を作る。この変換は一対一対応なので逆引きを作ることができる。

操作を逆から考え、初期状態を高橋君が $T = 0$ であるとする。ここから逆引きを考える。

• $X_N$ が高橋君の手番なら、一手前は $R[0,0]$ または $R[S_N,0]$ のいずれかであってほしい
• $X_N$ が青木君の手番なら、一手前は $R[0,1..6]$ または $R[S_N,1..6]$ のいずれかであってほしい

これを一般化する。状態を定義する。

• $Prev$ は、前が高橋君の手番なら $true$ 、青木君の手番なら $false$ とする
• $Current$ は、今が高橋君の手番なら $true$ 、青木君の手番なら $false$ とする
• $U \subseteq {0..6}$ は、前が高橋君の手番なら高橋君にとっての最善手の集合、前が青木君の手番なら高橋君にとっての最善手の集合とする

状態遷移は、 $Prev = Current$ なら、最善手を選ぶので $U$ の逆引き先 $P =\bigcup_{d \in {0,S}, j \in U} R[d,j]$ である。 $Prev \ne Current$ なら、相手が選ばない手を選ぶので $P$ の補集合 $\bar{P}$ である。このように $P$ または $\bar{P}$ を $U$ に置き換える。

$A_1$ が青木君で $P$ が0を含む、または $A_1$ が高橋君で $P$ が0を含まない、のいずれかが成り立てば青木君の勝ちである。そうでなければ高橋君の勝ちである。

公式解説と同じバックトラッキングであるが、公式解説の方がすっきり表現している。

コードはこちら

C++の力でごり押してしまった。

半畳の間に境界線を引く/引かない、つまり半畳をまとめる/まとめないをビット全探索すると、C++実装なら2秒を切るのでACできる。境界線の内側の領域(半畳がつながったものを)をunion-find木で管理する。以下の通り全探索する。

• 最初は各半畳が孤立した領域とする
• 境界線を引くなら領域をmergeする
• 領域の大きさが2(一畳)を超えたらその場で打ち切る
• 打ち切らずに一通り境界線を引く/引かないを終えたら、一畳がA枚、半畳がB枚あるかどうか数える

解説通りに畳の配置でDFSすると9ミリ秒で解ける。私のコードはこちら

コードはこちら

逆再生すればわかる。

$f_N(...(f_1(x))) = g(x)$ と置く。元々の出力値は $(-\infty, \infty)$ だったものを、 $f_N(x)$ によって取りうる値が狭まると考える。これを順に考えて、 $f_1(x)$ によって取りうる値で狭めると、 $x$ の定義域 $[L,R]$ が求まる。直感的に $g(x)$ は、

• $g(x) = g(L) : x \leq L$
• $g(x) = g(L) + x - L : L &lt; x &lt; R$
• $g(x) = g(R) : x \geq R$

と予想できる。なので $L,R$ を求め、 $g(L), g(R)$ を求めれば、 $x_{1..N}$ について答えが $O(N)$ で求まる。

そこで $L,R$ を求める。クエリを $i=N..1$ の順に再生する。

• $t = 1$ なら $L$ を $L - a_i$ , $R$ を $R - a_i$ に置き換える
• $t = 2$ なら $L$ を $max(L, a_i)$ , $R$ を $max(R, a_i)$ に置き換える
• $t = 3$ なら $L$ を $min(R, a_i)$ , $R$ を $min(R, a_i)$ に置き換える

厳密な証明は公式解説2にある。

コードはこちら

$N$ が小さいので全探索する。

コードはこちら

ベクトルを回転させれば求まる。

コードはこちら

えいやっとDP

同じ色のボールを回収するなら、右端のボールまで行って左端のボールまで回収するか、左端のボールまで行って右端のボールまで回収するか、どちらかにすればいい。左端か右端以外の場所で止まる意味は無い(次の色になってから動けば済むことなので)。

ここで今の色の左端と右端、次の色の左端と右端を組み合わせてDFSするとTLEする。そこでDPできないかと考える。つまり $DP[i][2]$ を、 $i$ 番目の色を回収して、左端または右端のボールを回収した時点の移動距離、とする。これでACできるが、証明が分からない。

コードはこちら

問題文をよく読む。

文字が同じなら入る数字も同じ、というのは分かる。しかし数字が同じなら文字も同じ、ということは問題文をよく読むと解る。後者の制約のおかげで随分簡単な問題になる。

まず文字が11種類以上あるときは解けない。文字が10種類以下なら総当たりでよい。文字が $n$ 種類あるとき、 $0..9$ から数字を $n$ 個取り出し、取り出した数字の順列組み合わせを文字に当てはめて総当たりする。文字の順序は、総当たり中に変わらなければ何でもいい。

$0..9$ から $n$ 個取り出す方法は、 $0..01..1$ という風に $0$ を $10-n$ 個、 $1$ を $n$ 個並べた配列を初期値として、 std::next_permutation すれば $0..9$ を取り出すか否かが分かる。

コードはこちら

$N=10^5$ ならDFSできる。

なので木を頂点1からDFSして、途中にある色を数えればいい。木なので葉に向かうときに経由した頂点の色を加え、根に向かうときに頂点の色を除く。

コードはこちら

解説を読んでも解けないのが青diff

連結成分に分解してそれぞれ解く、DFSでたどるのは分かったが、入力例1を解くことができずに諦めた。単に頂点の色を決め打ちして進むと、入力例1の右回りと左回りで同じ塗分けを重複して数えてしまう。DFSで頂点をたどる方法を固定すれば、重複せずに数えられる。

DFSで頂点をたどる順序を求めて頂点を追加すると、根が最初、深い場所が後になる。このとき追加順つまり根を最初に、深い場所を最後たどる必要がある。そうしないとTLEする。うっかり逆にしたためにTLEがなかなか取れなくて苦労したが、この難易度が青diffである。

コードはこちら

たまには青diffも早く解ける。

C++ならビット全探索でも通るだろうと思って計算量を気にしなかったら、1722 msで通ってしまった。

次のようなDPを考える。 $DP[i][S]$ は、 $i = 0..N$ 個の数字集合 $S$ を使う組み合わせの数とする。 $DP[][] = 0, DP[0][\emptyset] = 1$ とする。

$i$ 番目の要素として、 $S$ に $j = 1..N$ を追加することを考える。 $S$ に $j$ が含まれていたら追加できない。追加したとして、 $S$ が制約 $X = i, Y, Z$ を満たさないものは追加できない。追加できたら $DP[i][S \cup j]$ に $DP[i-1][S]$ を足す。

$DP[N][]$ の総和が答えである。

コードはこちら

鳩の巣原理。

鳩の巣原理であっさり解ける。こういう発想も重要である。定石通りDFSと再帰で求めてもいいが、パスを保存しながらエッジケースを実装するのが難しい。コードはこちら。