ABC037 - popleの日記

問題元

abc037.contest.atcoder.jp

A - 饅頭

概要

A円の饅頭とB円の饅頭がある． C円持っている時，最大でいくつの饅頭を買えるか．

解法

価値が同じ，かつ，いくつでも買えるので安い方をめいいっぱい買えば良い．

買える個数に上限ができ，価値がバラバラとなったら，総当りもしくは動的計画法を使うことになる．

A, B, C = list(map(int, input().split()))
print(C // min(A, B))

B - 編集

概要

大きさNの配列が与えられた後，ある区間全てをTに更新するクエリがQ個次々と与えられる．最終的な配列の値を出力しろ．

解法

NとQが小さいのでO(NQ)で愚直に実装すれば良い．

Nが大きい場合，更新する値と更新時間（？）をもたせたSegmentTreeを実装すればO(Qlog(N)+N)かな？

N, Q = list(map(int, input().split()))
ans = [0] * N
for _ in range(Q):
    L, R, T = list(map(int, input().split()))
    for i in range(L-1, R):
        ans[i] = T
print(*ans, sep="\n")

C - 総和

概要

長さNの数列が与えられる．この数列の長さKの連続する部分数列の総和を出力しろ．

解法

愚直にこなすとO(N²)で間に合わない．

真っ先に思い浮かぶのはSegmentTree．つまり，愚直な手法では部分列の和を求めるのに一々インデックスから引いて値を確認しているが，これをlogN個の区間の和の値を見るだけで済ませよう，という考え．

SegmentTreeを使えばO(NlogN)．おそらく間に合う．

先頭がiから始まる区間の和をsumとすると，先頭がi+1から始まる区間の和はsum-arr[i]+arr[i+K]．この関係を利用すると数列を先頭からなめていくだけで済む．O(N)．

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
ans = tmp = sum(A[:K])
for i in range(N-K):
    tmp = -A[i] + tmp + A[i+K]
    ans += tmp
print(ans)

D - 経路

概要

H*Wマスのフィールドそれぞれに数字が振られている．
上下左右数字の小さい方へは移動ができる．
スタート地点は好きに選んで良い．考えられる全ての経路の数を出力しろ．

解法

経路の数が膨大なものになることは容易に想像出来る．経路一つ一つをなぞって行っては到底間に合わない．

こういった場合は動的計画法が有効な場合が多い．というより，経路の総和を求める問題はその典型．つまり，ある地点へ到達する経路の数を求めるには，その地点の丁度一つ前の地点へ到達する経路の数が分かれば十分という性質を利用する．

動的計画法については田山さんの記事が非常に参考になる．

d.hatena.ne.jp

（部分問題の解を求めることで，次の問題の解を求め，最終的な解へ膨らませていく訳だが，その為にまずDAGを意識するべし．というイメージ．）

動的計画法を利用したコードを書く場合，簡単にでも漸化式をメモをしておくと楽に済む． ICPC形式の場合，漸化式の形式で相手に渡すと伝わりやすいため2度美味しい．

ボトムアップに求める場合，順序を決めるのにソートする必要があり計算量 O( ( W * H ) log ( W * H ) )．（実はこれだとPythonでは通らない．ひどい罠だ）

トップダウンに求める場合，計算量 O(W * H)．
（速度がギリギリだったため，Python2かつPyPyを利用している）

import sys
sys.setrecursionlimit(500000)
MOD = 10 ** 9 + 7
H, W = list(map(int, raw_input().split()))
a = [list(map(int, raw_input().split())) for _ in range(H)]
table = [[0] * W for _ in range(H)]
def dfs(x, y, v):
    if a[x][y] >= v:
        return 0
    if table[x][y] > 0:
        return table[x][y]
    ret = 1
    for dx, dy in zip((0, 0, 1, -1), (1, -1, 0, 0)):
        nx, ny = x + dx, y + dy
        if not(0 <= nx < H and 0 <= ny < W):
            continue
        ret = (ret + dfs(nx, ny, a[x][y])) % MOD
    table[x][y] = ret
    return ret
ans = 0
for x in range(H):
    for y in range(W):
        ans = (ans + dfs(x, y, a[x][y]+1)) % MOD
print(and)

ボトムアップ型だとこんな感じ．

from itertools import product
from array import array
MOD = 10 ** 9 + 7
H, W = list(map(int, input().split()))
a = [array("L", map(int, input().split())) for _ in range(H)]
q = list(product(range(H), range(W)))
q.sort(key=lambda x: a[x[0]][x[1]])
table = [array("L", [1] * W) for _ in range(H)]
for x, y in q:
    for dx, dy in zip((0, 0, 1, -1), (1, -1, 0, 0)):
        nx, ny = x + dx, y + dy
        if not(0 <= nx < H and 0 <= ny < W):
            continue
        if a[x][y] >= a[nx][ny]:
            continue
        table[nx][ny] = (table[nx][ny] + table[x][y]) % MOD
print(sum(sum(t) % MOD for t in table) % MOD)

今回とは逆に，呼び出しやら何やらのコストでトップダウン型だと通らない問題も存在するのが非常にタチが悪い．また，配るDPにするか貰うDPにするかで速度が変わる（定数部分が変わる）場合もある．トポロジカル順序にソートするために2要素，3要素を比較しないとならない場合もあるだろう．まだ見たことはないけど，ステートマシーンを回すようなDPもあるらしい．奥が深い．