Atcoder

提出コード 縦方向、横方向にそれぞれどれだけ移動する必要があるか。 縦方向 単純に下に行くだけなので$k$回の移動となる。 横方向 $a_x$を、マス$x$まで移動したときに元々どこからきたのかという情報とする。 つまり、1段目の$a_x$からスタートして、$k$段目の$x$まで移動したということになる。 各$k$ごとに、移動できない領域のいずれかのマスからスタートして、$b_i+1$に移動すると考えればよい。 答えは、$\underset{x}{min} (x-a_x) + k$となる。 以下は、入力例1における$a_x$の遷移を図示したもの。

提出コード 解説放送を見て道筋は理解できたが、そこからが長かった。 比較的実装が重い問題だと思う。 答えの回文LRを文字列Lと文字列Rに分けて考える。どちらも空文字列で初期化しておく。 $s_i$を追加するときは、Lの右側に追加するか、あるいはRの左側に追加する。 何度か$s_i$を追加して、L="abcde"、R="cba" となったとする。 このとき部分文字列 abc はすでに回文の条件を満たすのでL="abc"、R=""と見なしてもよいということになる。 なので、LとRの組 (L, R) を頂点として、ダイクストラ法を適用していけばよい。 LやRとして現れるのは$s_i$のPrefixとSuffixのみなので、今回の制約では十分間に合う。 頂点 (L, R) からの遷移については、すべての$s_i$について、$s_i$をLあるいはRに追加したときに部分的に回文の条件を満たすかどうかをチェックする。条件を満たす場合には、次の頂点に遷移できる。

提出コード 赤diffだった。問題文を読むと手を付けれそうな気がしたけど、そんなに簡単じゃなかった。 まず、$O(N^3)$のDPを考えて、それをもとに計算量を削減していくというアプローチを取る。 $i = 2, 5, 8, 11, \dots$ のように3文字おきに見ていく。 dp[i][x][y]を$i$番目まで見たとき、直前の2つの文字が$x$、$y$であるときの最大スコアとする。 a = v[i], b = v[i+1], c = v[i+2] として、パターン分けしていく。 スコア +1となる場合。どの3つでスコアを増やすか考える。 A) $a = b = c$ の場合、すべての$(x, y)$の組について dp[i+3][x][y] <= dp[x][y] となるので、代わりに答えに+1しておく。$O(1)$ B) $a = b = x$の場合、すべての$y$について dp[i+3][c][y] <= max(dp[i][a][*]) + 1 とする。$O(N)$ C) $a = x = y$の場合、dp[i+3][b][c] <= dp[i][a][a] + 1とする。$O(N)$ スコア +1とならない場合。どの2つを残すか考える。 D) $x$、$y$ を残す場合、dp[i+3][x][y] <= dp[i][x][y]なので何もしない。$O(1)$ E) $x$、$a$ を残す場合、すべての$x$について dp[i+3][x][a] <= dp[i][x][*]とする。$O(N)$ ...

提出したコード 木において「連結成分の数 = 頂点数 - 辺の数」で求められることに注目する。 直感的に、頂点が増えると連結成分の数が1増え、辺の数が増えると連結成分の数が1減るという感じで理解できる。 $f(L, R)$もこれで求められる。 $$ \begin{aligned} &f(L, R) \\ &= 区間[L \ R]に含まれる点の数 \\ &- 両端が区間[L \ R]に含まれる辺の数 \\ \end{aligned} $$ これをLとRの全通りで求めて総和をとればよい。 頂点数と辺の数はそれぞれ独立に求めていけばよい。 $$ \begin{aligned} &\sum_{L,R} f(L,R) \\ &= \sum_{L,R} 区間[L \ R]に含まれる頂点の数 \\ &- \sum_{L,R} 両端が区間[L \ R]に含まれる辺の数 \\ &= V - E \end{aligned} $$ 以下のように図示してみると、ある頂点$i$は全体で$(i+1)(N-i)$回現れるので、すべての$i$でこれの総和を取って$V$とすればよい。 同様にある辺$(u, v)$は全体で$(u+1)(N-v)$回現れるので、すべての辺について総和を取って$E$とする。 $V-E$が答えとなる。

