ABC113 参加記録&解説
AtCoder Beginner Contest 113 - AtCoder
22分台全完で21位でした。
A - Discount Fare
解法
を計算して出力すればよいです。
ACコード
(Ruby)Submission #3531033 - AtCoder Beginner Contest 113
B - Palace
解法
個の地点それぞれについて を計算し、それが最も小さい地点を探せばよいです。
ACコード
- (Ruby)Submission #3542648 - AtCoder Beginner Contest 113
- (C++)Submission #3542662 - AtCoder Beginner Contest 113
ちょっとした実装テクとして、上記のコードのようにC++の min_element
を使うと、「 vector
の中で最も小さい要素のインデックス」がスマートに取得できます。
C - ID
解法
市を県ごとに分類し、それぞれの県ごとに誕生年でソートします。そうすると、それぞれの市がその県で何番目に誕生した市かが分かります。
…というものを素直に実装すればよいです。300点問題で数学が要らないのは、最近だと珍しいですね…
ACコード
- (Ruby)Submission #3533911 - AtCoder Beginner Contest 113
- (C++)Submission #3542824 - AtCoder Beginner Contest 113
実装テクという点では、
- 誕生年でのソートをする際に、市のインデックスも巻き込むと後の実装がしやすくなる。そのため市を県ごとに分類する際、C++だと
pair
などを使って、誕生年と市のインデックスをまとめておく。 - 指定された桁数になるように左に0を埋める方法(C/C++だと、
printf
のフォーマット指定子で可能)
などを知っておくとよいですね。
D - Number of Amidakuji
解法
ある行までの横線の引き方は、その1つ上の行までの横線の引き方から計算できそうです。上からDPをしていくことを考えます。
「 行目まで考えた時に、縦線1からスタートしたものが 番目の縦線に移動しているような横線の引き方の総数」を とします。初期条件は で、答えは です。
行目から 行目への遷移に必要な情報は、「1行の横線の引き方であって、 番目の縦線から 番目の縦線に移動する引き方の総数」です。これを とすると、 行目から 行目の遷移は
と求められます。
次は、この の求め方を考えます。1行の横線の引き方は、線を引くところが 箇所しかないため、高々 通りです。 であることから は十分小さいので、全部確認してしまいましょう。
1行の線の引き方を全部列挙すれば、以下のように が求められます。
- 0から までの整数をループで回す。この整数をビット列として見た時の 個のビットがそれぞれ横線の有無を表し、 番目のビットが1であることは「 本目の縦線間に横線がある」ことを示す。
- これが「どの2つの横棒も端点を共有しない」というルールに違反する、つまりビット列として見た時に連続した1を含む場合、スキップする。
- この線の引き方のとき、 番目の縦線からどこの縦線に移動するかを各 ごとに計算する。これを とおく。
- 各 ごとに、 に1を加算する。
この を用いてDPを行えば、答えを求めることができます。