ABC178に引き続き，連続での参加となります．
今回はDP(動的計画法)が出ないことを祈って参加しました笑
解いたのはA~C問題．ですが，アクシデント(我が家のルーターぶっ壊れ事件)により，B問題までしか提出できていません．懺悔．
A問題：Plural Form
入力の文字列の末尾で条件分岐すればいいだけ．
s=input()
if s[-1]=="s":
print(s+"es")
else:
print(s+"s")B問題：Go to Jail
2つのサイコロを同時にN回振って，ゾロ目が連続で3回以上出るか否かを判定する．
順番にfor文で回してカウントすればOK．
#入力:[n1,n2,...nk](int:整数配列)
def input_array():
return list(map(int,input().split()))
n=int(input())
D=[input_array() for i in range(n)]
count=0
for d in D:
if d[0]==d[1]:
count+=1
else:
count=0
if count==3:
break
if count==3:
print("Yes")
else:
print("No")C問題：A x B + C
最初は$N=A \times B + C$を$N – C=A \times B$に式変形して，Cを固定かつ$A \times B$の約数を列挙して求めていた．(以下のコード)
def make_divisors(n):
divisors = []
for i in range(1, int(n**0.5)+1):
if n % i == 0:
divisors.append(i)
if i != n // i:
divisors.append(n//i)
divisors.sort()
return divisors
n=int(input())
count=0
for c in range(1,n+1):
ab=n-c
tmp=len(make_divisors(ab)) #約数の列挙
count+=tmp
print(count)固定するCは全探索で$O(N)$，約数の列挙は$0(\log N)$で，全体としての計算量は$0(N \log N)$である．
今回の制約は[$2 \leq N \leq 10^6$]なので，Pythonでは間に合いません(他言語だとどうなのかな．)
ということで考えを変えて，式変形を$C=N – A \times B$として，これを満たすAとBを考える．
$C \leq 1$なので，$N – A \times B \leq 1$ ．
つまり，この問題の解法は，
$A \times B \geq N-1$を満たすAとBの数をカウントする
さらにAとBを順番に探索すると間に合わないので，さらに式変形すると$A \geq \frac{N-1}{B} $となり，これを満たすAを順番に探索すると，計算量が$0(N)$で間に合う．
というわけで，以下のソースコードでAC．
n=int(input())
count=0
for a in range(1,n+1):
count+=(n-1)//a
print(count)感想(懺悔コーナー)
B問題まではすんなり解けて，さあC問題頑張るかーと思ってた矢先に，自宅のルーターがぶっ壊れました．．．
結局プラグを引っこ抜いてしばらく放電したら治ったんですが，それで再開するやる気は削がれました．
ってことで今回の私のABCは参加時間約15分で幕を閉じました(泣)
D問題は今週中に解いておきます．あとで解法もアップしますので(気長に)待っててください．
コメント