ABC119 参加メモ
スキー帰りでちょっと疲労感がありましたが無事参加しました。 https://atcoder.jp/contests/abc119
rating
734から980に増加しました(+246)。 色も茶から緑になりました。 この調子でまずは水色を目指したい。
A
Pythonだと不等号を用いることで、辞書式順における文字列の大小を判定できます。
したがって、 Sが 2019/04/30 以下ならば Heisei, そうでなければ TBDを出力するだけでよいです。
B
定義通り計算するだけですね。 出力誤差についてはそこそこ許容してくれるので、浮動小数点数演算に怯える必要はありません。
C
Dより苦戦しました（Cより先にDを解きました）。 Nが8なのでゴリ押しでいけそうな雰囲気なのですが、いざゴリ押しコードを書こうとすると手が進まない。
最終的には、以下の考え方で解きました。
- N本の竹から長さのAの竹を作るために用いる竹を高々N-2本選ぶ
- 選んだすべての竹に対して、合成魔法を適用する（ポイント: 合成魔法はどの順序で適用しても結果は変わらない）
- 合成後の竹の長さがAになるように、延長魔法または短縮魔法をかける
- 残った竹についても長さB, Cを作るために、同様の処理を実行する
処理回数が指数的に増加するので、TLEが懸念されますが、各竹について、A, B, C, 使わないのいずれかのラベルを貼ると考えれば、パターンは高々 です（すべてAとかはありえないので、実際はもっと少ない）。
Nは高々8なので余裕で解けると見積もれます。
D
Cを後に回して先に着手しました。 これも難しかったらヤバイなーって思いつつも問題読んだら、手がつけやすそうな問題で安心。
まず、各xについて、訪問パターンは以下の4通り考えられます。
- そのxより西側で最も近い神社sと西側で最も近い寺tを訪問:
- そのxより西側で最も近い神社と東側で最も近い寺を訪問:
- そのxより東側で最も近い神社と西側で最も近い寺を訪問:
- そのxより東側で最も近い神社と東側で最も近い寺を訪問:
あとは、各xについて、西／東側で最も近い神社／寺を見つける方法を考えればよいです。 そしてそれは二分探索で求められます。 Pythonだとbisectという標準ライブラリを使うと楽です。
