AtCoder Beginner Contest 179のA,B,C問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル：余計なことを考えずに済む
- 実装が楽：ミスやバグが減ってうれしい
- 時間がかからない：パフォが上がって、後の問題に残せる時間が増える
ご質問・ご指摘はコメントかツイッターまでどうぞ
Twitter: u2dayo
目次
ABC179 まとめ
A問題『Plural Form』
B問題『Go to Jail』
C問題『A x B + C』
ABC179 まとめ
全提出人数: 8902人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | AB---- | 300 | 12分 | 6850(6664)位 |
| 400 | ABC--- | 600 | 77分 | 5678(5493)位 |
| 600 | ABC--- | 600 | 42分 | 4677(4492)位 |
| 800 | ABC--- | 600 | 24分 | 3629(3445)位 |
| 1000 | ABC--- | 600 | 11分 | 2658(2474)位 |
| 1200 | ABC-E- | 1100 | 94分 | 1854(1674)位 |
| 1400 | ABCDE- | 1500 | 98分 | 1252(1073)位 |
| 1600 | ABCDE- | 1500 | 59分 | 825(649)位 |
| 1800 | ABCDEF | 2100 | 92分 | 529(365)位 |
| 2000 | ABCDEF | 2100 | 72分 | 325(191)位 |
| 2200 | ABCDEF | 2100 | 60分 | 199(93)位 |
| 2400 | ABCDEF | 2100 | 52分 | 121(42)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|
| 灰 | 3892 | 97.5 % | 90.9 % | 47.7 % | 2.2 % | 3.0 % | 0.2 % |
| 茶 | 1648 | 99.3 % | 99.3 % | 83.9 % | 8.7 % | 12.9 % | 1.2 % |
| 緑 | 1305 | 99.7 % | 99.7 % | 96.3 % | 33.7 % | 40.1 % | 3.1 % |
| 水 | 739 | 99.9 % | 99.9 % | 99.5 % | 74.2 % | 81.3 % | 24.9 % |
| 青 | 343 | 99.7 % | 99.7 % | 99.7 % | 94.2 % | 95.6 % | 75.8 % |
| 黄 | 151 | 98.7 % | 98.0 % | 98.0 % | 98.0 % | 96.7 % | 92.0 % |
| 橙 | 30 | 100.0 % | 96.7 % | 96.7 % | 96.7 % | 93.3 % | 93.3 % |
| 赤 | 7 | 85.7 % | 85.7 % | 85.7 % | 85.7 % | 100.0 % | 100.0 % |
※表示レート、灰に初参加者は含めず
簡易解説
- A問題 (8716人AC)『Plural Form』
- 文字列の一番後ろの文字を取り出すために、
S[-1]と書くと楽です。 - B問題 (8333人AC)『Go to Jail』
- ゾロ目かどうか判定するのは、A問題レベルです。あとは、今何連続でゾロ目か出ているか記録するだけです。
- C問題 (6059人AC)『A x B + C』
- $A$ と $B$ を決めると、$C$ は自動的に決定します。$A$ を全探索する方法と、$A$ と $B$ を二重ループで全探索する方法があります。約数を列挙する方法は、Pythonでは間に合いません。
- D問題 (1777人AC)『Leaping Tak』[この記事では解説しません]
- 素直な動的計画法を書くと、計算量が $O(N^2)$ になって間に合いません。いわゆる累積和、IMOS法のような配列に遷移情報を持っておくと、$O(KN)$ で解けます。
- E問題 (2008人AC)『Sequence Sum』[この記事では解説しません]
- $N$ が非常に大きいので、操作をシミュレートして解くことはできません。整数を $M$ で割った余りは $M$ 通りしかないので、途中から同じ数列を繰り返すことを利用すると解けます。
- F問題 (707人AC)『Simplified Reversi』[この記事では解説しません]
- （私がまだ理解できていない）
- 楽だが、Pythonで通すには実行時間に注意が必要な方法（PyPyなら安全）
- やや発想が面倒だが、Pythonでも余裕を持って通る方法（公式解説の方法）
- PyPyを使う（100ms程度で通る）
- 計算を行う部分を、関数として分ける（1800ms程度で通る）
私（うにだよ）の結果（参考）
A問題『Plural Form』
問題ページ：A - Plural Form
実装
一番後ろの文字を取り出すには、S[-1]と書くといいです。S[len(S)-1]とやってることは同じですが、より簡潔で、間違いもしづらいです。
コード
S = input()
if S[-1] == "s":
print(S + "es")
else:
print(S + "s")
B問題『Go to Jail』
問題ページ：B - Go to Jail
考察：
ゾロ目の判定は、ただif文で判定するだけなので、簡単にできます。
現在何連続でゾロ目が出ているか、記録することにします。初期値は0で、ゾロ目なら+1して、ゾロ目でなければ0にリセットします。
3連続以上ならOKということは、3連続になった瞬間に"Yes"と出力して構いません。こうすれば、最大何連続で出たか記録しておく必要がなくなって、楽です。
コード
returnを使うと楽なので、関数に分けて書きました。
def judge():
cnt = 0 # 今何連続でゾロ目が出ているか記録しておきます
for _ in range(N):
x, y = map(int, input().split())
if x == y:
# ゾロ目ストリークが1増えました
cnt += 1
else:
# ゾロ目ストリークが切れました
cnt = 0
if cnt == 3:
# 3連続になった瞬間、return True していいです
return True
# ダメでした
return False
N = int(input())
if judge():
# judge() で Trueが返ってくるとこっちに進みます
print("Yes")
else:
# Falseだとこっちです
print("No")
C問題『A x B + C』
問題ページ：C - A x B + C
2つの方法を書きました。
問題の意味
$1$ 以上の整数 $A,B,C$ の組み合わせで、$A\times{B} + C = N$となるのは何通りありますか。
考察1：楽だが、Pythonで通すには実行時間に注意が必要な方法
$C$ が左辺にくるように、式を変形してみます。
$C = N - A\times{B}$
となります。つまり、$A, B$ を決めてしまえば、$C$ は自動的に決定します。
そこで、$A, B$ を二重forループで全探索します。しかし、$A, B$ が取りうる範囲は、$1$ から $N - 1$です。下のコードのように何の工夫もしないと、計算量が $O(N^2)$ になって間に合いません。
# これはTLEになります
N = int(readline())
ans = 0
for a in range(1, N):
for b in range(1, N):
c = N - a * b
if c > 0:
ans += 1
$A = k$ と固定して考えてみます。（$k$ は適当な正の整数で、とくに中身を気にする必要はありません）
$B$ を $1$ からはじめて $N-1$ まで $1$ ずつ増やしていくと、 $C = N - kB$ は単調減少していきます。（グラフを書くと、1次関数の右下がりの直線になります。途中で増えることはなく、ただ減る一方ということです）
ということは、ある $B$ の時点で $C\le{0}$ になったら、それ以上大きい $B$ でも全て $C\le{0}$ になるで、今の $A$ でこれ以上探索する必要はありません。つまり、breakして打ち切ってしまって構いません。
サンプル3より、制約下で最大の $N=1000000$（$100$万）のとき、答えは $13969985$（$1400$万くらい） です。$C\le{0}$ になった瞬間に打ち切れば、ループの実行回数は $1400$万 + $100$万回程度になるので、間に合います。
実装1
この方法は、Pythonの場合、注意しないとTLEになって通りません。
前者は、何も考えずにPyPy7.3.0で提出するだけです。PyPy7.3.0はPython3.6準拠なので、Python3.7、3.8の機能を使っているとREになります。そこだけは注意が必要です。（代入式:=、逆元をpow(x,-1,MOD)で求めるなど）
後者は、計算を行う部分を関数に分けることで、そうしない場合よりも高速化します。私はあまり詳しくないのですが、Pythonはグローバル名前空間のアクセスが遅いので、関数として書いてローカル名前空間にアクセスさせることで速くなるようです。
コード1
# このように、関数内に書くだけで速くなります
def solve():
ans = 0
for a in range(1, N):
for b in range(1, N):
c = N - a * b
if c <= 0:
break
ans += 1
return ans
N = int(input())
ans = solve()
print(ans)
余談
関数内に書くだけで高速化するので、あらゆる問題であらゆる処理を関数内でやってしまってもいいです。
具体的には、下のようなコードになります。
def main()
# ここにコードを書く
if __name__ == '__main__':
main()
考察2：やや発想が面倒だが、Pythonでも余裕を持って通る方法
$C$ が左辺にくるように、式を変形してみます。すると、
$C = N - A\times{B}$
となります。つまり、$A, B$ を決めてしまえば、$C$ は自動的に決定します。
$A$ を固定して考えたとき、$C > 0$ を満たす $B$ が何個あるか高速に求められれば、$A$ を $1$ から $N-1$ まで全探索することで、この問題を解くことができます。
ここで、$A$ を固定したとき、$C > 0$ を満たす $B$ の最小値、最大値に着目してみます。
$B$ の最小値は $B = 1$ です。
$B$ の 最大値は $C = 1 \le{N - {A\times{B_{max}}}}$ を満たす最大の正整数 $B_{max}$ です。
最小最大の間の $B$ もすべて $C > 0$ を満たすので、求めたい個数は、$1$ ～ $B_{max}$ の間の $B_{max}$ 個 になります。つまり、$B_{max}$ が計算で求められればいいです。
再び式を変形すると、
1 \le{N - {A\times{B_{max}}}}\\
A\times{B_{max}} \le{N-1}\\
B_{max}\le{\frac{N-1}{A}}
となります。
$B_{max}$ は正の整数なので、$\frac{N-1}{A}$ を切り捨てた値が $B_{max}$になります。
あとは、$A$ を $1$ から $N-1$ まで全探索して、それぞれの $B_{max}$ を足しあわせれば答えが出ます。
コード2
N = int(input())
ans = 0
for a in range(1, N):
ans += (N - 1) // a
print(ans)