AtCoder Beginner Contest 113 参戦記
今度こそは水色へ、と意気込んだABC113。
C完でDも解法はある程度わかったのですが、実装で手間取って例題を通す前に時間切れとなりました。
うーん、水色目前で停滞中です。
A - Discount Fare
問題
https://beta.atcoder.jp/contests/abc113/tasks/abc113_a
解法
X + (Y/2) を出力するだけ
実装
x,y=gets.chomp.split.map(&:to_i) puts x+y/2
B - Palace
問題
https://beta.atcoder.jp/contests/abc113/tasks/abc113_b
解法
各Hi毎に平均気温とA度との差の絶対値を計算し、それが最小の時のiを出力すればよい。
実装
n=gets.to_i t,a=gets.chomp.split.map(&:to_i) h=gets.chomp.split.map(&:to_i) m=Float::INFINITY ans=0 h.each_with_index do |v, i| mm = (a-(t-v*0.006)).abs if mm < m ans = i+1 m = mm end end puts ans
C - ID
問題
https://beta.atcoder.jp/contests/abc113/tasks/abc113_c
解法
各市を読み込みながら、各県に誕生年を振り分けていく。
全て読み込んだら、各県毎の誕生年をソートして各市の順番(x番目)を決定する。
最後に各市毎に認識番号を出力していく。
ということで、考え方自体はそんなに難しくないが、誕生年の順番をどのように知るかにちょっと工夫が必要。
実装
実装としては、配列とハッシュを使って以下のようにした。
まず、各県ごとに誕生年を配列に格納してから最後にソートする。
その後、配列を先頭から見ていき、誕生年をキー、順番を値とするハッシュに格納する。
認識番号を決める際はこのハッシュを使って誕生年から順番を取得するようにする。
n,m=gets.chomp.split.map(&:to_i) p = [] y = [] py = Array.new(n+1).map{Array.new()} m.times do |i| pp, yy = gets.chomp.split.map(&:to_i) p << pp y << yy py[pp] << yy end ph = Array.new(n+1).map{Hash.new()} py.each_with_index do |v, i| v.sort! v.each_with_index do |vv, j| ph[i][vv] = j+1 end end 0.upto(m-1) do |i| printf("%06d%06d\n", p[i], ph[p[i]][y[i]]) end
D - Number of Amidakuji
問題
https://beta.atcoder.jp/contests/abc113/tasks/abc113_d
解法
あと一歩で解けなかったD問題。
取りかかってから10分ぐらいで動的計画法を使うっていうのは分かったんだけど、実装に手間取って例5を通すことが出来なかった。
この問題のポイントは、動的計画法の漸化式をどうたてるか、と、各縦線の数に対して有効な横線の引き方が1段について何通りあるか、です。
- 漸化式の考え方
i番目の行まで横線が引き終わっている時にj列目に存在するときの組み合わせをDP[i][j]とします。
すると、i+1番目でj列にいく組み合わせは
DP[i+1][j] = DP[i][j-1] x (j-1とjの間に線を引くときの組み合わせ)+ DP[i][j] x (j-1とjとj+1の間に線を引かない組み合わせ)+ DP[i][j+1] x (jとj+1の間に線を引くときの組み合わせ)
で求められます。
例を使って説明します。
i+1番目で4列目にいけるのは、i番目で3列目、4列目、5列目にいる場合です。
3列目にいる場合は、3列目と4列目の間に横線を引く必要があります。この場合、それ以外の場所については、左側は1、2列目の間、右側は5、6列目の間の横線の引き方の組み合わせとなります。
4列目にいる場合は、3列目と4列目、及び、4列目と5列目の間に横線を引いてはいけません。この場合、それ以外の場所については、左側は1、3列目の間、右側は5、6列目の間の横線の引き方の組み合わせとなります。
5列目にいる場合は、4列目と5列目の間に横線を引く必要があります。この場合、それ以外の場所については、左側は1、3列目の間、右側はこれ以上横線は引けません。
- 有効な横線の引き方
では、あみだくじとして有効な横線の引き方をどう算出するかです。
これも漸化式の考え方で求めることが出来ます。
縦棒の数がi本の時の一行分の線の引き方をSiとします。
このとき、漸化式は以下のようになります。
これは、i列目とi+1列目に横棒を引く場合はi-1列目とi列目に横棒は引けないのでそれより左側の組み合わせはSi-1通りとなり、i列目とi+1列目に横棒を引かない場合はそれより左側の組み合わせはSi通りになるためです。
ちなみにこれはフィボナッチ数列になります。なお、今回の問題は縦棒は8本までしかないので、数列はハードコードしてしまってます。
実装
以下の実装では、左端と右端は場合分けしていますが、両端に0の列を追加すればもう少し綺麗なるかも。
h,w,k=gets.chomp.split.map(&:to_i) dp=Array.new(h+1).map{Array.new(w)} MOD = 1000000007 nn = [1,2,3,5,8,13,21,34] dp[0][0] = 1 1.upto(w-1) do |i| dp[0][i] = 0 end if w == 1 puts 1 exit end 1.upto(h) do |i| 0.upto(w-1) do |j| dp[i][j] = 0 if(j==0) dp[i][j] += dp[i-1][j] * nn[w-2] dp[i][j] += dp[i-1][j+1] * nn[[0,w-3].max] elsif(j==w-1) dp[i][j] += dp[i-1][j] * nn[w-2] dp[i][j] += dp[i-1][j-1] * nn[[0,w-3].max] else n = nn[[0,j-2].max] n *= nn[[0,w-2-j].max] dp[i][j] += dp[i-1][j-1] * n n = nn[j-1] n *= nn[[0,w-2-j].max] dp[i][j] += dp[i-1][j] * n n = nn[j-1] n *= nn[[0,w-3-j].max] dp[i][j] += dp[i-1][j+1] * n end dp[i][j] = dp[i][j] % MOD end end puts dp[h][k-1] % MOD
結果
Cまでは順調だったんですが、Dで躓いてしまいました。
しかも、Dは動的計画法の漸化式まではある程度思いついたんですが、結局実装しきれませんでした。
とはいえ、動的計画法は苦手分野だったので、途中まで書けただけでも成長したかなという感じです。
いずれにせよ、水色手前でなかなか上がれません。
やはり400点問題は確実に解けるようにしたいところですね。