A - Adjacent Product
問題
ACコード
n = int(input())
a = list(map(int, input().split()))
ans = [a[i] * a[i + 1] for i in range(n - 1)]
print(*ans)
B - Piano
問題
考えたこと
長さ12の文字列"wbwbwwbwbwbw"が周期的に表れるので、図１のように12回繰り返せばありうる文字列のすべてを列挙できます。
これらの文字列に対して、図２のように各状態における白鍵の数$W'$と黒鍵の数$B'$を列挙し、setに格納します。このsetの中に入力として与えられた$(W, B)$があるかどうかを判定することで問題が解けました。
ACコード
w, b = map(int, input().split())
s = "wbwbwwbwbwbw"
ans = set()
for i in range(len(s)):
s_ = s[i:] + s[:i]
cnt_w, cnt_b = 0, 0 # cnt_w, cnt_b = W', B'
while cnt_w <= 100 and cnt_b <= 100:
for c in s_:
if c == "w":
cnt_w += 1
else:
cnt_b += 1
ans.add((cnt_w, cnt_b))
print("Yes" if (w, b) in ans else "No")
C - Σ
問題
考えたこと
$1$から$K$までの総和から$A$の各要素$a_i$に対して、$K$以下のものを引いていけばよさそうですが、重複するもあるのでsetで重複をなくしました。また、総和は下式のように求めることで大幅に計算量が抑えられます。
$$ 1 + 2 + \dots + K = \frac{(1 + K)K}{2}$$
ACコード
n, k = map(int, input().split())
A = set(map(int, input().split()))
ans = (1 + k) * k // 2
for a in A:
if a <= k:
ans -= a
print(ans)
D - Gomamayo Sequence
問題
考えたこと
まず、どのようにすれば良い文字列を作れるか考えます。結論としては、$010101 \cdots$と$101010 \cdots$という文字列を考えて、これらを図３のように合体させることで良い文字列を作ることができます。
次にコスト計算ですが、元の文字列に対してそれぞれ青下線部、オレンジ下線部に変形するコストを求めてそれらの和をとればよさそうです。
まず、前側のコスト算出方法です。こちらは素直に$010101 \cdots$と$101010 \cdots$ともに$1$文字目から$i$文字目までのコストを求めていきます。入力例１でいうと、
\begin{align}
00011 \rightarrow 01010のコストAは、A &= [0, 0, 9, 9, 9, 13] \\
00011 \rightarrow 10101のコストBは、B &= [0, 3, 3, 5, 11, 11]
\end{align}
となります。（$A[0]、B[0]$は和をとるときの実装を楽にするため導入したものです。$A[1]、B[1]$が1文字目に対応しています。）
後ろ側のコストは、
\begin{align}
&i + 1文字目からn文字目までのコスト= \\
&1文字目からn文字目までのコスト - 1文字目からi文字目までのコスト
\end{align}
で算出することができます。実際の算出を図４で行っているので参考にしてください。
これをすべての良い文字列に対して行い、最小値を求めていくことで解けました。
ACコード
n = int(input())
s = input()
C = list(map(int, input().split()))
# 順にA, Bに対応しています
zero_one, one_zero = [0 for _ in range(n + 1)], [0 for _ in range(n + 1)]
for i in range(1, n + 1):
zero_one[i] = zero_one[i - 1]
one_zero[i] = one_zero[i - 1]
if ((i - 1) % 2 == 0 and s[i - 1] == "1") or ((i - 1) % 2 == 1 and s[i - 1] == "0"):
zero_one[i] += C[i - 1]
else:
one_zero[i] += C[i - 1]
ans = float("inf")
for i in range(1, n):
tmp1 = zero_one[i] + (one_zero[-1] - one_zero[i])
tmp2 = one_zero[i] + (zero_one[-1] - zero_one[i])
ans = min(ans, tmp1, tmp2)
print(ans)
E - Paint
問題
考えたこと
鉄則本を読んだ人はわかると思うのですが、そこに書いてあった色塗りの問題は後ろから考えて解いていました。（そもそも色塗りの問題は後ろから考えるのが常套手段なのか？）
そのことを覚えていたので、今回も後ろから考えることで解くことができました。
後ろからのクエリの実行は図５のように考えていっており、後ろからのクエリにおいて前に実行した色を上塗りしないよう、塗っていくことでうまくいきます。
コードに落とし込むためには、以下の二つを気を付けました。
- すでに塗られている行、すでに塗られている列の数を数えておく
- 行を塗るなら、Wからすでに塗られている列の数を引けば個数を算出できる
- すでに塗られている行、列を覚えておく
- 上塗りしないようにできる
- 塗られていないものを最後に数え上げる
ACコード
from collections import defaultdict
h, w, m = map(int, input().split())
query = [list(map(int, input().split())) for _ in range(m)]
query = query[::-1]
colors = defaultdict(int)
# すでに塗られている行、すでに塗られている列を覚えておく
is_row_filled, is_col_filled = [0] * h, [0] * w
# すでに塗られている行の数、すでに塗られている列の数
cnt_row, cnt_col = 0, 0
for i in range(m):
t, a, x = query[i]
a -= 1
if t == 1 and is_row_filled[a] != 1:
colors[x] += w - cnt_col
cnt_row += 1
is_row_filled[a] = 1
elif t == 2 and is_col_filled[a] != 1:
colors[x] += h - cnt_row
cnt_col += 1
is_col_filled[a] = 1
filled_cnt = sum(colors.values())
# 塗られていないものを数え上げ、追加
colors[0] += h * w - filled_cnt
# ソート兼要素が0のものを削除
colors = sorted((color, cnt) for color, cnt in colors.items() if cnt > 0)
print(len(colors))
for color in colors:
print(*color)
感想
B、Dあたりは力づくで解いた気がしたのですが、解説に近いものがあり少し安心しました。
積本がえぐいことになっているので早く消化せねば・・・。