【AtCoder】ABC179の参加記録.~感想と解法~【python】

AtCoder
この記事は約4分で読めます。

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

コメント

タイトルとURLをコピーしました