初めに
AtCoderに参加した記録を残します。どのような考察をしながら問題に取り組んだかを記録していますので、必ずしも教育的なコードとは限りません。
始めたばかりの人など、どなたかの助けになれば嬉しいです。
成績
ABC296 3冠
D安定して解けるようになりたい...。
目次
A - Alternately
B - Chessboard
C - Gap Existence
D - M<=ab
E - Transition Game
A - Alternately
問題ページ
与えられたF, Mからなる文字列において、文字が交互に配置されているか判定する問題。
考察
とりあえず愚直に前後の比較をすればいけそうだなということを考えた。
もうすこしカッコよくやろうかなと思い、2真数に変換していい感じにXOR取ったりしてやろうとしたけど時間かかりそうだったから素直に愚直に判定してAC。
コード
N = int(input())
S = input()
bef = S[0]
for i in range(1, N):
if S[i] == bef:
print('No')
exit()
bef = S[i]
print('Yes')
改善点
着想面
前後比較で良かったっぽい。
コード面
わざわざ bef みたいな変数用意しなくても N-1 のループ回して i, i+1 に対して判定してやればもっと短くなったっぽい。
N = int(input())
S = input()
for i in range(N-1):
if S[i]==S[i+1]:
print('No')
exit()
print('Yes')
B - Chessboard
問題ページ
チェスのコマがどこにあるかをa1的なマス名で出力する問題。入力は8×8の盤面で、駒の場所は ' * ' , それ以外は ' . ' の文字列で与えられる。
考察
シンプルに8×8の２重ループ回して ' * ' がある l, h を見つけて、事前に用意した行と列の名称を変換するリストで適正な出力に変換。
low_pat = [1〜8]
col_pat = [‘a’, 〜, ‘h’]
コード
S = [list(input()) for _ in range(8)]
l_pat = [i for i in range(8, 0, -1)]
c_pat = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
for l in range(8):
for c in range(8):
if S[l][c] == '*':
print(f"{c_pat[c]}{l_pat[l]}")
exit()
改善点
着想面
問題なし。
コード面
事前にpatのlistは考えなくてもよくて、出力の際に整形すればKO。
ordは 文字列 → ASCII 、chrは ASCII → 文字列 の変換を行う関数。
N = 8
S = [list(input()) for _ in range(8)]
for l in range(N):
for c in range(N):
if S[l][c] == '*':
print(f"{chr(ord('a')+c))}{N-l}")
exit()
C - Gap Existence
問題ページ
与えれる長さNの数列Aに対して任意の1 <= i, j <= N を選んだ時に Ai - Aj = X となるような i, j の組みが存在するかを判定する問題。
考察
i, j の組を愚直に探索しようとするとO(N^2)かかってしまい、制約的に間に合わない。ここでAi - Aj = X を式変形すると、Ai + X = Aj となり、これは Ai + X となるような数が数列内に存在するか という問題に置き換えられたことになる。ここまで来ればあとはAi + X の候補集合をO(N)で作成し、数列の要素が候補集合に含まれるかの判定をO(N)で行えば良い。
コード
N, X = map(int, input().split())
A = list(map(int, input().split()))
need_set = set()
for a in A:
need_set.add(a+X)
for a in A:
if a in need_set:
print('Yes')
exit()
print('No')
改善点
着想面
式変形しなくても、片方を固定することさえ把握できていればOKだった。
コード面
そこそこ効率がいいと思うのでとりあえず放置。
D - M<=ab
問題ページ
整数N, Mが与えられ、条件を見たす最小のXを求める問題。
考察
M <= X <= N^2 なことくらいしかわからんかった…。この手の問題マジで解けない。
改善点
着想面
a <= bと仮定してaの方を探索する。b = M//a とし、 b <= N の場合は回の候補として記録。
この解法だと a<=b を仮定していることから a <= √M あたりまで探索すれば用意ことがわかり、十分高速に解けるらしい。うーん、やっぱり同じ問題出てもあんまり解ける気がしない...。
E - Transition Game
問題ページ
ゲーム木の探索っぽい問題。
考察
初手の選択だけちょっと特殊でそれ以外はいい感じにグラフの周期を見つけてどうにかしていくのかな〜っていうのはなんとなくわかったけど、制約デカすぎて何すればいいかようわからんかった。
改善点
着想面
雰囲気はあってたっぽい。強連結成分分解なる概念を使えばいい感じに解けるらしい。
参考資料
強連結成分分解＆トポロジカルソート p82以降
目指せグラフマスター p7以降
終わりに
書き始めたばかりで拙い部分も多いですが、みなさんと楽しく盛り上がれたらいいなと思っていますので、よろしくお願いいたします！