目次
AtCoder Beginner Contest 113
解説放送は無いそうです。
A - Discount Fare
問題
- 街 $a$ から街 $b$ までの鉄道の運賃が $X$ 円
- 街 $b$ から街 $c$ までのバスの運賃が $Y$ 円
- 鉄道とバスを同時に使うとバスの運賃が半額になる
- 街 $a$ から街 $c$ までの交通費を求めよ
解法
$X+Y/2$
バスのみ半額になるところとか問題文の読み取りミスに注意
x, y = map(int, input().split()) print(x + y // 2)
B - Palace
問題
- 宮殿を建てる
- 宮殿の建設候補地は $N$ 個あり、$i$ 番目の標高は $H_i$ である
- この国では標高 $h$ の地点の平均気温は $T-0.006h$ である
- 平均気温が $A$ に最も近い地点に宮殿を建てたい時、何番目の建設候補地がよいか求めよ
解法
各候補地について平均気温を求めて、$A$ との差の絶対値が最も小さい地点を見つければよい
n = int(input())
t, a = map(int, input().split())
ans, at = 0, float('inf')
for i, h in enumerate(map(int, input().split())):
tt = abs(t - h * 0.006 - a)
if at > tt:
ans = i + 1
at = tt
print(ans)
C - ID
問題
- $N$ 個の県に、全部で $M$ 個の市がある
- 県のIDは $1～N$ で振られている
- $i$ 番目の市は、IDが $P_i$ の県に属し、$Y_i$ 年に出来た
- 同じ年に出来た市は無い
- それぞれの市について、以下の命名規則によって決められるIDを求めよ
- 命名規則
- 数字からなる12桁
- 前半6桁は所属する県のID
- 後半6桁は所属する県の中でその市が出来た順番（1からの連番）
- 桁が満たない場合は0で埋める
例
県ID 出来た年 1 25 1 20 2 30 ↓ 1番目の市は、県1の中で2番目に出来たので、000001000002 2番目の市は、県1の中で1番目に出来たので、000001000001 3番目の市は、県2の中で1番目に出来たので、000002000001
解法
- 各市を県ごとに分類する
- 県ごとに、創設年でソートし、早い順にIDを決定していく
入力と出力の順番を合わせないといけないので、創設年でソートする際も、何番目の入力だったかを保持する必要がある。
Pythonならリストやタプルで(創設年, 入力順)と持たせておくと、ソートする際、まず創設年で比較し、同じ場合のみ入力順で比較される。今回は創設年は全て異なることが保証されているので、入力順は関係なくソートすることが出来る。
または、創設年が全て異なることを利用し、{創設年: 入力順}の逆引きdictを作っておいてもよい。やり方はいろいろある。
n, m = map(int, input().split())
cnt = [[] for _ in range(n + 1)]
for i in range(m):
p, y = map(int, input().split())
cnt[p].append((y, i))
buf = [None] * m
for p, l in enumerate(cnt):
if not l:
continue
l.sort()
for j, (y, i) in enumerate(l):
buf[i] = '{:06d}{:06d}'.format(p, j + 1)
print('\n'.join(buf))
Pythonの文字列整形について
- %表記
- Pythonの初期からある
- C言語のprintfとほぼ同じ表記で慣れた人にとっては覚えやすい
“%s is %02d years old.” % ('Tom', 6)“%(name)s is %(age)02d years old.” % {'name': 'Tom', 'age': 6}
- str.format()
- Python2の頃からある
- より多機能だが、覚えるのも大変（基本だけなら%表記と似ている）
“{name} is {age:02d} years old.”.format(name='Tom', age=6)
- f文字列
- Python3.6から（AtCoderでは使えない）
- str.format()と同じような書き方で、変数名を直接埋め込む形で書ける
name, age = 'Tom', 6f“{name} is {age:02d} years old.”
- （番外: str.zfill()）
- ゼロ埋め専用関数
D - Number of Amidakuji
問題
- 高さ $H+1$、縦棒 $W$ 本のあみだくじを作る
- 横棒の引き方のルール
- 横棒の端点となれるのは整数$(1,2,...,H)$地点のみ
- 隣り合った縦棒同士を結ぶ
- 同じ高さ同士を結ぶ（ナナメには引かない）
- 間隔は縦棒1つ以上空ける
- $(i-1,i)$番目の縦棒の間と$(i,i+1)$番目の縦棒の間に同時に横棒を引いてはいけない
- 最も左端の1番からスタートし、左から $K$ 番目に到達するような横棒の引き方を$\mod{10^9+7}$で求めよ
- $1 \le H \le 100$
- $1 \le W \le 8$
解法
日本人なら「あみだくじ」って言うとだいたいのルールは既知だけど、海外勢不利じゃないかと思ったり。
ルールをきちんとプログラムに落とし込み、さらにそれが $K$ に到達するかの判定がいかにも面倒そう。
ここはDPを用いる。
$dp_{h,i}=$上から$h～h+1$間の地点では、$i$番目の縦棒を通過するような、$h$までの横棒の引き方の数
1 2 3 4 5 |1 |0 |0 |0 |0 ←dp(0,i) 1 |---| | |---| |5 |3 |0 |0 |0 ←dp(1,i) 2 | |---| |---| |34 |24 |6 |0 |0 ←dp(2,i) ...
これは、以下の手順で遷移できる。
- $h～h+1$地点で$i$にいるためには、直前の$h-1～h$地点では$i-1,i,i+1$のいずれかにいないといけないので、この3つから遷移する。
- 干渉しない部分はどう引こうが自由なので、引き方の数だけ倍加する
$$dp_{h,i}=dp_{h-1,i-1}L_1R_1+dp_{h-1,i}L_2R_2+dp_{h-1,i+1}L_3R_3$$
足し合わせられている1番目の項が$i-1→i$への移動、2番目が$i→i$への移動、3番目が$i+1→i$への移動に対応する。
ここで$L,R$は、それぞれ左、右で干渉しない部分の、高さ$h$地点の横棒の引き方の数を示す。 これは左、右に縦棒が何本あるかで一意に決まる。
L1, R1
... o i-1 i o ...
| v | |
h | |->-| |
| | v |
└----┘ └----┘
L1 R1
L2, R2
... o i o ...
| v |
h | | |
| v |
└----┘ └----┘
L2 R2
縦棒の本数と引き方の数の関係は、フィボナッチ数列となる。なぜこうなるかは略。
| 縦棒の本数 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| 引き方の場合の数 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 |
これでDPを更新し、$dp_{H,K}$ が答え。
h, w, k = map(int, input().split())
dp = [1] + [0] * (w - 1)
facts = [1, 1, 2, 3, 5, 8, 13, 21, 34]
for _ in range(h):
ndp = [0] * w
for b in range(w):
if b > 0:
ndp[b] += dp[b - 1] * facts[b - 1] * facts[w - b - 1]
ndp[b] += dp[b] * facts[b] * facts[w - b - 1]
if b < w - 1:
ndp[b] += dp[b + 1] * facts[b] * facts[w - b - 2]
ndp[b] %= 1000000007
dp = ndp
print(dp[k - 1])
もしくは、フィボナッチ数列を使わず、この部分のみ全通り探索する方法でもよい。$2^{W-1}$ 通りのbit探索で数え上げられる。
2進数表記で、1なら横棒を引く、0なら引かないと対応させる。
1 2 3 4 5 6 7 8 |-| | |-| |-| | 1 0 0 1 0 1 0
ルールに違反しない横棒の引き方かどうかは、2進数表記を文字列にして'11'が出現するかどうか、またはi & (i << 1)が0でないかどうかで判断できる。
$i$ 番目の縦棒から $j$ 番目の縦棒へ遷移する場合の係数を、$W \times W$ の行列として作成する。
この係数は$h$に関わらず一定なので、最初に1回だけ計算しておけばよい。
この正方行列を$M$とすると、$dp_{h}=\{1,0,0,...,0\} \times M^h$ で求められる。
なので、累乗の高速化テクニックを使うとDP遷移部分は$O(W^3\log{H})$でも求めることが出来る。
