AtCoder Grand Contest 034
水色以下にとってはAB早解き競争だったのに私は凡ミスで3WAして順位を200以上落としました
A - Kenken Race (400点)
問題: A - Kenken Race
まず、から
あるいは
から
の間に岩が2連続しているとどうやっても飛び越せないので、ゴールは不可能。次に、
の場合にはすぬけ君がふぬけ君をどこかで飛び越さないといけないが、これは3マス以上連続した空白がないと不可能。これを判定してAC。
。
B - ABC (600点)
問題: B - ABC
これは "BC" を 'S' とでも置き換えると、"AS"を "SA" に変えることのできる最大の回数を求める問題に帰着できる。更に、この問題は 'A' あるいは 'S' からなる連続する部分文字列各々の中で何回 'S' を左に寄せることができるか、という部分問題に分割できる。'A', 'S'の列に分解すれば、この部分問題はAGC029-Aそのものなので、これを実装してAC。。
C - Tests (800点)
問題: C - Tests
わかりませんでした
公式解説によれば (問題リンク先メニューの解説>PDF を参照) 1つの教科を除いたほかは、満点をとるか0点をとるかしかないので、満点でも0点でもない教科を全探索しどこまで満点を取ればいいか二分探索して解けるらしいです
D - Manhattan Max Matching (1200点)
問題: D - Manhattan Max Matching
見てません
E - Complete Compress (1500点)
問題: E - Complete Compress
木の根を固定すると、根以外にあるコインを2つ選んで手繰り寄せる操作とみなすことができる。この操作はコインが初めに乗っているノードの深さから操作をすべき回数がわかる。操作を行うコインの組を無向グラフの辺とみなすと、このノードの深さは頂点の次数となり、したがってコインの乗っているノードの深さの和は偶数でなくてはならず、また操作の最小回数はこの和の2分の1とわかる。
（以下解説見た）
また、その操作は、最近共通祖先の深さが広義単調減少するような操作をすることで最小回数の操作が達成できる。つまり、近いノードから順にまとめていくと操作が達成できるかわかる。木DPで、コインを順次手繰り寄せていってかかる最大の操作回数を更新していき、最終的に木DPで求めた最大回数と先述のノードの深さの和÷2が一致すればこの操作は真に可能と判定できて、有効な操作のうち最小回数を求めてAC。木の根はすべてのノードを全探索し、各ノードでBFS、木DPを行うので
、合わせて
。
拙解: まだ
F - RNG and XOR (1600点)
見てません
まとめ
A問題は添字が1ずれてたのとB問題はデバッグ表示をcoutで行っていたのとで順位とパフォをそれぞれ200以上落としてしまいました
バルマーピーク狙って少し酒を飲みながら参加していたんですがケアレスはどうにもならないですね…（むしろ悪化してる）
