競プロ初心者の復習用記事です。
参加したコンテストはこちら↓。
https://atcoder.jp/contests/panasonic2020
ここで書くコードは他の人の解答や解説を見ながら書いたものです。実際に提出したものではありません。
A - Kth Term
事前に決められた数列から与えられた入力n番目の項を出力する問題です。
li = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
i = int(input())
print(li[i-1])
項の番号は1から数えていることだけ注意。
B - Bishop
$H\times W$マスの盤面で角が動ける範囲を答える問題です。
横か縦のサイズが1しかないとき角は一歩も動けないので注意しましょう（一敗）。
提出したコードはこんな感じです。
import math
H, W = map(int, input().split())
if H == 1 or W == 1:
print(1)
else:
w_odd = math.ceil(H/2)
w_even = H // 2
N_odd = math.ceil(W/2)
N_even = W // 2
print(w_odd * N_odd + w_even * N_even)
横のマス目を左から数えて偶数番目の時と奇数番目の時で移動可能なマスの数は異なります。この二つの場合のマスの数と、それぞれが該当する列の数を別々に求めました。
実際にはもっと簡潔に書けます。
単純に全てのマスのうち半分は移動可能な範囲です。さらに2で割って余りが生じる場合、余りである右下のマスは必ず(奇数、奇数)の位置にあります。それは移動可能な位置なのでさらに一マス増えます。
H, W = map(int, input().split())
if H == 1 or W == 1:
print(1)
else:
print((H * W + 1) // 2)
あと、切り上げ処理にmathをインポートする必要もないですね。
C - Sqrt Inequality
入力A B Cに対して
$$\sqrt{A} + \sqrt{B} < \sqrt C \tag{1}$$
であるかを判定する問題。
ダメだろうなーって思いつつ以下を提出しました。
a, b, c = map(int, input().split())
if a**0.5 + b**0.5 < c**0.5:
print("Yes")
else:
print("No")
ダメでした。mathを使う場合も駄目。
(1)式の両辺を2乗してみます。
$$A + 2\sqrt{AB} +B < C \tag{2}$$
これも駄目。諦めました。平方根の計算で何か誤差が出るんだろうなあとは思うんですが、その手の知識がありません。
解説を見ました。(2)式をさらに変形させます。
$$ 2\sqrt{AB} < C - A - B$$
この両辺が正である時、両辺を二乗して
$$ 4AB < (C - A - B)^2 $$
が成立します。これで平方根の計算が消えました。
というわけで答え。難しいことはないのでこれは気づくべきでした。
a, b, c = map(int, input().split())
if 0 < c - a - b and 4 * a * b < (c - a - b)**2:
print("Yes")
else:
print("No")
D - String Equivalence
N(≦10)の文字数で存在する文字列パターンを全て並べろ、という問題です。
いいやり方がわからなかったので、一度全パターンを並べてから消していくゴリ押しで解こうとしました。実際には書いてる途中で詰まって提出できてないですが、以下のようなコードを書きました。
import itertools
N = int(input())
alp = [chr(ord('a') + i) for i in range(N)]
allS = list(itertools.product(alp, repeat=N))
answers = []
PatternList = []
for s in allS:
pattern = []
letters = []
for l in s:
if not l in letters:
letters.append(l)
pattern.append(letters.index(l))
if not pattern in PatternList:
PatternList.append(pattern)
answers.append(s)
for answer in answers:
print(''.join(answer))
N=10までならいけると思ったのですが、後半でTLEが出ました。
解説を見ました。標準形の条件は、以下の数式に置き換えられます。
$$ s_1 = a $$
$$ s_k \leq \max[ s_1, \cdots, s_{k - 1}] + 1$$
この二つの条件を満たすようにDFSで探索すればいいようです。最大値の情報を保持する変数mxに最大値の情報を格納し、再帰関数で渡していきます。
サンプル通りに作ったのが以下です。
n = int(input())
def dfs(s, mx):
if len(s) == n:
print(s)
else:
for i in range(0, mx + 1):
c = chr(ord('a') + i)
if i == mx: dfs(s+c, mx+1)
else: dfs(s+c, mx)
dfs('', 0)
E - Three Substrings
文字列sから取り出した部分文字列a, b, cの三つを与えられて、元の文字列sを推測する問題です。
文字列sとしてa+b+cの長さを持つ空の配列を用意して、a, b, cの三つを片っ端から当てはめていく方針で書き始めましたが、詰まる要素があったりどうせTLE出るのが見えてたりで諦めました。
解説を見ました。aとb、bとc、aとcの三つそれぞれについて存在しうる「相対位置」を配列として取得します。これをab[]、ac[]、bc[]として格納。そこからaとbの位置関係をi、aとcの位置関係をjで表すとbとcの位置関係はj-iで取得できます。
これによってiとjを回していき、ab[i]とac[j]、bc[j-i]の三つの条件を満たす場合の文字数を計算することによって求まります。a, b, cはそれぞれ$\pm 4000$まで離れうることに注意しましょう。
ほとんど解説をPythonに書き換えただけですが、以下のコードで通りました。Pypy3でもこのアルゴリズムだとカツカツで、1991 msというギリギリの時間になります。例えばab[]に1と0ではなくTrueとFalseを入れるだけでTLEが出ます。数倍早い計算時間を出してる人やPythonでこれを通している人もいたので、もっと早い手法があるようです(まだちゃんと見てない)。
a = input()
b = input()
c = input()
A, B, C = len(a), len(b), len(c)
ab, bc, ac = [1] * 16000, [1] * 16000, [1] * 16000
for i in range(A):
if a[i] == '?':
continue
for j in range(B):
if b[j] != '?' and a[i] != b[j]:
ab[i-j+8000]= 0
for i in range(B):
if b[i] == '?':
continue
for j in range(C):
if c[j] != '?' and b[i] != c[j]:
bc[i-j+8000]= 0
for i in range(A):
if a[i] == '?':
continue
for j in range(C):
if c[j] != '?' and a[i] != c[j]:
ac[i-j+8000]= 0
ans = 6000
for i in range(-4000, 4000):
for j in range(-4000, 4000):
if ab[i+8000] and bc[j-i+8000] and ac[j+8000]:
L = min(0, min(i, j))
R = max(A, max(B+i, C+j))
ans = min(ans, R-L)
print(ans)
この記事はここまでとします。できれば後にF問についても追記したい。