日立コン2020 C - ThREE (600)
問題：C - ThREE
解法：piとpjの和または積が3の倍数であることは、「pi, pjが1 (mod 3), 2(mod 3)のそれぞれどちらか」または「pi, pjのどちらかが0 (mod 3)」であることである。よって、各頂点に対し、mod3で0, 1, 2を上記の条件を満たすように当てはめることを考える。
ここで頂点1を根とすると、距離が3だけ離れている2頂点については、根からの距離の偶奇が異なる。よって根からの距離が偶数のものと奇数のものに分け、各頂点にどの数を当てはめるとよいか考える。
根からの距離が偶数の頂点を偶数頂点と呼び、その個数をtcnt個とする。同様に根からの距離が奇数の頂点を奇数頂点と呼び、その個数をfcnt個とする。
tcnt > n/3 かつ fcnt > n/3の場合、例えば偶数頂点に1を、奇数頂点に2を当てはめてゆき、1・2が足りなくなった場合0を当てはめるという方法を考える。このとき、条件より1は偶数頂点で、2は奇数頂点で使い切れるためうまくいく。
tcnt ≦ n/3のとき、上記の方法を用いると、偶数頂点で1を使いきれない可能性がある。すると奇数頂点で1を使うことになり、偶数頂点と奇数頂点で1が両端となる辺が出てしまう可能性がある。よって上記の方法は使えない。ここで先に偶数頂点で0を使うこととすると、条件より偶数頂点はすべて0が割り当てられることになり、このとき奇数頂点は0, 1, 2どれでもよいことになる。
fcnt ≦ n/3のときも同様である。
ABC158 E - Divisible Substring (500)
解答：Submission #10651412 - AtCoder Beginner Contest 158
解法：解説AC。
s[i: j]をsのi文字目からj文字目までの部分文字列を評価した整数とする。するとs[i: j] = (s[i: N] - s[j+1: N]) / 10j - i +1であることが重要。つまり、s[i: N]を各iについて保持すると、まとめて計算しやすくなる。
「p ≠ 2 かつ p ≠ 5」の場合はs[i: j] ≡ 0 ⇔ (s[i: N] - s[j+1: N]) ≡ 0である。よって、s[i: N] (mod p)の個数を保持する配列を準備し、iを後ろから見てゆき、事前に保持されたs[i: N] (mod p)の値の個数を解答に加算しつつ、s[i: N] (mod p)の個数を更新してゆけばよい。
上記以外の場合、すなわち「p = 2 または p = 5」の場合は、s[1: k] ≡ s[2: k] ≡ … ≡ s[k: k]である。すなわち下1桁でpで割れるか割れないかが決まるため、下1桁を全てチェックするような実装で済む。
AGC033 C - Removing Coins (800)
解答：Submission #10579618 - AtCoder Grand Contest 033
解法：木の直径に注目すると、直径の端点を選んだ場合は直径が1減少し、それ以外の点を選んだ場合は直径が2減少する。
よってこのゲームは「木の直径から1または2を交互に減少させてゆき、木の直径を1にすると負け」というゲームに帰着される。
このゲームは木の直径を3で割った時のあまりが1なら後手の勝ちで、それ以外は先手の勝ちである。
- 木の直径を3で割った時のあまりが0：先手があまり2をキープし、直径が2になった時に先手が端点を選ぶ
- あまりが1：後手があまり2をキープし、直径が2になった時に後手が端点を選ぶ
- あまりが2：先手があまり0をキープし、直径が3になった時に先手が端点を選ぶ
ARC041 C - ウサギ跳び
問題：C - ウサギ跳び
解答：Submission #10535617 - AtCoder Regular Contest 041
解法：左の壁から連続するLと右の壁まで連続するRについては、壁（もしくは先にいるウサギ）に突き当たるまで進ませる。
R...RL...Lになっている並びのウサギを考える。まずはRLの境界のウサギまで、Rのウサギを右に、Lのウサギを左に動かす。そこからどのようにウサギを動かすかだが、RのウサギとLのウサギのいずれか多い向きのウサギをそれ以外のウサギに当たるまで動かすのがよい。例えばRが2匹Lが3匹いれば、Lのウサギを左に動かした方が総移動距離が大きくなる。
なお、実装としては最も左のウサギがLなら位置0にRのウサギを追加し、最も右のウサギがRなら位置L+1にLのウサギを追加することで、全てR...RL...Lの形として処理できる。
CODE FESTIVAL 2016 Final D - Pair Cards (700)
解答：Submission #10528447 - CODE FESTIVAL 2016 Final
解法：mod Mごとに数をグループ分けする。ペアの作り方は下記の3通り。
- 同じ数同士でペアを作る
- 同じグループの違う数同士でペアを作る
- 異なるグループの数同士でペアを作る
グループ0とMが偶数の時のグループM / 2については1, 2の作り方のみ可能である。違う数同士でペアを作れるため、ペアの個数はグループ内の数の個数 / 2（切り捨て）となる。
グループiとグループM - iについては、1, 2, 3全てのペアの作り方が可能である。ここで、最大のペア数を生み出すペアの作り方、すなわち最大マッチングの方法は下記の通りである。(グループiの数の個数をT、グループM - iの数の個数Sとし、T ≦ Sとして一般性を失わない。)
- T個のペアを3の作り方で作る（グループiの数は全てペアになる）。このときグループM - iの数はペアに出来ないものから選ぶ
- グループM - iの残りのS - T個について、ペアに出来るものをペアにする
この方法で最大マッチングが実現できることを次のように証明する。
- 最大マッチングが与えられたとき、ペアの数を減らさずにグループiの数は全てグループM-iとペアになっているようにできることを示す
- 上記の場合、グループM-iの数はペアにならないものからグループiとマッチングされていることを示す
2はもしそうでなければ最大マッチングでないことがあるため、その通りである。よって1を示す。 最大マッチングが与えられたとき、グループi、グループM - i の数は下記の3通りの状態にある。
- ペアになっていない
- 同じグループの数とペアになっている
- 違うグループの数とペアになっている
3の場合は問題ない。
グループiに1の状態の数がある場合、グループM-iにも1の状態の数があれば、ペアが出来てしまうため、最大マッチングの仮定よりグループM-iには1の状態の数がない。T ≦ Sを仮定するため、グループM-iには2の状態の数がある。よってそのペアを解消し、グループiとグループM-iとでペアを作れればよい。
グループiに2の状態の数がある場合、まずそのペアを解消する。このときグループM-iに1の状態の数が2つ以上あると、最大マッチング以上のペアが作れてしまうため、グループM-iに1の状態の数は1以下である。このときT ≦ Sを仮定するため、グループM-iに2の状態の数がある。よってこちらもそのペアを解消し、グループiとグループM-iとでペアを作り直せばよい。
AGC022 B - GCD Sequence (600)
解答：Submission #10499621 - AtCoder Grand Contest 022
解法：解説AC。
aiの和をSとすると、gcd(ai, S) > 1 でgcd(a1, a2, ..., an) = 1を満たすaiの構築をすればよい。
制約がN ≦ 20000、ai ≦ 30000であり、N = 20000の時は30000から2/3程度選ばれていることになる。
ここで「Sが6の倍数であり、aiが2の倍数または3の倍数でかつ2と3を含む」とすると、このaiは問題の条件をクリアしている。これはaiを6k+2, 6k+3, 6k+4, 6kと選んでいき、最後にこの数列を修正してあげることで達成できる。
Sの和の推移は、mod 6で2, 5, 3, 3, 5, 2, 0, 0 であり（次は2に戻って繰り返す）、修正すべき場合はS≡2, 3, 5(mod 6)の場合である。なお、aiが上限の30000をとるときはS≡0(mod 6)である。（上記の8項の最後の0）
修正方法は下記の通り。
- S≡2(mod 6)の場合：8を除去して30000を追加する。(30000は必ず使われていない)
- S≡3(mod 6)の場合：9を除去して30000を追加する。(30000は必ず使われていない)
- S≡5(mod 6)の場合：9を除去して29998を追加する。(29998は必ず使われていない)
ARC027 C - 最高のトッピングにしような
解答①：Submission #16192313 - AtCoder Regular Contest 027
解法①：スペシャルチケットがx枚であるときは、x種類までしか品物を選ぶことができない。逆に、x種類までで品物を選ぶとしたらその中では通常のチケットとスペシャルチケットの枚数を区別する必要がない。
よって、dp[i][j][k] ：i番目の品物までで、j個品物を買っており(j ≦ x)、残りのチケット枚数がk枚であるときの嬉しさの最大値 としてDPする。
解答②：Submission #10481643 - AtCoder Regular Contest 027
解法②：今の品物の番目、残りのスペシャルチケットの枚数、残りの通常チケットの枚数を保持しながらメモ化再帰。
遷移は愚直にやるとスペシャルチケットi枚と通常チケットt[j] - i枚の使用を1 ≦ i ≦ t[j]で考えることになるが、これだとTLE。
「基本的にスペシャルチケットは1枚ずつ使用し、通常チケットを全部使うときに足りないチケットをスペシャルチケットで補う」みたいな考え方で遷移させるとうまくいった。
メモ化再帰のmemo用mapのキーをtupleにしていたらTLEだった。intにして3変数をうまく表現させるとぎりぎり間に合った。
