ABC354 with Python (A～E)

ABC354のA~E問題をpythonで解説していきます。筆者は途中参加で、A-Eの5完でした。

A - Exponential Plant

問題

高橋君は植物を育てています。その植物の発芽時の高さは $0\space \mathrm{cm}$ です。発芽した日を $0$ 日目としたとき、発芽してから $i (0 \le i)$ 日目の夜には $2^i\space\mathrm{cm}$ 植物の高さが伸びます。
高橋君の身長は $H\space\mathrm{cm}$ です。
高橋君は毎朝この植物と背比べをします。植物の高さが高橋君の身長より高くなるのは発芽から何日目の朝か求めてください。

考察

問題文通り植物の高さを伸ばしていき、高橋君の身長を超えたタイミングでその日付を出力すればよいです。実装にはwhile文を用いました。

コード

A.py

H = int(input())
now = 0
date = 0
while now <= H:
    now += 1 << date
    date += 1
print(date)

B - AtCoder Janken 2

問題

$N$ 人の AtCoder ユーザーが集まり、AtCoderじゃんけん2 を行います。$i$ 人目のユーザー名は $S_i$ 、レートは $C_i$ です。

AtCoderじゃんけん2 は以下の手順で行われます。

• それぞれのユーザーに、ユーザー名の辞書順に $0, 1, \dots ,N - 1$ の番号を割り当てる。
• $N$ 人のレートの総和を $T$ とする。番号 $T \bmod N$ を割り当てられたユーザーが勝者となる。

勝者のユーザー名を出力してください。

辞書順とは？

辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、英小文字からなる相異なる文字列 $S, T$ の大小を判定するアルゴリズムを以下に説明します。

以下では「 $S$ の $i$ 文字目の文字」を $S_i$ のように表します。また、 $S$ が $T$ より辞書順で小さい場合は $S \lt T$ 、大きい場合は $S \gt T$ と表します。

1. $S, T$ のうち長さが大きくない方の文字列の長さを $L$ とします。$i=1,2,\dots,L$ に対して $S_i$ と $T_i$ が一致するか調べます。
2. $S_i \neq T_i$ である $i$ が存在する場合、そのような $i$ のうち最小のものを $j$ とします。そして、$S_j$ と $T_j$ を比較して、$S_j$ が $T_j$ よりアルファベット順で小さい場合は $S \lt T$ 、そうでない場合は $S \gt T$ と決定して、アルゴリズムを終了します。
3. $S_i \neq T_i$ である $i$ が存在しない場合、$S$ と $T$ の長さを比較して、$S$ が $T$ より短い場合は $S \lt T$ 、長い場合は $S \gt T$ と決定して、アルゴリズムを終了します。

考察

ユーザー名で辞書順にソート + レートの総和の$mod\space N$が計算できればよいです。実装はコードを参照してください。

コード

B.py

N = int(input())
S = []
C = []
for _ in range(N):
    s, c = map(str, input().split())
    c = int(c)
    S.append(s)
    C.append(c)
S.sort()
print(S[sum(C) % N])

C - AtCoder Magics

問題

高橋くんは、カードゲーム「AtCoder Magics」のカードを $N$ 枚持っています。$i$ 番目のカードをカード $i$ と呼ぶことにします。各カードには強さとコストのパラメーターがあり、カード $i$ の強さは $A_i$ で、コストは $C_i$ です。

高橋くんは、弱いカードは要らないので捨てることにしました。具体的には、以下の操作をできなくなるまで繰り返します。

• $2$ つのカード $x, y$ であって、 $A_x > A_y$ かつ $C_x < C_y$ であるようなものを選ぶ。カード $y$ を捨てる。

操作ができなくなったとき、捨てられなかったカードの集合は一意に定まることが証明できます。これを求めてください。

考察

強さの値が小さい&コストが高い　カードがいらないので、強さの値が大きい順になるようにカードをソートして、今まで見てきたコストの最小値よりコストが大きいかどうかをチェックすればよいです。コストが大きければ、それは強さの値が小さいにもかかわらずコストが高いという意味なので、そのカードは捨てればよいということです。

コード

C.py

INF = float("inf")
N = int(input())
AC = []
for i in range(N):
    a, c = map(int, input().split())
    AC.append((-a, c, i))
