−目次

AtCoder Beginner Contest 113
- A - Discount Fare
  - 問題
  - 解法
- B - Palace
  - 問題
  - 解法
- C - ID
  - 問題
  - 例
  - 解法
- D - Number of Amidakuji
  - 問題
  - 解法

AtCoder Beginner Contest 113

解説放送は無いそうです。

解説pdf: https://img.atcoder.jp/abc113/editorial.pdf

chokudai(高橋直大)さんのツイート: "今日は強行開催なので鯖が半分だったり色々怪しいんでごめんなさい＞＜先日から発信し続けてた通り、AtCoder社員全員不在でサポートはほぼ出来ないのでご了承ください！（勝手にUnrated判断しても責任は取れません！ごめんなさい！）"

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の新しい文字列フォーマット : %記号、str.format()から文字列補完へ | POSTD
%表記
- 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})$ でも求めることが出来る。