ABC 297 のA,B,C,D 問題を解くために考えたこと、ACできるPython3(PyPy3)コードを紹介します。
この記事は @u2dayo さんの記事を参考にしています。見たことのない方はそちらもご覧ください。とても勉強になります。
また、問題の難易度を表す指標を Atcoder Problems から引用しています。このサイトは勉強した問題を管理するのにとてもオススメです。
質問やご指摘はこちらまで
Twitter : Waaa1471
作者プロフィール
Atcoder ：緑色 1029
230409 現在
目次
はじめに
A.Double Click
B.chess960
C.PC on the Table
D.Count Subtractions
はじめに
特にC問題以降になると、競技プログラミングに典型的な前提知識、少し難しい数学的考察が必要になり始めます。
しかし、公式解説ではこの部分の解説があっさりしすぎていて競技プログラミング(Atcoder)を始めたばかりの人にはわかりにくい、難しいと感じるのではないでしょうか。
またC++がわからないと、コードの書き方を勉強することが難しいです。一応、参加者全員のコードを見ること自体は可能ですが、提出コードは必ずしも教育的ではありません(ここで紹介する記事も本番で提出したものとは全く異なります)。そんなものから初学者が解説もなしになにか得ることはとても難しいと思います。実際適当に何人かのコードをみたものの、意味がわからずに終わった経験があるのではないでしょうか。
この記事がそんな方々の勉強の助けになればよいなと思っています。
A.Double Click
難易度：灰色 16
考察
前から順番にクリック時刻 Ti を確認し、直前の Ti-1 との差が D 以下であるかを調べていきます。
この問題では初めて成功したタイミングのみ問われているので、一度ダブルクリックを検出したタイミングで処理を終了する必要があります。
コード
pypy3
61 ms/2000 ms
N,D=[int(nd) for nd in input().split()]
T=[int(t) for t in input().split()]
for i in range(1,N):
if T[i]-T[i-1]<=D:
print(T[i])
exit()
print(-1)
補足
なし
B.chess960
難易度： 灰色47
考察
各文字の位置を調べ、それらが条件を満たすか調べます。
コード
pypy3
64 ms/ 2000 ms
S=input()
B=[]
R=[]
for i in range(8):
if S[i]=="B":
B.append(i)
if S[i]=="R":
R.append(i)
if S[i]=="K":
K=i
if B[0]%2!=B[1]%2 and R[0]<K<R[1]:
print("Yes")
else:
print("No")
C.PC on the Table
難易度 ： 灰色 96
考察
文字列 TT を 文字列 PC に置き換えます。python では文字列の置き換えが replace() 関数で容易に行えます。
コード
67 ms/ 2000 ms
pypy3
H,W=[int(hw) for hw in input().split()]
for i in range(H):
s=input()
s=s.replace("TT","PC")
print(s)
補足
D.Count Subtractions
難易度：灰色 273
考察
B > A が成立する間、B-A を繰り返すことになるが、これを素直に操作することはできない。B=10^18 , A=1 の場合などで 10^18 回程度が必要となるからである。
そこで操作回数を減らす工夫を考えてみると、B>A が成立する間(成立しなくなるまで) B-A を繰り返すことは、B を A で割ることと同値であること が利用できそうである。
この間の B-A を繰り返す回数は B//A であり、この操作によって B ⇒ B%A となる。つまり、B//A の操作回数を割り算 1回 ( O(1) ) で実現することができた。
あとはこれを A=B となるまで繰り返せばよい。ここで A=B となる直前では、B は Aの倍数であり、B-A を B//A -1 回繰り返すことで A=B の状態になる。
さて肝心の計算量であるが、正直に言うと筆者は厳密に推定することなく"勘"で通しました。
なんか正解できそうな考察(主観)だし、5分考えても厳密な推定ができなさそうと感じたため、ペナルティ覚悟で提出して AC できた感じです。
※ 補足にて厳密な計算量推定を行っています。
コード
pypy3
A,B=[int(nm) for nm in input().split()]
ans=0
while A!=B:
# B の方が大きい状態を維持
if A>B:
A,B=B,A
# B が A の倍数なら B-A を B//A -1 回繰り返して操作終了
if B%A==0:
ans+=B//A-1
B=A
# そうでないなら、B-A を B//A 回繰り返す
else:
ans+=B//A
B=B%A
print(ans)
補足 ～計算量推定～
1回の操作によって B ⇒ B%A (以下 B') となるが、このとき 2B' < B が成立すれば B は log2B 回以下で 1 に到達できる。
したがって A,B がともに 1 となって条件を満たす最も操作回数が必要になる場合でも、高々 log2A + log2B 回で操作が完了することになる。
つまり、2B' < B が成立するならば十分高速に操作を完了できることがわかった。
以下、 2B' < B を示す。
-
2A < B のとき
B' < A ( 余り < 割る数 )
⇔ 2B' < 2A < B -
2A = B のとき
2B' = 0 < B -
2A > B のとき
2B' = 2B - 2×Ak
≦ 2B - 2A
< 2B - B
< B
以上より、十分高速に操作が完了することを示せた。
参考
公式解説
終わり
記事は中途半端だわ、E は解けないわで悔しい