提出したコード コンテスト後追加されたテストケース after_contest01.txt でコケた。 それ以外は自力で通ったので考察の詰めが甘かった。 まず、（A）答えが負となる場合と（B）答えが非負となる場合で場合分けをする。 （A）の場合には、絶対値の小さい順に貪欲にとればよい。（B）の場合を考えていく。まず、キューを2つ用意しておく。 非負な値を降順にソートしたもの（例：9 6 5 2 1 0 0） 負な値を昇順にソートしたもの（例：-8 -7 -3 2） 単純に、負数同士の積は正という性質を使う。 $K$が2個以上残っている場合には、2つのキューからそれぞれ2つの値を取り出して、大小比較をする。 例えば、$9 \cdot 6 = 54 < -8 \cdot -7 = 56$ であれば、負数のキューから2つ値を取り出せばよい。 一方で、非負なキューのほうが大きい場合には、非負のキューから1つ値を取り出せばよい。 繰り返しになるが、非負なキューから取り出す場合には、1つの値だけでよいことに注意する。 https://twitter.com/shirakia/status/1279773457413074944で例が言及されている。after_contest01.txtもこのケースに該当しそう。 そのあとは、非負なキューからとる場合は1つずつ、負なキューからとる場合は2つずつのペアとして、取り出していけばよい。 （B）の計算途中で、どうしても答えを正数にすることができない場合には、（A）の結果を答えとする。

