AtCoder Beginner Contest 105 - moriijohnのブログ

AtCoder Beginner Contest 105に出ました。最近競プロの精進ができていなくて不安でしたが、4完できてうれしいのでブログを書きます。解法ではなく考えのプロセスを書くようにしてみます。

A - AtCoder Crackers

トランプのカードを全部配るようなものを想像すれば、差は0か1かのどちらかであり、差が0になるのはNがKで割り切れるときのみです。

提出コード

N,K=map(int,input().split())   
if N%K == 0:
    print(0)
else:
    print(1)

B - Cakes and Donuts

ちょっと数学をしたくなりますが、誘惑をこらえて制約をチェックし、4ドルの数と7ドルの数についての全探索をします。その際両方0であるようなものに対してNoを出力することに気を付けます…と書いているときに制約でNが0でないことに気づきました。

数学の経験値がプログラミングの経験値よりも多い人は、数学をする誘惑に負けずに全探索でできないか考えることが大切だとおもいます。また、最初から全探索を考えるだけでなく、いったん数学的な考察をして何か面白い事実に気づいた時点で、その面白い事実を踏まえた別な全探索ができないかを考えることも大切だと思います。ぼくはこの後者を忘れがちです。

提出コード

N=int(input())

if N<4:
    print("No")
    exit()
for i in range (26):
    for j in range(15):
        if N == 4*i + 7*j:
            print("Yes")
            exit()
print("No")

C - Base -2 Number

問題文が難しくなりました。まずは問題文を理解し、サンプルを紙に書いて理解します。

どんな数でもこの方法で表現できるのはなぜだろう？と考えて、紙に手書きで1桁で表現できる数、2桁で表現できる数、...を列挙することで糸口をつかむことができます。ここで図を掲載すべきところでしょうが大変なので、文章で書きます。1桁で表現できるのは0と1のみです。2桁ではこの2つに-2をした数が増えるので、-2, -1が仲間に加わります。3桁までつかうとこれらの仲間に4を足した数である2,3,4,5が新たに仲間に加わります。ここまで手で紙に書いてみると、証明はともかくすべての整数がいつか仲間になることが腑に落ちるはずです。

具体的に表示を求めるには、以上のプロセスを逆にたどっていけばよいです。まず、元の数が初めて仲間に入った時の桁は1でなければいけません。次に、元の数から、今用いた(-2)の累乗数を除いた残りの部分を、残りの桁で表現するということを考えます。そのためには、「第n桁目ではじめて表現できるようになった数にその数が含まれているか」を判定して、結果に応じてその桁を1か0にする、桁数を減らして繰り返す、というような再帰的な手順になります。日本語が下手ですが推敲はしません。ごめんなさい。

提出コード

N=int(input())
left,right=0,1
parity=1
interval=[]
ansList=[]
digit = -1
for i in range(40):
    if parity == 1:
        interval.append((right-2**i+1,right))
    else:
        interval.append((left,left+2**i-1))
    if left <= N and N <= right:
        digit = i
        break
    else:
        if parity==1:
            left -= 2**(i+1)
            parity=-1
        else:
            right += 2**(i+1)
            parity=1
#for (x,y) in interval:
#    print(x,y,y-x+1)
while digit >= 0:
    left,right = interval[digit]
    #print(N)
    if left <= N and N<= right:
        ansList.append('1')
        N -= parity*(2**digit)
    else:
        ansList.append('0')
    digit -= 1
    parity = -parity
ans = "".join(ansList)
print(ans)

D - Candy Distribution

区間の和がMで割り切れる区間が題意を満たします。区間の和ということから累積和を連想すべきです。そして今回はmodだけが問題なので、mod Mの累積和を使うとよいのではないかと思えます。

最初のサンプルで累積和の配列を手で書いてみると、何も足さないという場合を含めて0, 0, 1, 0という累積和の列になります。区間の和のmodが0であるというのは、この累積和の列において始点と終点の値が等しいという言い換えができます。ここでは0が3つあるので、1->2, 1->3, 2->3の合わせて3通りが解になるのだ、と考えるとつじつまが合います。

これを一般化すると、累積和を計算しながら、modの値ごとにそれが何個あらわれるかを記録しておいて、その個数をnとするときにn*(n-1)/2通りの解が存在することがわかります。それをすべてのmod値について加えたものが答えです。

提出コード

N,M=map(int,input().split())
A=list(map(int,input().split()))
cumMods = {}
cummod = 0
cumMods[cummod] = 1
cList = [0]
for a in A:
    cummod += a
    cummod = cummod%M
    cList.append(cummod)
    if cummod in cumMods:
        cumMods[cummod] += 1
    else:
        cumMods[cummod] = 1
#print(cList)
import math
ans = 0
for key in cumMods:
    #print(key,cumMods[key])
    ans += (cumMods[key]*(cumMods[key]-1))//2
print(ans)

感想

modに慣れている人にとってはDが易しいのではないかとおもいました。Dの解き方は比較的すぐ気づけたものの、なぜかΣnを考えるべきところでfactorial(n)と書いてしまい、答えが合わずしばらく時間を浪費してしまいました。紙に色々書いてたら気づきましたが・・・。 Cの実装方針が少し悪かったのか、DよりもCに苦戦した気がします。解説をみたらよりスマートにできるでしょうか。