AtCoder ABC216
ABC216参加しました。
A - Signed Difficulty
解説 - AtCoder Beginner Contest 216
文字列で受け取り、うまくX,Yを抜き出せれば、後はifで分岐するだけ
B - Same Name
解説 - AtCoder Beginner Contest 216
forの二重ループを書いても計算量的には間に合います。
普通に仕事でも書きそうなコードだとは思います。
C - Many Balls
解説 - AtCoder Beginner Contest 216
Submission #25422752 - AtCoder Beginner Contest 216
コラッツ予想という問題がありますが、それに似ているなと思いました。
Nから0に向かう手順を考えればよいです。 0から上がっていくと、ピッタリNに合わせるのは難しいですが、ピッタリ0にあわせるのは、以下で考える魔法の逆演算を考えれば簡単だとわかります。
問題文で与えられた魔法は0->Nへ向かうときの魔法なので、逆算して考える場合は、ちょうど魔法の逆演算をすることになります。
この場合明らかに魔法Aは1を引くこと、魔法Bは2で割ることが逆演算です。
後は、120回という制約のもとでNから0に向けて、ひたすら小さくしていくことになります。演算過程で強力なのが魔法Bの逆演算で、これで一気に値を小さくできます。このため、できる限り魔法Bの逆演算を多用して回数を稼いでおきたいところです。
この魔法Bの逆演算を適用するには、偶数である必要があります。なぜなら、0からNに向かう場合が本来考えたい過程であるため、その過程でどれだけ魔法A,Bを多用しても「小数」は出てきません。よってNから0へと向かうように考えている過程であっても小数が出てはいけません。
つまり、Nが偶数であれば魔法Bの逆演算、奇数であれば魔法Aの逆演算を施しつつ、0に向かって小さくしていけばいいです。
120回の制約は、Nが最大値の$10^{18}$だと、魔法Bを60回近く使えば達成できます。これは実際にNのlog2を取ってみればわかります。途中魔法Aを使っても達成できるでしょう。
D - Pair of Balls
解説 - AtCoder Beginner Contest 216
Submission #25473484 - AtCoder Beginner Contest 216
ACできなかったので、公式解答を見ました。で、
Pair of Balls [AtCoder Beginner Contest 216 D] - はまやんはまやんはまやん
ここの答えをそのままC#で実装したのが上のコードです。
コメントを見てもらうとわかりますが、結局の所、筒を何度も見なくて済むように、Available[i]にメモしておくのが肝なんだと思います。queは、先頭が消せる筒の番号をメモしたものです。
Available[i]は、既に値(=筒番号)が入っていれば、その値とiとが、queに入れられることになります。逆にAvailable[i]に値が入っていない場合は、単にAvailable[i]に筒番号を入れるだけです。
C#に馴染みがない人に向けての補足ですが、最後のArray.TrueForAll()は引数で渡した配列について、述語のramda式ですべての要素を評価し、すべてtrueを返すかどうかを調べています。今回は、Aが筒の配列なので、すべての筒が要素数0かどうかを調べています。ListではなくLinkedListの配列なのは、(先頭)要素の削除が多そうで、Listだと時間を食いそうだったからです。
まとめ
D問題はなにかしら法則を見つけ出す問題だと信じて疑わなかったので、愚直にシミュレーションしてなかったな～。
