AtCoder Beginner Contest 198参加記（～E問題）

コーナーケースに気を付けろ！！
　　　　　

A - Div

A君が得るお菓子の個数を個、B君が得るお菓子の個数を個とすると、という等式が成り立つ。この式から、を固定するとは通りに定まること、がともに正の整数でなければならないことを考えると、が取りうる範囲の中にある整数の個数、つまりが答えとなる。計算量は、。

ちなみに制約がゆるいので、brainfuckでも簡単なif文の処理が書ければ解ける。

B - Palindrome with leading zeros

問題文中の操作は、「を文字列としてみたときの末尾から連続している0をすべて削除する」と言い換えられる。こうすることで、操作後の文字列が回文かどうかを一度判定するだけで答えが求まる。のときの処理に注意。計算量は。

C - Compass Walking

歩歩くことで、ユークリッド距離が以内の点に移動することができる。また、歩以下で到達できる範囲は、原点から距離が以内の範囲である。このことから、解を二分探索して求めることができる。
ただし、歩歩くことで到達できるのは原点からちょうど離れている点だけであるので、二分探索して得られた解がだった場合にのみ、原点からの距離で場合分けする。

二分探索について。ルートを使うと小数誤差にやられる危険性があるので、整数のまま計算する。具体的には、距離の大小さえわかればよく、距離は負の値を取らないので、距離の2乗をそのまま比較する。式は以下の通り。

また、解の最大値は程度と見積もれるが、距離の2乗で比較する方針だと上式の右辺が最大でとなりオーバーフローするので、二分探索するときの解の最大値はとした。こうすると右辺は単にとなる。計算量は。

コンテスト中はこれで十分だが、より厳密に議論すれば二分探索を用いなくてもで答えを求めることができる（公式解説より）。考察をサボれるときはサボることも大事。

D - Send More Money

条件がごちゃごちゃ書いてあるが、普通に覆面算を解くだけの問題。各英小文字に一桁の整数を割り当てるので、文字の種類数が以上ある場合は解なし。

文字の種類数が以下だった場合、各文字に整数を割り当てる方法を全通り試す。文字の種類数をとすると、通り試せばよいことになる。C++のnext_permutation関数に長さ10の順列を与えてループを回し、順列の先頭個だけをみて実際に文字に割り当て、が成立するか確かめる。計算量は。

E - Unique Color

与えられるグラフは木であるので、頂点間を結ぶパスは必ずつだけ存在する。もちろんそのパスが最短である。また、木の頂点から頂点までのパス上に頂点が含まれていた場合、そのパスに頂点から頂点までのパスが完全に含まれている。

以上のことより、頂点からDFSをして「よい頂点」でない頂点を探すこととする。具体的には、DFSをしながら通った頂点の色をメモしていき、頂点の色がすでに登場しているなら答えから外す、ということをしていけばよい。

メモするための道具として集合（set、挿入・削除がともに）を用いたがTLEしてしまった。setのかわりにunordered_setを使ってみたが変わらず。しかもこの方法はメモリも大量に使うため非常に重い。
もう少し考えると、DFSで戻ってくるとき「どのタイミングで色が使われなくなったか」は「どのタイミングで初めて色が使われたか」の解と等しいため、setを使わず、bool配列で管理することができる。
計算量は、。

F - Cube

むずすぎ

感想

青パフォだったのでうれしいけど、Eでの2ペナがもったいないと思った