AC.sort()
cost = INF
ok = []
for _, c, idx in AC:
    if c > cost:
        continue
    cost = c
    ok.append(idx + 1)
ok.sort()
print(len(ok))
print(*ok)

D - AtCoder Wallpaper

問題

AtCoder 社の壁紙の模様を $xy$ 平面上に表現すると、以下のようになります。

• 以下の $3$ 種類の直線で領域が分割されている。
  • $x = n$ ($n$ は整数)
  • $y = n$ ($n$ は偶数)
  • $x + y = n$ ($n$ は偶数)
• 各領域は白もしくは黒で塗られている。いずれかの直線で隣接する $2$ 領域は異なる色で塗られている。
• $(0.5, 0.5)$ を含む領域は黒で塗られている。

下の図は、模様の一部を表したものです。

整数 $A, B, C, D$ が与えられます。各辺が $x, y$ 軸に平行で、左下の頂点が $(A, B)$ にあり右上の頂点が $(C, D)$ にあるような長方形を考えます。この長方形の内側に存在する黒で塗られた領域の面積を求め、それを $2$ 倍したものを出力してください。

出力する値は整数になることが証明できます。

考察

この模様は、左下を$(0,0)$、右上を$(4,2)$とする長方形の模様の繰り返しになっていることが図を観察するとわかります。簡単のためこの長方形を下(even)と上(odd)の2つの長方形にわけ、それぞれのx座標で黒の三角形(1x1の正方形の半分)が何個あるかの情報を配列で持っておきます。
あとは少し実装が重いですが、これを使って範囲内の黒色の三角形の個数を数えればそれがそのまま答えとなります(この三角形は面積を2倍するとちょうど1になるため)。

コード

D.py

A, B, C, D = map(int, input().split())
even = [2, 1, 0, 1]
even += even
odd = [1, 2, 1, 0]
odd += odd

s = A % 4
if C - A <= 4 - s:
    EVEN = sum(even[s : s + C - A])
    ODD = sum(odd[s : s + C - A])
else:
    EVEN = sum(even[s:4])
    ODD = sum(odd[s:4])
    tmp = C - A - (4 - s)
    p, r = divmod(tmp, 4)
    EVEN += 4 * p + sum(even[:r])
    ODD += 4 * p + sum(odd[:r])

t = B % 2
cnt = (D - B + 1) // 2

ans = 0
if t % 2 == 0:
    ans += EVEN * cnt
    ans += ODD * (D - B - cnt)
else:
    ans += ODD * cnt
    ans += EVEN * (D - B - cnt)
print(ans)

E - Remove Pairs

問題

高橋君と青木君は $N$ 枚のカードを使ってとあるゲームをします。$i$ 枚目のカードの表面には $A_i$ が、裏面には $B_i$ が書かれています。初めに場には $N$ 枚のカードが並べられており、高橋君を先手として、$2$ 人は以下の操作を交互に繰り返します。

• 場にあるカードの中から表面同士に同じ数が書かれている、または裏面同士に同じ数が書かれている $2$ 枚のカードの組を選び、そのカードを場から取り除く。このようなカードの組が存在しない場合、操作を行えない。

先に操作を行えなくなった方が負けとなり、もう一方が勝ちとなります。両者がそれぞれ勝つために最適な操作を選ぶ時、どちらが勝つか求めてください。

考察

$N \leq 18$という制約からbit全探索的な手法を使うことができるとわかります。再帰で全探索してもいいのですが、pythonは関数呼び出しが遅いという特徴があるので、今回はbit DPで実装することにします。
$dp[s]:今残りカードがsの状態であるとき、先手は勝つことができるか(1=勝ち, 0=負け)$
というdpを考えれば、あとは移動先のdpで一つでも$0$が存在すれば勝てるので$1$、そうでなければ勝てないので$0$とすればよいです。

コード

E.py

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N)]

dp = [0] * (1 << N)
for S in range(1 << N):
    for i in range(N):
        if (S >> i) & 1:
            continue
        a1, b1 = AB[i]
        for j in range(N):
            if (S >> j) & 1 or i == j:
                continue
            a2, b2 = AB[j]
            if a1 != a2 and b1 != b2:
                continue
            dp[S | (1 << i) | (1 << j)] |= dp[S] ^ 1
if dp[-1]:
    print("Takahashi")
else:
    print("Aoki")