参加したけど記録を書いてなかったので、とりあえず D まで解いた現時点での記録を書いていきます。
ABC129 A – Airplane
空港 \(A, B, C\) があり、それぞれの空港の間では、双方向に飛行機が運航しています。
https://atcoder.jp/contests/abc129/tasks/abc129_a
空港 \(A, B\) 間の飛行時間は片道 \(P\) 時間、空港 \(B, C\) 間の飛行時間は片道 \(Q\) 時間、空港 \(C, A\) 間の飛行時間は片道 \(R\) 時間です。
いずれかの空港からスタートして他の空港に飛行機で移動し、さらにそのどちらでもない空港に飛行機で移動するような経路を考えます。
飛行時間の和は最短で何時間になるでしょうか。
経路が3通り考えられるので、その最小値を求めれば良いだけです。
回答案
以下のコードで Python3 で 20 ms で AC でした。
P, Q, R = map(int, input().split())
print(min(P + Q, Q + R, R + P))ABC129 B – Balance
\(1\) から \(N\) の番号がついた \(N\) 個の重りがあり、番号 \(i\) の重りの重さは \(W_i\) です。
https://atcoder.jp/contests/abc129/tasks/abc129_b
ある整数 \(1 \leq T < N\) に対してこれらの重りを、番号が \(T\) 以下の重り と 番号が \(T\) より大きい重りの 2 グループに分けることを考え、それぞれのグループの重さの和を \(S_1, S_2\) とします。
このような分け方全てを考えた時、\(S_1\) と \(S_2\) の差の絶対値の最小値を求めてください。
制約を見てみると、 \(N\) が 100 以下なので愚直に全部調べてもいけそう。ということで何も考えずに全探索しました。
回答案
以下のコードで Python3 で 17 ms で AC でした。
N = int(input())
*W, = map(int, input().split())
s1, s2 = 0, sum(W)
ans = sum(W)
for i in range(N):
s1 += W[i]
s2 -= W[i]
ans = min(ans, abs(s1 - s2))
print(ans)ABC129 C – Typical Stairs
\(N\) 段の階段があります。高橋君は現在、上り口( \(0\) 段目)にいます。 高橋君は一歩で \(1\) 段か \(2\) 段上ることができます。ただし、\(a_1, a_2, a_3, …, a_M\) 段目の床は壊れており、その段に足を踏み入れることは危険です。
https://atcoder.jp/contests/abc129/tasks/abc129_c
壊れている床を踏まないようにしながら、最上段( \(N\) 段目)にたどりつくまでの移動方法は何通りあるでしょうか？ 総数を \(1,000,000,007\) で割った余りを求めてください。
壊れた床がない場合はフィボナッチになりますね。
たとえば、壊れた床がないとして \(n\) 段目までの行き方を \(f_n\) とすれば、 \(n\) 段目までの行き方を次のように場合分けをすることで、漸化式を得ることができます。
- \(n – 1\) 段目を踏む場合の \(f_{n – 1}\) 通り
- \(n – 1\) 段目を踏まない場合の \(f_{n – 2}\) 通り
\(f_n = f_{n – 1} + f_{n – 2}\)
あとはこれを応用して考えてみます。壊れた床の前後で分割して考えれば、例えば次のように細かいフィボナッチ数の積で考えられますね。 \(f_0 = 0\) とすれば、壊れた床が2つ続く場合も対応できますね。
フィボナッチ数は計算スピードが少し怖かったので gg って高速で計算できそうなアルゴリズムを見つけてパク真似させていただきました。まぁ行列使うとうまくいくよねっていう感じで、細かい話は下の記事を御覧ください。
回答案1
以下のコードで Python3 で 232 ms で AC でした。
from itertools import product
INF = 1000000007
def mat2_mul(X, Y):
z = [[0, 0], [0, 0]]
for (i, j, k) in product(range(2), range(2), range(2)):
z[i][j] += X[i][k] * Y[k][j]
return z
def mat2_pow(X, n):
if n == 0:
return [[1, 0], [0, 1]]
elif n % 2:
return mat2_mul(X, mat2_pow(X, n - 1))
else:
half_pow = mat2_pow(X, n / 2)
return mat2_mul(half_pow, half_pow)
def fib(n):
if n == 0:
return 0
else:
f = [[0, 1], [1, 1]]
return mat2_pow(f, n - 1)[1][1]
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
ans, start = 1, 0
for k in a:
ans *= fib(k - start)
ans %= INF
start = k + 1
ans *= fib(N - start + 1)
print(ans % INF)とても長いですが、前半はフィボナッチの定義してるだけです。
DP (動的計画法)
動的計画法を使うのが想定解だそう。下から上に dp の中を計算しながら、うまく処理して a のときは 0 通りにすればOKですね。こんな感じになります。
回答案2
以下のコードで Python3 で 176 ms で AC でした。
N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
INF = 1000000007
dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
dp[1] = 1
else:
dp[1] = 0
for i in range(2, N + 1):
if i in a:
continue
dp[i] = dp[i - 1] + dp[i - 2]
dp[i] %= INF
print(dp[N])DP に関しては、自分もまだ理解が浅いので、AtCoder の DP まとめコンテスト (https://atcoder.jp/contests/dp) とかを解き進めていこうと思った次第です。
ABC129 D – Lamp
縦 \(H\) 行横 \(W\) 列のグリッドが与えられます。このグリッドのうち、いくつかのマスには障害物が存在します。
https://atcoder.jp/contests/abc129/tasks/abc129_d
すぬけ君は、障害物のないマスのうち一つを選び、そのマスに明かりを設置しようとしています。 設置されたマスから、上下左右の四方向にまっすぐに光線が伸びます。それぞれの方向について、最初に障害物が存在するマスにぶつかる、もしくはグリッドの端にぶつかる手前のマスまで照らされます。明かりを設置したマスも照らされますが、障害物が存在するマスは照らされません。
すぬけ君は明かりによって照らされるマスの個数を最大化したいです。
\(H\) 個の長さ \(W\) の文字列 \(S_i\) \((1 \leq i \leq H )\) が与えられます。\(S_i\) の \(j\) 文字目 \((1 \leq j \leq W )\) が"#"のとき、グリッドの上から \(i\) 行目で左から \(j\) 列目のマスには障害物があり、"."のときは障害物がありません。
照らされるマスの個数の最大値を求めてください。
コンテストでは 残り10分で D に到達して、適当に書いているうちに終了みたいな感じでしたが考えてみます。
\(S_{i j}\) のそれぞれについてマスを数える方針だと TLE になってしまうので、先にマスを数えておきます。数える方向は上下左右の 4 方向ですから、
L[i][j]: 左の照らせるマスの個数R[i][j]: 右の照らせるマスの個数D[i][j]: 下の照らせるマスの個数U[i][j]: 上の照らせるマスの個数
と分割して、
X[i][j] = L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3 とすれば大丈夫そうですね。
具体例
入力例 2 にある例で具体的に考えてみます。
8 8
..#...#.
....#...
##......
..###..#
...#..#.
##....#.
#...#...
###.#..#
となるので、 X[i][j] は次のようになります。
回答案
以下のコードで PyPy3 で 1067 ms で AC でした。
H, W = map(int, input().split())
S = [input() for _ in range(H)]
# そのマスを含めてLeft, Right, Up, Downにそれぞれ何マス分明かりを照らせるかを配列に記録
L = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]
for i in range(H):
for j in range(W):
if S[i][j] == ".":
if j == 0:
L[i][j] = 1
else:
L[i][j] = L[i][j - 1] + 1
for i in range(H):
for j in range(W - 1, -1, -1):
if S[i][j] == ".":
if j == W - 1:
R[i][j] = 1
else:
R[i][j] = R[i][j + 1] + 1
for j in range(W):
for i in range(H - 1, -1, -1):
if S[i][j] == ".":
if i == H - 1:
D[i][j] = 1
else:
D[i][j] = D[i + 1][j] + 1
for j in range(W):
for i in range(H):
if S[i][j] == ".":
if i == 0:
U[i][j] = 1
else:
U[i][j] = U[i - 1][j] + 1
ans = 0
X = [[0] * W for _ in range(H)]
for i in range(H):
for j in range(W):
X[i][j] = L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3
ans = max(ans, max(X[i]))
print(ans)