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問題は今週中に解いておきます.あとで解法もアップしますので(気長に)待っててください.
コメント