AtCoder Beginners Contest 322 (ABC322) をPythonで解きました。
見やすいコードを書く練習も兼ねてます。
A - First ABC 2
問題ページ
考察
$0$ ～ $2$ 文字目が "ABC" かどうかを見る
→ $1$ ～ $3$ 文字目が "ABC" かどうかを見る
→ $2$ ～ $4$ 文字目が "ABC" かどうかを見る
$\cdots$
と見ていきます。どこかで "ABC" があったら、そのインデックスを出力してプログラムをexit()で強制終了します。(左端のインデックスを $0$ として数えていたので、答えは $1$ だけプラスするのを忘れないように！)
最後まで見つからなかったら、 $-1$ を出力しておしまいです。
コード
N = int(input())
S = input()
for i in range(N - 2):
if S[i:i + 3] == 'ABC':
print(i + 1)
exit()
print(-1)
別解
findメソッドをつかった解法
findメソッドは、引数の文字列があるインデックスを返してくれます。
もし 見つけたい文字列が全体の中に $2$ つ以上 あったら、左端の文字列のインデックスを返してくれます。
もし引数の文字列がなかった場合、findメソッドは $-1$ を返してくれます。
"""findメソッドの使用例"""
S = "WeSingABCandABC"
idx = S.find("ABC") # 6
idx2 = S.find("CDE") # -1
似たものとしてindexメソッドがあります。
もし引数の文字列がなかった場合、indexメソッドはValueErrorを起こします。今回の問題ではfindメソッドの方が使い勝手がよさそうです。
"""indexメソッドの使用例"""
S = "WeSingABCandABC"
idx = S.find("ABC") # 6
idx2 = S.find("CDE") # ValueErrorを起こす。
"""findメソッドをつかった解答例"""
N = int(input())
S = input()
idx = S.find("ABC")
if idx == -1:
print(-1)
else:
print(idx + 1)
B - Prefix and Suffix
問題ページ
考察
文字列の一部分だけを取り出すのは、こんな感じで書けます。
S = "AtCoder"
t1 = S[:4] # AtCo (左端から右へ見ていって、S[4]の1つ手前まで)
t2 = S[3:] # oder (S[3]から右へ見ていって、最後の文字まで)
また、負の数をインデックスに入れることもできます。
S = "AtCoder"
p1 = S[-3] # d (右端を-1として、左に1つ動かすごとに-1する)
p2 = S[-3:] # der (負の数をつかって文字列の一部分を取り出すこともできる)
これをつかうと、先頭 $N$ 文字を取り出すのと、末尾 $N$ 文字を取り出すのは、次のように書けます。
S = "PythonIsGood"
a1 = S[:4] # Pyth(先頭4文字)
a2 = S[-6:] # IsGood(末尾6文字)
答えは $4$ 通りあって、if文などの条件分岐が必要ですが、match文をつかえば見た目的にも簡単に書けてオススメです。
コード
N, M = map(int, input().split())
S = input()
T = input()
f1 = S == T[:N] # 接頭辞ならTrue
f2 = S == T[-N:] # 接尾辞ならTrue
match (f1, f2):
case (True, True): print(0)
case (True, False): print(1)
case (False, True): print(2)
case (False, False): print(3)
C - Festival
問題ページ
考察
競プロでよくある考え方の一つに、「逆から見てみる」というのがあります。
今回の問題は完全にそれで、最後の日にちから順に最初の日にちまで見ていきます。
- $ans[i]$ : $i$ 日目から最短で花火が上がるまでの日数
として、このリストを後ろから決めていきます。
リスト $ans$ の初期設定として、花火が上がる日にちはあらかじめ分かっているので、その日は値を $0$ にしておきます。また、それ以外の日は $0$ 以外の数を入れておきます。
すると、最終日( $N-1$ 日目)は花火が上がるのでいいとして、それ以外の $0$ ～ $N-2$ 日目に関して次の式が成り立ちます。
- $ans[i] \neq 0$ のとき、 $ans[i] = ans[i+1] + 1$
$N-2$ 日目から見ていくので、 $ans[i]$ を求めるときにつかう $ans[i+1]$ はすでに求まっている状態で計算できます。($0$ 日目から見ていくと、間違った計算結果になってしまいます。)
コード
N, M = map(int, input().split())
A = list(map(int, input().split()))
ans = [10] * N
for a in A:
ans[a - 1] = 0
for i in range(N - 2, -1, -1):
if ans[i] != 0:
ans[i] = ans[i + 1] + 1
for a in ans:
print(a)
D - Polyomino
問題ページ
考察
3つのポリオミノそれぞれに対して、回転・平行移動をして作れるポリオミノをすべて列挙します。
(1つ目のポリオミノから作れるポリオミノ)、(2つ目のポリオミノから作れるポリオミノ)、(3つ目のポリオミノから作れるポリオミノ)の組み合わせを全パターン試して、どれか1つでもうまく全マスを埋められるものがあればYes、1つもなければNoを出力すればいいです。
理屈としては簡単ですが、実装がとにかくしんどいです。
やってることはたくさんあって、
- ポリオミノを回転させた新たなポリオミノを求める
- 上下左右に平行移動したポリオミノをすべて求める
- 3つのポリオミノで全マスを埋められるかどうかを求める
大きく分けると、この3つのことをします。
簡単なのに実装重い系の問題は、関数をつくって小分けにするのがオススメです。
この量のコードを打ってバグなく1発でACする方が稀です(hyouchun調べ)。バグが出たときに修正する箇所も分かりやすくなるし、コードを書いているときも何をしているのかがスッキリしてやりやすいです。
(細かいところは下の実装例を見てください。)
コード
# 時計回りに90度だけまわしたものを返す
def rotate90(grid):
return list(zip(*reversed(grid)))
# これでもok
# def rotate90(grid):
# ret = [['.'] * 4 for _ in range(4)]
# for i in range(4):
# for j in range(4):
# ret[i][j] = grid[j][3 - i]
# return ret
# 上下に平行移動できるものをすべて格納したリストを返す。
def pattern_row(grid):
ret = [grid]
for i in range(3):
if '#' in grid[i]:
break
nex = [['.'] * 4 for _ in range(4)]
for ii in range(i + 1, 4):
for jj in range(4):
nex[ii - i - 1][jj] = grid[ii][jj]
ret.append(nex)
for i in range(3, 0, -1):
if '#' in grid[i]:
break
nex = [['.'] * 4 for _ in range(4)]
for ii in range(i):
for jj in range(4):
nex[ii + (4 - i)][jj] = grid[ii][jj]
ret.append(nex)
return ret
# 左右に平行移動できるものをすべて格納したリストを返す。
def pattern_col(grid):
def all_dot(g, nj):
for i in range(4):
if g[i][nj] == '#': return False
return True
ret = [grid]
for j in range(3):
if not all_dot(grid, j):
break
nex = [['.'] * 4 for _ in range(4)]
for ii in range(4):
for jj in range(j + 1, 4):
nex[ii][jj - j - 1] = grid[ii][jj]
ret.append(nex)
for j in range(3, 0, -1):
if not all_dot(grid, j):
break
nex = [['.'] * 4 for _ in range(4)]
for ii in range(4):
for jj in range(j):
nex[ii][jj + (4 - j)] = grid[ii][jj]
ret.append(nex)
return ret
# 上下左右に平衡移動してできるものすべてを格納したリストを返す。
def pattern_all(grid):
ret = []
for p1 in pattern_row(grid):
for p2 in pattern_col(p1):
ret.append(p2)
return ret
# 回転・上下左右の平行移動をしてできるものすべてを格納したリストを返す。
def pattern_rotate_all(grid1):
grid2 = rotate90(grid1)
grid3 = rotate90(grid2)
grid4 = rotate90(grid3)
ret = []
for grid_r in [grid1, grid2, grid3, grid4]:
for grid in pattern_all(grid_r):
ret.append(grid)
return ret
# この3つで、衝突なしで全部のマスを埋められたらTrue
def is_ok(p1, p2, p3):
grid = [[False] * 4 for _ in range(4)]
for p in [p1, p2, p3]:
for i in range(4):
for j in range(4):
if p[i][j] == '#':
if not grid[i][j]:
grid[i][j] = True
else:
return False
for i in range(4):
for j in range(4):
if not grid[i][j]:
return False
return True
Ps = []
for _ in range(3):
P = [list(input()) for _ in range(4)]
Ps.append(P)
A = []
for grid in Ps:
A.append(pattern_rotate_all(grid))
for p1 in A[0]:
for p2 in A[1]:
for p3 in A[2]:
if is_ok(p1, p2, p3):
print("Yes")
exit()
print("No")
E - Product Development
問題ページ
考察
問題の制約に $1 \leqq K,P \leqq 5$ とあります。
最悪の場合を考えて、パラメータの個数が $K=5$ で、パラメータの値をすべて $P=5$ 以上にしたいとします。
パラメータの値が $6$ 以上のときもパラメータの値を $5$ にすることにすると、
- パラメータの個数: $5$ 個
- パラメータの取りうる値の数: ( $0,1,2,3,4,5$ で) $6$ 個
なので、パラメータの取り方は全部で $6^5=7776$ 通りです。
1つの開発案で $7776$ 通りのパラメータすべてを更新します。そして、開発案の個数 $N$ は $N \leqq 100$ なので、ざっと計算するのは $7776000 \leqq 10^7$ 回くらいです。これなら実行時間に間に合います。
$K$ 個あるパラメータをリストにして、それを辞書のキーにして解いてもいいですが、そこそこ遅くなってしまいます。(今回の問題は実行時間の制限が4秒になっていて、この方法でもかなり余裕でACできます)
下のコード例では、 $K$ 個あるパラメータのリストを $P+1$ 進数の数に見立てて、それを $10$ 進数にしたものをつかって解いています。
コード
def lst2int(lst):
val = 0
for i, el in enumerate(lst):
val += el * ((P + 1) ** i)
return val
def int2lst(v):
ret = []
val = v
for _ in range(K):
val, mo = divmod(val, P + 1)
ret.append(mo)
return ret
N, K, P = map(int, input().split())
dp = [1 << 40] * ((P + 1) ** K)
dp[0] = 0
for _ in range(N):
c, *A = map(int, input().split())
nex = dp[:]
for i, cost in enumerate(dp):
lst = int2lst(i)
nex_lst = [min(el1 + el2, P) for el1, el2 in zip(A, lst)]
nex_int = lst2int(nex_lst)
nex[nex_int] = min(nex[nex_int], cost + c)
dp = nex
if dp[-1] >= 1 << 40:
dp[-1] = -1
print(dp[-1])
おまけ (F問題)
問題ページ
考察
遅延セグメントツリーの問題です。
TLEしますが、Python版のACLをつかったコードです。公式解説の通りに実装していて、同じ実装をRustで提出したら180msでACできているので、おおまかな解法は間違っていないはずです(たぶん)。
もう少し工夫すればACできるかもしれないんですが、遅延セグメントツリーが重くて他の問題でもしんどいがちなので、C++やRustで書けるようになる方がいい気がします。
import sys
from atcoder.lazysegtree import LazySegTree
from dataclasses import dataclass
@dataclass()
class Monoid:
m0: int
m1: int
l0: int
l1: int
r0: int
r1: int
s: int
def swapped_monoid(monoid: Monoid) -> Monoid:
m0, m1 = monoid.m1, monoid.m0
l0, l1 = monoid.l1, monoid.l0
r0, r1 = monoid.r1, monoid.r0
s = monoid.s
return Monoid(m0, m1, l0, l1, r0, r1, s)
# TODO (区間演算opの単位元)
e = Monoid(0, 0, 0, 0, 0, 0, 0)
# 区間演算
def op(ele1: Monoid, ele2: Monoid) -> Monoid:
m0 = max(ele1.m0, ele2.m0, ele1.r0 + ele2.l0)
m1 = max(ele1.m1, ele2.m1, ele1.r1 + ele2.l1)
l0 = ele1.s + ele2.l0 if ele1.l0 == ele1.s else ele1.l0
l1 = ele1.s + ele2.l1 if ele1.l1 == ele1.s else ele1.l1
r0 = ele1.r0 + ele2.s if ele2.r0 == ele2.s else ele2.r0
r1 = ele1.r1 + ele2.s if ele2.r1 == ele2.s else ele2.r1
s = ele1.s + ele2.s
return Monoid(m0, m1, l0, l1, r0, r1, s)
def mapping(func: int, ele: Monoid):
if func:
return swapped_monoid(ele)
else:
return ele
def composition(func_upper: int, func_lower: int) -> int:
return (func_upper + func_lower) & 1
# mapping(func, ele) = ele となるようなfunc
id_ = 0
readline = sys.stdin.readline
N, Q = map(int, readline().split())
S = input()
monoid0 = Monoid(1, 0, 1, 0, 1, 0, 1)
monoid1 = Monoid(0, 1, 0, 1, 0, 1, 1)
v = [monoid1 if int(s) else monoid0 for s in S]
lazy_segtree = LazySegTree(op, e, mapping, composition, id_, v)
for _ in range(Q):
c, l, r = map(int, readline().split())
l -= 1
match c:
case 1:
lazy_segtree.apply(l, r, 1)
case 2:
ans = lazy_segtree.prod(l, r).m1
print(ans)