AtCoder Beginner's Contest 099 の振り返りノート

AtCoder Beginner's Contest 099に参加しました。
目標としていた4問完答ができて、うれしいです。
自分の解法、editorialの解法、ほかの人から聞いた解法など交えつつ、解法に至るまでの思考過程とか、その問題に「どんな要素があったのか」ということを自分の言葉で書いていければいいなとおもいます。

• editorial(公式解説)
• もりい（筆者）の提出コード

A-ABD

import Control.Applicative

main = do
    a <- readLn
    putStrLn $ if a >= 1000 then "ABD" else "ABC"

1000以上かどうかの場合分けで解けます。
最初の3文字だけでよいので、出力は2通りしかないということがポイントでしょうか。
問題文を読んだだけでこの事実に気づかなかったとしても、手で紙に書いて具体例を試すことで気づくことができそうです。

Editorial解もこれと同じなようです。

B-Stone Monument

import Control.Applicative
main = do
    [a,b] <- map read . words <$> getLine
    print $ solve a b

solve a b = right - b
    where n = b-a 
          right = div (n * (n+1) ) 2

もし柱の位置がわかれば等差数列の和の公式

1+2+3+\dots+n = \frac{n(n+1)}{2}

によって高さがわかります。
見ている柱の位置は、この問題では「入力の差が元の柱の高さの差」に等しく、「柱の高さの差は高いほうの柱の位置に等しい」ことからわかります。たとえば、$1+2$は2番目の柱の高さで$1+2+3$は3番目の柱の高さなので、差である$3$は3番目の柱の高さです。よって、

• 入力の差
• =　高さの差
• →　高いほうの位置
• →　高いほうの柱の高さ
• →　雪が積もっている高さ

という流れを式に表すことになります。
Editorial解もこれと同じなようです。

分析

ポイントは、

• 「入力の差から高さの差がわかること」
• 「高さの差から柱の位置がわかること」
• 「柱の位置から元の柱の高さがわかること」

だと思います。問題文を読んで気づかなかった場合でも、「手で具体例を計算」することで気づくことができそうです。 また3つ目の部分は和の公式をしらないこともあるとおもいますが、その場合はforループ等によって計算しても大丈夫です。

「高さの差が、すべての隣接する柱の間で異なっていること」、つまり「ユニークであること」はこの問題から学べる大事な要素かもしれません。

C-Strange Bank

ans = [0] * 100001
ans[0] = 0

n = int(input())

for i in range(1,n+1):
    cand1 = ans[i-1]
    cand2 = 100001
    cand3 = 100001
    x = 6
    while (x<=i):
        cand2 = ans[i-x]
        x=6*x
    y = 9
    while (y<=i):
        cand3 = ans[i-y]
        y=9*y
    ans[i] = min(cand1,cand2,cand3) + 1

print(ans[n])

ぼくの周辺でいちばん会話が多かったのがこの問題でした。いろいろなやりかたがあるみたいですね。ぼくの解はいわゆるDP(動的計画法)と呼ばれるもののうち初歩的なものであるようです（詳しく知らない）。

いま$N$円に対しての解、すなわち最短手順を求めたいとします。これを$ans(N)$とおくことにします。上記コード内でいうところのans[n]です。
その際、「$N-1$円までに対する最短手順$ans(k) (k=1\dots N-1)$がすでにわかっている」と仮定しましょう。

$N$円に対する「初手」を決めたとします。その初手で$x$円を引き出すならば、その初手から始めるという拘束条件をつけたうえでの「最短手順」は$ 1 + ans(N-x)$となるはずです。1は初手の分、$ans(N-x)$は残った金額に対する最短手順です。

初手のバリエーションは限られている（制約上、10個くらいしかないそうです）ので、すべての可能な初手について「その初手によるときの最短手順」を求め、「それらの中での最短手順」を次に求めることで、「本当の最短手順$ans(N)$」が計算できます。

「$N-1$円までに対する最短手順$ans(k) (k=1\dots N-1)$がすでにわかっている」と仮定したのですが、これを満たすためには、「N=0から順番に計算してゆき、計算結果を覚えておく」ことをすればよいです。

なお、ぼくのコードでは6,9それぞれの累乗について「引き出すことのできる最大値」のみを比較候補に挙げています。$ans(x)$は$x$について非減少関数、つまり$x>y$ならば$ans(x) \geq ans(y)$なので、これで大丈夫（のはず）です。もっとも最大値をもとめるところがwhileループなので、結局全累乗をたどっていることになり、僕のコードでは特段速くできているわけではないとおもいます。

D-Good Grid

N,C = map(int,input().split())

d = []
c = []
for i in range(C):
    raw = list(map(int,input().split()))
    d.append(raw)

for i in range(N):
    raw = list(map(int,input().split()))
    c.append(raw) 

colorNum = [[0] * 3 for _ in range(C)]

for i in range(N):
    for j in range(N):
        colorNum[c[i][j]-1][(i+j)%3] += 1

#print(colorNum)

minimum = 1000*500*500

def calc(i,j,k):
    cost = 0
    for color in range(C):
        c0 = colorNum[color][0]
        c1 = colorNum[color][1]
        c2 = colorNum[color][2]

        cost += c0 * d[color][i]
        cost += c1 * d[color][j]
        cost += c2 * d[color][k]
    return cost


for i in range(C):
    for j in range(C):
        if i==j:
            continue
        for k in range(C):
            if j==k or i==k:
                continue
            cand = calc(i,j,k)
            minimum = min(minimum,cand)

print(minimum)

上記コードはEditorial解と同様の解法によるものです。
なので解法は省略して、思考のプロセスを振り返っていきます。D問題におよそ1時間かかったからです。

まずサンプルの例を手で計算しました。ここでグリッドが3つのグループに分かれるのだということには気づくことができました。

次に色分けの仕方がいくつあるか考えました。30*29*28以下になることがわかります。
N^2が250000で、掛け算すると10^9を超えます。このままだと無理そうだから、何かうまくしないといけないかな、と思っていました。ここでもう少しよく考えれば、早く解けたかもしれません。しかし、別なことが頭をよぎってそちらに気を取られてしまいました。

というのも、少し前に最小値問題について「xで実現できるかの判定問題」を解き、「xについてのバイナリサーチ」をするという方法を見たことがありました。そこでこのアプローチができないか？ということが頭をよぎったのです。しかし、この問題の場合判定問題として捉えたとしても結局最小値問題と同じようなことをしなければならないと気づき、この方針を捨てました。

そうして冷静に問題を見直してみると、3つのグループごとに高々30通りの色の数を覚えておけば全コスト（違和感）を計算できるのだから、90*30*29*28と、前処理のN^2分で解けることに気づきました。これならきっと間に合うでしょう。

ただPython3で間に合うのかどうか自信がなく、慣れないC++で書こうとして挫折するなど、実装でも少し時間をロスしました。Python3で書いてだめならあきらめよう、と思って書いてみたところ、500ms台と、やはり速くはないもののACすることができました。

おわりに

はじめに「ほかの人から聞いた解法など交えつつ、」などと書きましたがそんなことしてたら時間かかりすぎて熱が冷めてしまいそうなので、もう投稿します。
コンテスト直後にブログ書く人はすごいなぁ...