解説放送は無いそうです。
$X+Y/2$
バスのみ半額になるところとか問題文の読み取りミスに注意
x, y = map(int, input().split()) print(x + y // 2)
各候補地について平均気温を求めて、$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)
県ID 出来た年 1 25 1 20 2 30 ↓ 1番目の市は、県1の中で2番目に出来たので、000001000002 2番目の市は、県1の中で1番目に出来たので、000001000001 3番目の市は、県2の中で1番目に出来たので、000002000001
入力と出力の順番を合わせないといけないので、創設年でソートする際も、何番目の入力だったかを保持する必要がある。
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の文字列整形について
“%s is %02d years old.” % ('Tom', 6)“%(name)s is %(age)02d years old.” % {'name': 'Tom', 'age': 6}“{name} is {age:02d} years old.”.format(name='Tom', age=6)name, age = 'Tom', 6f“{name} is {age:02d} years old.”日本人なら「あみだくじ」って言うとだいたいのルールは既知だけど、海外勢不利じゃないかと思ったり。
ルールをきちんとプログラムに落とし込み、さらにそれが $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) ...
これは、以下の手順で遷移できる。
$$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})$でも求めることが出来る。