Kotlin Heroes: Episode 12

• https://codeforces.com/contest/2087

Kotlin Heroes はコンテストには参加せず，C++ や Python で書いたコードを chatgpt に変換してもらうことで AC しています．コンテスト中にこれをやるのはルール違反なはず．

A. Password Generator

$a$ 個の digit，$b$ 個の大文字，$c$ 個の小文字をこの順に並べます．偶奇で $2$ 種の文字を使い分けます．

• https://codeforces.com/contest/2087/submission/314435953

B. Showmatch

ソートして順に組む方法が条件を満たすかどうかを確認します．

• https://codeforces.com/contest/2087/submission/314436260

C. Coin Game

$3$ 種の個数を求めて min, max の和です．個数は累積和テーブルから求めます．

• https://codeforces.com/contest/2087/submission/314436511

D. Uppercase or Lowercase?

先頭の文字列を聞いて，その先頭の文字によって小文字優先・大文字優先を判別します．あとは単に二分探索です．

• https://codeforces.com/contest/2087/submission/314436874

E. Color the Arrows

選べる部分列の必要条件として，次のどちらかが成り立ちます：左端が右向き，右端が左向き．これは各時点でそうであることが帰納的に確かめられるからです．

これは十分条件でもあります．左端が右向きのとき，右側にある左向きを右から順に消費していき，そのあと右向きを順に消費していけばよいです．

端となる文字を固定し，残りの部分は $max(c,0)$ でとっていくというパターンを計算すればよいです．

• https://codeforces.com/contest/2087/submission/314437388

F. Weapon Upgrade

何日目，攻撃力1，攻撃力2 の 3 つ組をキーとして dp をします．最小被ダメージを dp の値とします．

攻撃力の和が今まで撃破した総数を表すので，食らうダメージ数はここから分かります．またその攻撃力で倒せる相手の数もこの情報から分かるので，必要なことは全て計算可能になっています．

• https://codeforces.com/contest/2087/submission/314438935

G. Esports in Berland

これ（https://atcoder.jp/contests/jag2014summer-day4/tasks/icpc2014summer_day4_d）が似ていると思います．これの私のユーザー解説の真似をします．

$\mathrm{dp}[i][j]$ を日付，スキルに対する dp テーブルとします．遷移は次の通り．

• $\mathrm{dp}[i+1][j]=max(\mathrm{dp}[i][j-1],\mathrm{dp}[i][j]+a_i+j)$．

変数変換していきます．

• ${\mathrm{dp}}_1[i][j]:=\mathrm{dp}[i][j]-S_i$ とすると ${\mathrm{dp}}_1[i+1][j]=max({\mathrm{dp}}_1[i][j-1]-a_i,{\mathrm{dp}}_1[i][j]+j)$．
• ${\mathrm{dp}}_2[i][j]:={\mathrm{dp}}_1[i][j]-ij$ とすると ${\mathrm{dp}}_2[i+1][j]=max({\mathrm{dp}}_2[i][j-1]-(i+a_i)-j,{\mathrm{dp}}_2[i][j])$．
• ${\mathrm{dp}}_3[i][j]:={\mathrm{dp}}_2[i][j]+(\genfrac{}{}{0ex}{}{j+1}{2})$ とすると ${\mathrm{dp}}_3[i+1][j]=max({\mathrm{dp}}_3[i][j-1]-(i+a_i),{\mathrm{dp}}_3[i][j])$．

$j$ を固定したときに $\mathrm{dp}[N][j]$ 最大化のためには ${\mathrm{dp}}_3[N][j]$ を最大化すればよく，そのためには $i+a_i$ が小さいものを優先してスキルアップにあてればよいことが分かります．

• https://codeforces.com/contest/2087/submission/314442767

H. Nim with Special Numbers

$k$ 個の山がありますがこれらはゲーム和の形なので，ひとつの山に対する grundy 数を求めればよいです．

$S$ のところで区切りがあり，区切りの間では「山 $0$ 個の場合の grundy 数だけが違う NIM」があります．すると石の個数に対する grundy 数は，例えば次のようになります：$[5,0,1,2,3,4,6,7,8,\dots ]$．

区切りの位置を固定して，左端での grundy 数を入力と見なしたとき，左端の grundy 数から右端の grundy 数を与える規則は $x⟼\{\begin{array}{ll}n& (x<n)\\ n-1& (n\leqq x)\end{array}$ という関数になります．

これを少し拡張して，$x\mapsto \{\begin{array}{ll}b& (x<a)\\ c& (a\leqq x)\end{array}$ という形の関数を考えるとこれは合成について閉じており，セグメント木で扱うことができます．これで区切り位置での grundy 数が取得できるようになって，そこから任意の点での grundy 数も取得できます．

• https://codeforces.com/contest/2087/submission/314916883

I. Hamiltonian Partition

ひとつのサイクルに同時に採用できる辺集合は，各頂点での入次数・出次数がともに $1$ 以下であるようなものです．入力が DAG なのでこのような選び方で出来るのはパスの集合で，これをつないでサイクルを作れます．

すると，頂点を倍化して二部グラフを作ったとき，ひとつのサイクルに同時に採用できる辺集合はマッチングになります．辺集合をマッチングに分解するというのは辺彩色です．

• https://judge.yosupo.jp/problem/bipartite_edge_coloring

二部グラフ辺彩色は頂点数の色数で可能で，それが最適解を与えます．辺彩色は $O(m\log m)$ 時間の手法なども存在しますが，実装要求量が多いです．Kotlin 要求下での実装が必要なので，交代パスを使った $O(NM)$ 時間の方法（資料）を実装しました．

• https://codeforces.com/contest/2087/submission/314960494