ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

ABC113 参加記録&解説

AtCoder Beginner Contest 113 - AtCoder

22分台全完で21位でした。

f:id:betrue12:20181104225338p:plain

A - Discount Fare

A - Discount Fare

解法

 X + \frac{Y}{2} を計算して出力すればよいです。

ACコード

RubySubmission #3531033 - AtCoder Beginner Contest 113

B - Palace

B - Palace

解法

 N 個の地点それぞれについて  |(T - H_{i} \times 0.006) - A| を計算し、それが最も小さい地点を探せばよいです。

ACコード

ちょっとした実装テクとして、上記のコードのようにC++min_element を使うと、「 vector の中で最も小さい要素のインデックス」がスマートに取得できます。

C - ID

C - ID

解法

市を県ごとに分類し、それぞれの県ごとに誕生年でソートします。そうすると、それぞれの市がその県で何番目に誕生した市かが分かります。

…というものを素直に実装すればよいです。300点問題で数学が要らないのは、最近だと珍しいですね…

ACコード

実装テクという点では、

  • 誕生年でのソートをする際に、市のインデックスも巻き込むと後の実装がしやすくなる。そのため市を県ごとに分類する際、C++だと pair などを使って、誕生年と市のインデックスをまとめておく。
  • 指定された桁数になるように左に0を埋める方法(C/C++だと、printf のフォーマット指定子で可能

などを知っておくとよいですね。

D - Number of Amidakuji

D - Number of Amidakuji

解法

ある行までの横線の引き方は、その1つ上の行までの横線の引き方から計算できそうです。上からDPをしていくことを考えます。

 i 行目まで考えた時に、縦線1からスタートしたものが  k 番目の縦線に移動しているような横線の引き方の総数」を  dp\lbrack i \rbrack\lbrack k \rbrack とします。初期条件は  dp\lbrack 0 \rbrack\lbrack 1 \rbrack = 1 で、答えは  dp\lbrack H \rbrack\lbrack K \rbrack です。

 i 行目から  i+1 行目への遷移に必要な情報は、「1行の横線の引き方であって、  j 番目の縦線から  k 番目の縦線に移動する引き方の総数」です。これを  num\lbrack j \rbrack\lbrack k \rbrack とすると、  i 行目から  i+1 行目の遷移は

 dp\lbrack i+1 \rbrack\lbrack k \rbrack = \sum_{j} (dp\lbrack i \rbrack\lbrack j \rbrack \times num\lbrack j \rbrack\lbrack k \rbrack)

と求められます。

次は、この  num\lbrack j \rbrack\lbrack k \rbrack の求め方を考えます。1行の横線の引き方は、線を引くところが  W-1 箇所しかないため、高々  2^{W-1} 通りです。 W \le 8 であることから  2^{W-1} は十分小さいので、全部確認してしまいましょう。

f:id:betrue12:20181104234145p:plain

1行の線の引き方を全部列挙すれば、以下のように  num\lbrack j \rbrack\lbrack k \rbrack が求められます。

  1. 0から  2^{W-1} -1 までの整数をループで回す。この整数をビット列として見た時の  W-1 個のビットがそれぞれ横線の有無を表し、  k 番目のビットが1であることは「  k, k+1 本目の縦線間に横線がある」ことを示す。
  2. これが「どの2つの横棒も端点を共有しない」というルールに違反する、つまりビット列として見た時に連続した1を含む場合、スキップする。
  3. この線の引き方のとき、 j 番目の縦線からどこの縦線に移動するかを各  j ごとに計算する。これを  k_{j} とおく。
  4.  j ごとに、 num\lbrack j \rbrack\lbrack k_{j} \rbrack に1を加算する。

この  num\lbrack j \rbrack\lbrack k \rbrack を用いてDPを行えば、答えを求めることができます。

ACコード