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

解法

  1. 各市を県ごとに分類する
  2. 県ごとに、創設年でソートし、早い順に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', 6
    • f“{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})$でも求めることが出来る。

programming_algorithm/contest_history/atcoder/2018/1104_abs113.txt · 最終更新: 2018/11/05 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0