学校が吹き飛んでるのに埋めのペースが鈍ってきています。由々しき事態です。
- AGC043-C Giant Graph (900)
- AGC033-E Go around a Circle(1500)
- AGC016-D XOR Replace (1000)
- AGC010-F Tree Game (1600)
- AGC010-D Decrementing (1000)
- AGC007-C Pushing Balls (1000)
- AGC010-C Cleaning (700)
- AGC030-C Coloring Torus (1000)
- AGC038-D Unique Path (700)
- AGC043-D Merge Triplets (1200)
- AGC019-D Shift and Flip (1000)
- AGC015-F Kenus the Ancient Greek (1700)
- まとめ
(ネタバレ防止用の空白)
AGC043-C Giant Graph (900)
本番後に解説をチラ見した
1) 重みの差が大きすぎるので頂点は貪欲に取っていい
2) $X$ に隣り合う頂点は取ってはいけない 周りに隣り合う頂点がなくなったら取っていい
この条件にデジャビュを感じるので思い出すと、これはGrundy数っぽい
3) 3次元だと考えにくいので1次元に戻す
ここでGrundy的性質を見ると、各頂点のGrundyはxyzそれぞれ1次元で求めたGrundyのXORになる (←ここが思いつかなかった 3ゲームをマージすると考えれば自然な流れなのかも)
Grundy数は√Mに比例する個数しかなく、数え上げパートは頑張れば行ける ΣΣΣ10a_i+b_j+c_kみたいなものの求め方さえわかれば一直線
AGC033-E Go around a Circle(1500)
まずBが最初にあったらRとBを反転させ、以後最初はRとして扱う。
まず全部同じな場合がコーナーケースで、その時は答はリュカ数列になる。
Bが2個以上連続すると、真ん中から出発できなくなるのでBの長さは絶対に1でなければならない。またRが偶数個連続すると、パリティより脱出できない点ができるのでRは全て奇数。最小のRの長さと冒頭のRを考慮して、Rの最大長もわかる。このとき最後がRだったとき、その部分の弧の真ん中で停止しても問題ないことに注意する。
数え上げパートだが、実験するとN項間漸化式が出てくる
AGC016-D XOR Replace (1000)
総XORを$x$とすると、1回の操作は$x$と数列の要素を交換する操作になる。これでYES/NOは終わり
本質はここからで、まず同じ要素はまとめてよい(ここで迷った。) swap可能性をUnionFindで考えるのは典型で、$x$が同じ連結成分かどうかで答えが変わる。
AGC010-F Tree Game (1600)
頂点$x$の周りが$x$より大きい奴で囲まれてたらGAME OVER
先手が$x$より大きい頂点へ移動したとして、後手は$x$へ戻すことで両方の頂点の数が1減った元のゲームに戻すことができ、これを繰り返すといつかは$x$が尽きて詰む
残された手は小さい方へ避難することだけなので、適切にグラフの辺に向きをつけられるor消せる トポロジカルソートの要領で答えが出る こういうお気持ち系はりんごさんをバグらせるのかな
AGC010-D Decrementing (1000)
1が発生したらパリティ勝負になることを踏まえて、パリティ勝負っぽさがある
1を引くことで、パリティの変動は必ず1になる。
また1を引いた後に全体を奇数で割ってもパリティの変化は起こらない。ここで問題になるのが、偶数で割った場合である。
偶数で割るとパリティがぐちゃぐちゃになる。しかし、パリティの変動は必ず1であることを使うと「勝ち筋」に入った側が変動させるのを阻止し続けることができる。よってこれを使いたいときは自分が「負け筋」にいるときで、なおかつ自分の操作で2で割る行動をできるようにすることができる時である。このような場合は奇数が1個だけある時で、これを使っても状況が好転しなければ無駄で好転すればそのまま逃げ切ってよい。再び奇数が1個だけになった場合は後手がほぼ同じように振る舞う。この操作はlogA回で終わるので十分高速
階差とかいろいろ考えて迷走したけどやっぱりパリティは大事 atcoder.jp
AGC007-C Pushing Balls (1000)
$i+1$回目の期待値は$i$回目の$\frac{N-i+2}{N-i+1}$です 何で？ 各区間が何回足されるかを求めようとすると面倒な二項係数と二重階乗とが出てきて計算量がO(N3)になって破滅する
AGC010-C Cleaning (700)
ずっと考えては挫折してきた問題
今回は葉っぱから見るのが正解 ある頂点を見たとき、操作で選ばれるパスはある頂点で折り返して下に行くか上まで行くかの2択 ここでdp[x]=頂点xに至るまで下から何本伸ばせるか というDPを考える
頂点xにある石の個数から、何回折り返せばいいかは一意に定まる あとは実際に要求を満たすことができるか検証 ここもやさしめ(700だから？)
AGC030-C Coloring Torus (1000)
AGC-Cラスト！！！
初手でガチャガチャやっても拡張性が無だったのでTwitterでぼやいていたところ、何やらヒントをもらう
そのヒントをガチャガチャしているとmod4で3の場合が作れ、2の場合が作れ、そして1の場合が作れた
どうやったら自力で思いつくの？？？？
AGC038-D Unique Path (700)
A-BとA-CがUniqueならきっとB-CもUniqueだろうと信じ、まずはC=0をUnion-Findで結ぶ。
C=1の作り方だが、連結成分を頂点に縮約した後
全体が連結
二重辺が存在しない
この2つを満たしていればとりあえず条件に合致する。逆に合致しなければ即アウト
最後は辺の数だが、各成分から代表者を1個ずつ選んできて、それを円形につなげば最小。完全グラフにすれば最大。
AGC043-D Merge Triplets (1200)
最小性の議論よりXを除去した後にXより小さい値を除去することになったら、それはXのすぐ下になければならない。X>Y>Zの時にX-Z-Yの順で入っていることもあることに気づくと、その時点での最大が更新されるまでずっと同じ要素の後ろにくっついてくる。この辺を考えると、今の最大から次の最大までの距離が高々3であることが必要。あと2以上がたくさんあると詰められなくなるのでこれも必要条件で、実際にこれが構築できるので十分でもある。
数え上げパートが本題、ここからでも普通に800ありそう。 手元に詰め込んでいない要素がN個あったとして、そこからPの先頭にブロック単位で詰め込んでいくことを考える。
1個詰め込む場合は必ず最大を取ってきて入れる。2個か3個詰め込む場合は最大値とおまけを取ってきて詰め込む。これをDPに落とせばOKだが、この見方ができないとつらそう
AGC019-D Shift and Flip (1000)
bitset高速化のO(N3logN)通るかと思って限界高速化を試して41WA出したのは秘密
Aを回すと見づらいので代わりにBを回して、「Bのonになっている部分が通ったら自由に反転してよい」という風に変更する。
|A|=Nとして、N2程度なら間に合うので最終的なBの回転を決め打つ。右回しと左回しがあるが片方は後で文字列を反転させて同じ問題を解くことで省略する。最適なムーブは0→逆向きに$x$個回す→0→順向きに$k$個回す→さらに$y$個回して戻す だと直感的にわかるので適切に実装する。
最初の座標、終点として決めた座標から最終的に変えなければならない位置(以後ペナルティ)までの距離を割り出す。これは二分探索で可能 各ペナルティに対して、そこに左からつけるか右からつけるかの二択があるので結局こういう問題に帰着できる。
長さ$N$ の数列A , Bがある。各iについて、AiとBiのどちらかを選ぶ。 max(選んだA)+max(選んだB)を最小化せよ。
これはAでソートすれば簡単
実装がしんどいと思ったけどそんなにしんどくなかった
AGC015-F Kenus the Ancient Greek (1700)
反復回数が最大になるような組はフィボナッチ数の隣接項というのは常識
GCDが2以上になるような組は絶対に最大にならないことは示せる。(ある数の2倍が採用されるより先に次のフィボナッチ数が来ることから)
実際に条件を満たすペアを構築することを考える。$(F{i-1} , F_i)$ まで構築し、最後の1回で$(F_i, F_i+kF{i-1})$という風にすることで条件を満たす。
それ以外の方法でも構築ができる。フィボナッチ数の計算の時、途中のどこかで片方を2倍しても条件を満たす。例えば{1,1,2,3,5,13,18,31,49}の様にする。解説によれば2倍する操作は2回以上行われず、また3倍以上することもないらしいが証明できなかった。
まとめ
12問 13300点
解ける問題がほとんどないのでAGC埋めはこの辺にしてABC/ARCやCodeforcesに転換しようと思います。
3カ月間42問解いた経験は無駄ではないと思います。今までありがとうございました。AGCの開催楽しみにしております。
