はじめに
先日、所属しているサークルOSKの競プロ班に新しい人が何人か入りました。
既に競プロはかじったことがあるようだったので、困っている点をいくつか聞いてみると、解法は理解しているのにその実装でうまくいかないパターンが多いように感じました。
改めてTwitter上での初学者の嘆きや提出コードを思い出してみると、同様の事象は広く起こっていると思います。
一方で、競技プログラミングでは実装についての記事が少なく、アルゴリズム部分へ注力されがちです。
そこで、ひとつのコードをレビューしながら、競プロ初心者が陥りがちな実装の罠をいくつか紹介し、その改善方法を提案してみたいと思います。
注意点
Python 使いなので Python のコードを例に挙げますが、他の言語でも同様なことがいえると思います。
かなり一般的な話にしているため問題ないと思いますが、私のレーティング（Atcoder水）より上の世界では違う可能性があります。初心者向けの記事であるため、その点をご了承ください。
以下問題・解法のネタバレがあるため、注意してください
問題：C - Airport Code（ABC349）
問題文
英大文字からなる長さ $3$ の文字列 $T$ が、英小文字からなる文字列 $S$ の 空港コード であるとは、$T$ が $S$ から次のいずれかの方法により得られることとします。
- $S$ の長さ $3$ の（連続とは限らない）部分列をとり、それを英大文字に変換したものを $T$ とする
- $S$ の長さ $2$ の（連続とは限らない）部分列をとり、それを英大文字に変換したものの末尾に
Xを追加したものを $T$ とする
文字列 $S$, $T$ が与えられるので、$T$ が $S$ の空港コードであるか判定してください。
制約
- $S$ は英小文字からなる長さ $3$ 以上 $10^5$ 以下の文字列
- $T$ は英大文字からなる長さ $3$ の文字列
解法
貪欲に取ればよいことが示せます。
- $S$ を前から見て行って、$T$ の頭文字と一致したらその文字を $T$ から削除していく
- (最後 or 残りが
Xのみ) まで削除できたらYes、削除しきれなかったらNoとする
今回はコードの改善が目的なので解法についての詳細な議論は省略しますが、以後の理解を深めるためにもこの操作のイメージを掴んでから読み進めてください。
今回修正するコード
S = input()
T = input()
i = 0
d = False
for j, t in enumerate(T):
if j == len(T) - 1 and t == "X":
print("Yes")
d = True
break
f = False
for ii, s in enumerate(S[i:]):
if s == t.lower():
f = True
i += ii + 1
break
if not f:
print("No")
d = True
break
if not d:
print("Yes")
ぱっと見何やっているのかよくわかりませんね……。
ただ通ってはいるので、間違った処理を行っている訳ではなさそうです。
変数名を常に一文字にしてしまう
早速是非が分かれる議題ですが、僕は競プロであっても極端な一文字変数は否定的です。
一文字変数はその変数が何を表しているのかを覚えるのが難しいです。
「これってなんだっけ？」「この変数って使ったっけ？」となったことはありませんか？
例えば、i はindexを表していることが多いですが、id と単に一文字増やしただけで、その変数が何を表しているのかが明確になります。
一方でコーディング速度が落ちるのでは？という意見もありますが、予測補完が効いているエディタを使っていれば入力時間はさして変わりませんし、上記のような迷っている時間の方が圧倒的に長いと思います。
今回のコードの一文字変数を以下のように変更してみましょう。
- i = 0
+ s_id = 0
- d = False
+ done = False
- f = False
+ found = True
すると、全体を以下のように修正できます。
S = input()
T = input()
s_id = 0
done = False
for i, t in enumerate(T):
if i == len(T) - 1 and t == "X":
print("Yes")
done = True
break
found = False
for j, s in enumerate(S[s_id:]):
if s == t.lower():
found = True
s_id += j + 1
break
if not found:
print("No")
done = True
break
if not done:
print("Yes")
大分わかりやすくなりましたね！
また、元々 j 、ii であったループ変数も i 、j に変更しています。
恐らく後からループ変数が必要な事に気づき、まだ使っていない変数を適当にあてがっていたのだと思います。
これは s_id といった全体にかかる変数を、i といったよく使う単純な変数名を使ってしまうことによるものです。
名著：リーダブルコードにもあるように、スコープの範囲が広い変数ほど、その変数名をわかりやすくする必要があります。
競プロであれば厳密な命名は必要ありませんが、それでも変数名をわかりやすくすることで、コードの実装がスムーズになります。
解が求まった時にbreakを使ってしまう
break は認知負荷が高いもののひとつです。
for i in range(n):
...
if flag:
...
break
上記はよくある break の使用例ですが、for 文と break 文の間に多くのコードが書かれると、break の対象が何かわかりにくくなります。
これがネストされた場合、瞬時に break の対象を見つけることはほぼ不可能でしょう。
解が確定している場合、その後の処理は必要ないため、サッサと終了してしまう方がよいでしょう。
S = input()
T = input()
s_id = 0
- done = False
for i, t in enumerate(T):
if i == len(T) - 1 and t == "X":
print("Yes")
- done = True
- break
+ exit()
found = False
for j, s in enumerate(S[s_id:]):
if s == t.lower():
found = True
s_id += j + 1
break
if not found:
print("No")
- done = True
- break
+ exit()
- if not done:
- print("Yes")
+ print("Yes")
途中からの探索を行うとき、for文を使ってしまう
このコードでは、T を前から見て、S を見ていない部分 s_id 以降を見ていくといった処理を行っています。
このように、2つの配列を非同期的に前から見ていく処理は、競プロだと比較的よくあります。
尺取り法はその代表例でしょう。
この処理を行うとき、両方 for 文を使ってしまうと s_id を更新する処理が複雑になりがちです。
while 文を使うことで、s_id を更新する処理をシンプルにすることができます。
S = input()
T = input()
s_id = 0
for i, t in enumerate(T):
if i == len(T) - 1 and t == "X":
print("Yes")
exit()
found = False
- for j, s in enumerate(S[s_id:]):
- if s == t.lower():
- found = True
- s_id += j + 1
- break
+ while s_id < len(S):
+ if S[s_id] == t.lower():
+ found = True
+ s_id += 1
+ break
+ else:
+ s_id += 1
+ continue
if not found:
print("No")
exit()
print("Yes")
ただ、これでも配列外参照などややこしい問題が残っています。
そもそも「前から見ていって、戻ることがない」という性質を踏まえると、Queue を使うのが適切だと考えられます。
+ from collections import deque
S = input()
T = input()
- s_id = 0
+ S = deque(S)
for i, t in enumerate(T):
if i == len(T) - 1 and t == "X":
print("Yes")
exit()
found = False
- while s_id < len(S):
- if S[s_id] == t.lower():
- found = True
- s_id += 1
- break
- else:
- s_id += 1
- continue
+ while S:
+ if S.popleft() == t.lower():
+ found = True
+ break
if not found:
print("No")
exit()
print("Yes")
このようにすることで、s_id の更新処理が不要になり、コードがシンプルになります。
不自然な処理の順番
さて、ある程度コードが整理されたので、改めてコードと解法を見比べてみましょう。
解法
- $S$ を前から見て行って、$T$ の頭文字と一致したらその文字を $T$ から削除していく
- (最後 or 残りが
Xのみ) まで削除できたらYes、削除しきれなかったらNoとする
コード
from collections import deque
S = input()
T = input()
S = deque(S)
# Tを前から見て、Sの中で見つかるかどうかを探す
for i, t in enumerate(T):
# 末尾までたどり着き、かつtがXの場合はYes
if i == len(T) - 1 and t == "X":
print("Yes")
exit()
# 残っているSを見て、tと一致するものがあるかどうかを探す
found = False
while S:
if S.popleft() == t.lower():
found = True
break
# 見つからなかった場合はNo
if not found:
print("No")
exit()
print("Yes")
どうでしょうか？解法とコードが一致していないことがわかりますね。
この記事の始めでコードが理解できなかったのは、このような不自然な処理の順番が原因でした。
改めて解法通りのコードを書いてみましょう。
S = input()
T = input()
# Sを前から見る
for s in S:
# Tの頭文字と一致したら削除
if s == T[:1].lower():
T = T[1:]
# (最後 or 残りがXのみ) まで削除できたらYes
if not T or T == "X":
print("Yes")
exit()
print("No")
なんということでしょう。あんなに複雑だったコードが、これだけシンプルになりました。
上記のコードは T = T[1:] 部分で O(len(T)) の計算量がかかってしまいますが、今回は T の長さが最大3なので問題ありません。
もし T の長さが大きい場合は、T を deque に変換することで先頭文字を O(1) で取り出すことができます。
from collections import deque
S = input()
T = input()
if T[-1] == "X":
T = T[:-1]
T = deque(T.lower())
for s in S:
t = T.popleft()
if s == t:
if not T:
print("Yes")
exit()
else:
T.appendleft(t)
print("No")
ついでに、X の例外処理を最初に移すことで、単なる部分文字列かどうかの確認となるようにしてみました。
なぜこのようなコードが生まれてしまうのか
読者の中には「最初のコードがおかしすぎない？」と思った方もいるのではないでしょうか？
もちろん私がこの記事用に書いたコードなので作為的におかしなコードになっていますが、実際に初心者が書いてしまうコードも同様の問題があります。
「おかしい」と思えたのは、すでに解法を知っていたからです。
この問題を、「前から順番に取っていけば出来るな～」程度の解像度で実装を始めると、最初のようなコードが生まれてしまうのです。
あくまでコードはコンピュータへの指示書です。
指示する手順を具体的にイメージできないことには、その指示書を書くことは難しいです。
上記の解法のような具体的な手順のイメージをもってから、実装に移ることが重要なのです。
まとめ
アンチパターン集と銘打って紹介してきましたが、変数名の一文字化や break の使用方などについては、あくまでコードを書くときに自分が迷子にならない工夫です。
実装で詰まる場合、ほとんど（いわゆる重実装と呼ばれる問題以外）は実装の前段階で誤っています。
解法を理解し、具体的な手順をイメージするトレーニングを積みましょう。
おまけ
最後の直す直前のコード、別に不自然ではないと思ったそこの君！！正解だ！！
というのも、今回は $S$ と $T$ どちらを基軸に考えても何らおかしいことは生じないです。
私が不自然さを感じてほしい点は、解法とコードが一致していないことです。
もし最初に以下の解法を提示していたら、正解不正解を全く逆にして書いていたと思います。
解法
- $T$ を前から見て $S$ と一致するか試し、あれば次に進む
- （最後 or 残りが
X）のみまでたどり着いたらYes、つかなかったらNo
コード
from collections import deque
S = input()
T = input()
if T[-1] == "X":
T = T[:-1]
S = deque(S)
for t in T:
found = False
while S:
if S.popleft() == t.lower():
found = True
break
if not found:
print("No")
exit()
print("Yes")
全然きれいですね。
結局は解法の手順が簡潔に整理されているのが鍵ってのは変わらなさそうです。
ただ、発展的な課題としてよりコンピュータに近い処理で整理できる解法を選ぶ、というのも速度が重要な競技プログラミングでは必要です。
上記の2方針ではそこまで差がありませんが、正規表現で処理できると思いつけば瞬殺できます。
コンテスト中に思いつくのは現実的でないですが……。