提出したコード 前提知識として、Nimというゲームであることを知っておくと良い。Nimには必勝法があり、すべての山の石の数 $A_i$ についてXORをとり、その結果が0以外であれば、その手番の人が最適な動きを取れば必ず勝つ。 必勝状態であるXOR != 0で手番が回ってきたとき、ある山からある数の石をうまく取り除くと、XOR = 0の状態に遷移できる。 逆に、XOR = 0の状態からは、どんな選び方をしても、必ずXOR != 0 の状態（必勝状態）に遷移してしまう。 ターンの経過に伴って石の数の合計は減っていくので、必ずゲームは終わる。 Grundy数というらしい。 これをふまえて、考察を進める。「1番目の山から0個以上$A_1$個未満の石を2番目の山に移すことで …」とあるので、先頭二つの山についてのみ考えればよいことがわかる。なので、これ以降$A=A_1$、$B=A_2$、$X = A_3 \oplus A_4 \oplus \cdots \oplus A_N$とする。また、“移す"という操作を$A$を$a$、$B$を$b$に変更すると言い換える。そうすると、以下の条件を満たしつつ、できるだけ$a$を大きくすればよい（“移す"石の数が最小）ということになる。 $$ a + b = A + B = S \ a \oplus b = X \ 1 \leq a \leq A \ $$ これは桁DPによって解くことができる。$dp_{i,j,k}$を、下から$i$桁目まで見たときの$a$の最大値とする。 ただし、一つ上の桁に対して繰り上がりがある場合は$j=1$、$i$桁目まで見たときに$a$が$A$を上回っていれば$k=1$とする。 50桁くらいまで見れば十分。 提出コードにコメントをつけておく。初期値は以下の通り。 rep(a, 2) { ull b = a ^ (X & 1); // b は a から決まる ull carry = a & b; ull _sum = a ^ b; if (_sum != (S & 1)) continue; // そもそも合計がS出なければスキップ ull over = a > (A & 1); chmax(dp[0][carry][over], a); } dp[i][j][k]からの遷移は以下の通り。配るDPなので i + 1 桁目について見ていく。 ...

提出したコード 解説を漁ってみると、どうやらアルファベットを適当に$K$回挿入したあとの 長さ$N+K$の文字列の中で、$S$の各文字の位置が固定されていると考えればうまくいくということだった。 そう考えると、あとは長さ$N+K$の文字列で$K$文字をどうやって挿入していくかだけを考えれば良い。 入力例1を使って考える。 S = “oof” N = len(“oof”) = 3 K = 5 例えば、位置1に’o’、位置3に’o’、位置5に’f’をおいてみる。 また、長さ$N+K$の文字列を先頭から見たときに"oof"がはじめて登場するのがこれらの位置ということにする（条件1）。 このとき、位置0には’o’以外の25種のアルファベットを挿入できる。 逆に、位置0に’o’を挿入するのは、条件1を満たさないのでダメ。 同様にして、位置2にも’o’以外の25種のアルファベットを挿入できる。 また、位置4にも’f’以外の25種のアルファベットを挿入できる。 位置6と7に関しては、特に制約がないので、26種のアルファベットを挿入できる。 まとめると、‘f’の位置$j$が$N-1 … N+K-1$まで移動したとき、 2つの’o’が取れる位置の組み合わせは${}_j C _{N-1}$ となる。 また、25種のアルファベットを挿入する位置は$j - (N-1) $個、 26種のアルファベットを挿入する位置は$(N+K-1)$個、となる。 つまり答えは$\sum_{j=N-1}^{N+K-1} {}_j C _{N-1} \cdot 25^{j-(N-1)} \cdot 26^{(N+K-1)-j}$となる。

提出したコード 解いた後の振り返りが大事だと思う。 2次元平面上で、スタート位置からゴール位置までの最短経路を求める。 ただし、平面上にはいくつかブロックがあり、そのセルは通れない。 さらに、一回の移動で、同一方向に$1 … K$の任意の個数のセルを進めることができる。 頂点は$(y, x, dir)$として、グラフを考えて、ダイクストラ法で最短経路を算出すればよい。 頂点$(y, x, dir)$からの遷移は以下の通り。 移動にかかるコストを$K$倍して考えるとよい。 方向を変えるときは、$K$で切り上げ。 $cost(y, x, new dir) \leftarrow ((cost(y, x, dir) + K -1) / K) * K$ 同方向に移動。$dir$は上下左右の4種類。$dx$、$dy$は方向ごとの差分。 $cost(y + dy, x + dx, dir) \leftarrow cost(y, x, dir) + 1$ 計算量は$O(HW log(HW))$かな。

EDPC を全部埋めた。 雑多なメモなので、きれいに解法をまとめたものではない。 W - intervals $dp_i$ を、いくつかのビットに1が立っているとき、最も右側にある1が$i$であるときの最終スコアとする。 ここで、$dp_i$は$ max_{j=0 … i-1} dp_j$ と $i$ 文字目を1にしたときに得られるスコアの和で求められる。 $block_i$を右端$r$が$i$であるブロックの集合として、 $dp_i$を計算する際に、 $i$文字目を1にしたときに得られるスコアとして $block_i$ を足しこむ。 $block_i$ は $i$ 未満の $dp$ にも影響するため、遅延セグメントツリーを使って、 影響する $dp$ に区間加算を行う。 最終的な答えは $max_{i=0 … N} dp_i$ となる。 はじめて、遅延セグメントツリーを使った。復習しておく。 Z - Frog 3 $dp_i$ を足場 $i$ に到達するまでの最小コストする。 初期値は $dp_0 = 0$。 まずは素直にDPの更新式を作ると以下のようになる。 $$ \begin{aligned} dp_i &= min_{j=0 … i-1} (dp_j + (h_j - h_i)^2 + C) \\ &= min_{j=0 … i-1} (dp_j + h_j^2 - 2 h_i h_j + h_i^2 + C) \\ &= min_{j=0 … i-1} (-2 h_i h_j + dp_j + h_j^2) + h_i^2 + C \\ \end{aligned} $$ ...

ABC #139 D - ModSum $p_1=N, p_2=1, p_3=2, … , p_N=N-1$ とすると、$m_1=0, m_2=1, m_3=2, … , m_N=N-1$ となる。 なので、答えは$1, 2, 3, …, N-1$の総和。 ABC #139 E - League $i$と$j$の試合を頂点$(i,j)$と表す。ただし、$i$と$j$をひっくり返したものは同一視する。 各頂点は、直前にすべき試合数$prev_{(i,j)}$と、その次に実行可能な試合の一覧$next_{(i,j)}$をもつ。 そして、$prev_{(i,j)} = 0$である試合を見つけるたびに、貪欲にその試合をしていくよう、シミュレーションする。 ここで、ある試合をするたびに、その次の頂点の$prev_{(p,q)}$をデクリメントすることに注意する。 ABC #139 F - Engines あらかじめ各ベクトルを偏角ソートしておき、 720度分になるようにそのベクトルをつなげておく（後々、楽になる）。 そうすると、この問題の答えは、連続したベクトルの和であることが分かる。 すべてのベクトルについて、以下の操作を行う。 あるベクトルを始まりとして、連続したベクトルを足していき、長さが最長となるものを見つける。 ABC #140 D - Fce Produces Unhappiness まず、幸福でない人に注目して、それをどれだけ減らせるかに注目する。 たとえば、$RLLLLRRRRRLLRRLLRRR$から幸福でない人を抜きだすと、$RL…….RL..RL…R$となる。 連続する人は同時に操作できるので、$RLRLRLR$と考えてよい。 そして、$RLRLRLR$ -> $RLRLR$ -> $RLR$ -> $RR$ -> （空）のように操作を繰り返せば良い。 ABC #140 E - Second Sum Nから1まで、順番に見ていく。 ある要素$i$について見た時、左右には$i+1, i+2, … , N$の要素が置かれていることになる。 右側に最大値がある場合と、左側に最大値がある場合、それぞれについて、組み合わせを計算して、 合算すればよい。最大値の位置については、setのlower_boundで見つけた。 ...

いくつかABCの問題を解いたけど、ブログに記録するのを忘れていた。 まとめて書いておく。 ABC #136 D - Gathering Children 一度RLの組に入ると抜け出せない。 偶数距離を移動させて、RLの組にくっ付ける。 ABC #136 E - Max GCD ソートしておいて、小さい値は0に、大きい値は答え$d$に近づける。 前と後の両方向から、累積和を求めておく。 ABC #136 F - Enclosed Points ある点$x$がふくまれるような矩形の数は、その上下左右の4つの領域からそれぞれいくつの点を選ぶかによって計算できる。領域ごとに含まれる点の数を$A, B, C, D$とする。 点$x$を含まない場合は、それぞれの領域から点を取るかどうかで16個に場合分けして考える 点$x$を含む場合は単純に$ABCD$ 領域ごとの点数の算出には、平面走査を使う。また、事前に座標は圧縮しておく必要がある。 ABC #137 D - Summer Vacation アルバイトはどれも一日で終るためコストは変わらず、単純に支払日だけが異なるだけ。 アルバイトを報酬の大きい順に見ていって、できるだけ後ろの日程から埋めていく。 ABC #137 E - Coins Respawn まず、DFSを使って、始点と終点どちらからも到達可能な頂点の集合$S$を求める。 あとはコストに$-1$を掛けて、ベルマンフォード法を適用して、最長経路を求める。 もし、集合$S$内の頂点が、閉路に含まれていたら、$-1$を返す。 単純に、ベルマンフォード法で閉路を見つけるだけでは不十分なことに注意する。 ABC #137 F - Polynomial Construction フェルマーの小定理を使う。頻出テクニックだと思うので、復習しておきたい。 $a = {0,0,…,0}$の$i$番目を1にした$a’ = {0,0,..,1,…,0}$を考える。 そうすると、$a$を使った$f$と、$a’$を使った$f’$は以下のような関係になる。 これをすべての1が立っている$i$について、計算すればよい。 $$ f’(x) = f(x) + (1- (x-i)^{P-1}) $$ ...

今回はE問題がかなり難しかった。F問題より難しく感じた。 Youtubeの解説放送を聞いて、やっとわかってきた。 自分用のメモなので、日本語が雑になっている。。 ABC #135 D - Digits Parade dp[i][j]をi桁目まで見た時に、あまりがjとなる場合の数として、求めていく。 ABC #135 E - Golf 事前に、X>=0,Y>=0にしておく 1) X+Yが奇数 かつ Kが偶数 -1を返す。 どうやっても奇数番地にはたどり着けない 2) X+Y>K n=ceil(X+Y/K)として、X+Y と nK の偶奇が異ればn++とする。余剰 nK-X-Y のために、冗長な経路を作る。 ここで、X=0 だと、序盤の移動において、マンハッタン距離が正しくないので、swap(X,Y)しておく（もちろん出力時には戻す）。 +(X,Y) | Y (0,0)+ - t | | t = (nK-X-Y)/2 |-----| X 3)X+Y<K 3-1) X+Yが偶数 n=2となる。それ以降の計算は、2) と同じ。 +(X,Y) | Y (0,0)+ - t | | t = (2K-X-Y)/2 |-----| X 3-2) X+Yが奇数（ 1) の条件よりKも奇数） n=3になる。これは思いつかない。この場合のみ、X, Y両方向に冗長な経路を取る必要がある。 ...

前回の続き。Atcoder Beginner Contest #130 ~ #133を解いたので、まとめておく。 まだまだ解説なしでは解けない。。 ABC #130 F - Minimum Bounding Box dp[i][j]をi,j番目が部分共通文字列となるときの組み合わせ数とする。 更新式もメモ化しておくと高速に計算できる。 ABC #131 F - Must Be Rectangular! (x,y)座標を2部グラフとみなす。 グラフに置き換えて考えることでスムーズに解ける。 ABC #132 F - Small Products N/xが同じ値になるxを同じグループとみなして、グループごとに計算を進める。 DPを圧縮していくイメージ。 ABC #133 F - Colorful Tree 木構造の頂点間の距離はLCA（最小共通祖先）を使うことで求めることができる。 実装解説は蟻本にまとまっている。 あらかじめクエリを先読みしておき、必要な頂点と色を抽出しておく。 DFSしつつ必要な値を埋めていく。

Atcoder Beginner Contest #116 ~ #129のCD問題をすべて解いた。 また、#126 ~ #129についてはEF問題が追加されているので、すべて解いた。 F問題は、解説PDF、解説Youtube、解説ブログを参考にした。 ABC #126 F - XOR Matching https://atcoder.jp/contests/abc126/submissions/5909511 M=3とすると、長さ2^(M+1)の数列は、{0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7}のような要素をもつ。 このとき、{<0,1,...,7からKを除いた昇順の数列> K <7,6,...,0>からKを除いた降順の数列 K}とすれば良い。 K以外の要素について：間にはKだけが残ることになるので、条件を満す Kについて：間には <7,6,...,0>からKを除いた降順の数列 が残る。XORをとるとKになるので条件を満たす。 ABC #127 F - Absolute Minima https://atcoder.jp/contests/abc127/submissions/5930963 中央値が最小値となる性質を利用する。中央値が２つあるときには、左側を採用する。 中央値は、小さいほうと大きいほうをそれぞれ優先度付きキューで管理すると便利。 解説動画では、同一のaを二度入れてキュー間で交換するテクニックを使っていたが、 ナイーブに一度だけ入れる方法でも問題ない。 キューが片方に偏らないように、整理する必要がある。 更新クエリのとき、aが最小値を取る区間のなかに含まれていれば、最小値の更新はない。 一方、含まれていなければ、最小値を取る区間のなかで、最も近い点との差分を、最小値に追加する。 ABC #128 F - Frog Jump https://atcoder.jp/contests/abc128/submissions/5921198 A、Bをそのまま扱うのではなく、C=A-B と k=何度戻りが発生するか という変数に置き換えて考える。 Cを固定すると、kが増えるにつれて、蓮を多く踏めるようになる。 同一の蓮を二度以上通るかどうかは、単純にsetで管理した。 ABC #129 F - Takahashi’s Basics in Education and Learning https://atcoder.jp/contests/abc129/submissions/5945816 難しかった。まず、等差数列の各要素が何桁なのかによって、分割する。たとえば、A=3、B=4であれば、3,7と11,15,19に分けて考える。分割後は、sum_i=0^(l-1) (A+Bi)*10^k^(l-i-1)を求めることになる。 A sum_i=0^(l-1) 10^k^iとB sum_i=0^(l-1) i*10^k^(l-i-1)にわけて、計算する。 どちらも漸化式に変換して解く（コード中のf,gに対応）。 解説動画を見るのがおすすめ。 ...

Atcoder Beginner Contest #1 ~ #115 の CD 問題をすべて解いた。 C問題は7割くらい、D問題は半分くらい自分の力で解くことができた。 特殊なアルゴリズムを使うことはあまりなく、ちゃんと考察できれば、解けるんじゃないかなと思う。 役立ちそうなことを残しておく。 Example の最初の1~2個は手で解いてみる。特に、幾何の問題は実際に書いてみる。 複数のパラメータを総当たりするときはどちらか一方のパラメータを固定して考える。 あらかじめソートや累積和を計算しておく。 その他、Youtube の解説動画が充実していて、かなり助けになった。

ちょっと競技プロをやってみた． Codeforces #308 (Div.2) Codeforcesに初参加． 結局A-Eの5問中，Aしか解けなかった． Aは，実装するだけという感じだったので，そんなに時間がかからず解けた． Bは，ヒストグラムを作れば解けたと思うが，それに気づくのが遅かった． Cは，4番目のpretestで失敗． D,Eは手を付けてない． それと，pretestに失敗した時は，「My contest submissions」から テストケースの詳細が見れるのを知らなかった． ARC040 4問中3問解けた． 問題DはDPかなんかで計算量下げるんだろうなと思ったが， 全探索以外の手法が思いつかず終了． 精進します．