AtCoder ABC112

2018.10.06 21:00~のAtCoder ABC112に参加しました。

結果はDを1WAで全完でした。47分かかってしまったのでもっと早くしたいです。

A - Programming Education

1つ目の入力が1か2かで分岐。出題形式がちょっと珍しい気がしました。

B - Time Limit Exceeded

時間が目標時間T以下か判定。もし小さいなら最小コストをとminをとって更新。

更新がないならTLE、または最小コストを出力

C - Pyramid

「ピラミッドの中心座標と高さをちょうど 1つに特定することができる」とか言っておいて、x、yが0~100の外には別の解が存在しうる詐欺問題だが、それをテストケースで教えてくれてる良心問題だった。 x,yを0~100の範囲で変更し、全てで矛盾がなければそこが正解。 あるx,yを中心とするときの高さは、ある0でない高さを持つ点の座標と高さからO(1)で計算可能。 候補数N、範囲XでO(NX²)で最大10⁶なので問題ない。

D - Partition

全ての数が持つ共通の約数は和の約数でもある。 Mの約数を大きいものから、「その約数をN個足すとMより大きくなるか」を判定する。 Mより大きくなってしまうと、和がMという制約を破ってしまう。 そうならない最大の約数が答えである。 副産物として、新しく「約数を列挙するライブラリ」を作った。

感想

• Cが制約をちゃんと見ていなかったので時間がかかった
• Dの最大の約数がな気がしてしまってわけわからん回答をしたのがいたかった