2015-06-24

SRM661 Div2(hard)復習

ちょっと前にSRM661 Div2のeasyとmedを復習したんですが, hardもやっと解けました.

あとこの前のTCO Round2B で無謀にもチャレンジしたせいでレートが200下がって一気に灰色まで落ちました. 泣きたい..

hard(950) : ColorfulLineGraphsDiv2

問題文のおおよその意訳

ボブは以下の２つの手順でN個の節点からなるグラフを作ろうとしている.

1からNの番号をつけた節点を用意し, それぞれの節点にはK色のうちのいずれか一色で色を塗る.
それぞれの節点i $(2\leq i \leq N)$ から, 節点iと色の異なる節点j $( j\lt i )$ に枝を張る. ただし, ボブは枝を張らないこともある.

N $(1 \leq N \leq 100)$ とK $(1 \leq K \leq 3)$ が与えられたとき, ボブが作りうるグラフの数を求め, $10^9+7$ で割った余りを答えよ.

解法

枝の張り方は色さえ決まっていたらO(N)で求められますが, そもそも色の塗り方が $K^N$ , 最悪 $3^{100}$ あるので, 塗り方ごとに枝の張り方を考えて数えるなんて事は到底無理. さてどうするか.

色々悩んだんですが, 最終的にDPになりました. 例えば, K=2として以下のようにN=2のグラフにもう一つ節点を加えてN=3のグラフを作ることを考えます.

f:id:Tawara:20150624001112p:plain

まず三つめの節点から枝を張らない場合, 好きな色の節点(赤か青)を三つ目の節点に選べるので2通り作れます. 次に三つ目の節点から枝を張る場合, 一つ目の節点に枝を張りたいなら青以外の色, すなわち赤を三つ目の節点に, 二つ目の節点に枝を張りたい場合は青を三つ目の節点に選ぶ必要があります. よって枝を張る場合も2通り作れて, 合計4通り作れます.

上のことは書いてみると結構当たり前のことなんですが, 枝を張る場合と張らない場合を分けて考えるのが一番のポイントなんじゃないかなーと思います. 三つ目の節点の色を決めてから枝を張れるかどうか考えると非常にややこしいんですが, 分けて考えてしまうととても楽です. 枝を張る先ごとに色を決めるってのが超重要.

因みに3色の場合も同様に以下のように考えられます.

f:id:Tawara:20150624003708p:plain

枝を張らない場合は3通りで, 枝を張る場合は張る先の節点以外の色を三つ目の節点の色に使えるので2*2=4通り, 合計7通りです.

もうちょっと一般的にn-1個の節点からなるグラフにn個目の節点を加えてグラフを作ることを考えると, 枝を張らない場合は単純にK通り, 張る場合は枝を張る先の節点i ( $1\leq i \leq n-1$ )ごとにn個目の節点にiと違う色すなわちK-1色のいずれかを選ぶことになるので, 作り方は

$K + (n-1)(K-1)$

通りとなります. よってボブの作りうるn個の節点からなるグラフが $a_n$ 通りだとすると, 漸化式

$a_{n+1} = a_n \lbrace K + n(K-1)\rbrace$

が成り立ちます. あとはこの式でn = 1からNまで順に求めていけば終わりです.

実装

前述の漸化式実装するだけなのでめちゃくちゃシンプルになりました.

class ColorfulLineGraphsDiv2:
    def countWays(self, N, K):
        mod = 10**9+7
        result = 1
        for i in range(N):
            result *= (K + i*(K-1)) % mod
        return result % mod

終わりに

後から聞いたんですが, Div2は制約が緩いのでここまでちゃんとやらなくても解けたらしいです(その分コードは長くなりそうですが). 逆にDiv1では制約が恐ろしいことになってて( $10^{12}$ とか), 単に漸化式作るだけでは無理だったそうな.

なにはともあれ, これでSRM661は終わりです. この調子で今までの宿題も少しずつ解いていきたい.

f:id:Tawara:20150624011117p:plain

2015-06-13

SRM661 Div2(Easy, Med)復習 —ワーシャルフロイドに惑う—

昨日の朝にあったSRM661に参加しました。

DIV1に上がってやるぜとか意気込んでたのにEasyしか解けなかった..しかも結果的にはMedはけっこう簡単だったみたいで、非常につらい。

Hardにたどり着けてないので宿題に..こんなことばっか言ってるなあ。

Easy (250) : FallingSand

(問題文のおおよその意訳)

正方形のマス目に分かれた長方形のボードが与えられ、いくつかのマスに障害物が、いくつかのマスに砂粒がある。この盤を立てたときの最終的なボードの状態を答えよ。ただし障害物は動かず、砂粒は何も無いマスにのみ落ちるものとする。(一マスに砂粒は一つしか入らない)。

これは単にシミュレーションするだけでした。stringで与えられるのがちょっとめんどくさいですね。

class FallingSand:
    def simulate(self, board):
        b = [list(s) for s in board]
        r = len(b)
        c = len(b[0])
        for i in range(c):
            for j in range(r-2,-1,-1):
                if b[j][i] == "o":
                    for k in range(j,r-1): 
                        if b[k+1][i] == ".":
                            b[k][i] = "."
                            b[k+1][i] = "o"
                            continue
                        break
        ans = tuple("".join(s) for s in b)
        return ans

Med (500) : BridgeBuildingDiv2

(問題文のおおよその意訳)

大きさがN( $2 \le N \le 11$ )の２つの節点列A,Bが与えられる。それぞれの列の隣り合う接点は辺で結ばれており、Aのi番目の節点とi+1番目の節点の間の辺の長さはa[i]、Bのi番目の節点とi+1番目の節点の間の辺の長さはb[i]である。ここで、長さ0のK本( $1 \le K \le N-1$ )の新しい辺をAの節点とBの節点の間に加えることを考える(ただし、辺を加えられるのはAのi番目の節点とBのi番目の節点(i=0,1, ... , N-1)の間のみ)。

新しい辺を加えてできたグラフについて、二節点間の最短距離のうち最大のものをグラフの直径と定義する。グラフの直径が最小になるようにK本の辺を加えたときのグラフの直径を求めよ。

f:id:Tawara:20150613010359p:plain

全点対距離..いつか勉強したワーシャルフロイドを使うときが来た！と、思ったのですが、N本からK本を選んで新しい辺を加え、そこから計算することを考えると、計算量は $_NC_k \times (2N)^3$ 、N = 11, K = 6のときなら $_{11}C_6 \times (22)^3 = 4919376 \fallingdotseq 5.0 \times 10^6$ 。ああ、pythonあかんやつやんこれ..

それでC++で実装しようとしたんですけど、組み合わせの列挙どうしたら良いんやってあーだこーだしてて終了致しましたorzやっぱ普段からやってないと駄目ですね。

どうやら全点についてダイクストラ法を用いると、計算量が $_NC_k \times (2N+(2(N-1)+K)) \log2N$ ぐらいなんでそれで行けたっぽい..のですが、やっぱpythonでもワーシャルフロイドで通したい！ってことで考えてみました。

ワーシャルフロイドでは、ある中継点kを考えたときの(i-k間の距離＋ k-j間の距離)と現時点のi-j間の距離の小さい方をi-j間の距離とするのを繰り返すことで全節点対の最短距離を求めます。ここで、通常は中継点に全節点を用います。今回はAの節点を0, .., N-1、Bの節点をN, ..., 2N-1 として

for k in range(2*N):
        for i in range(2*N):
                for j in range(2*N):
                        d[i][j] = min(d[i][j], d[i][k]+d[k][j])

をK本の新しい辺の加え方ごとにやることになります。ただこれでは計算量がよろしくない。

よくよく考えると、新しい辺を加えたときにある二節点間の最短距離が更新されるなら、その経路は絶対にいずれかの新しい辺を通ることが分かります。となれば、まず節点列A,Bそれぞれの中で全節点対の最短距離を求めておいた後に、新しく加えた辺の両端の節点のみを中継点としてワーシャルフロイドを実行すればいけそう。

for k in inter: #interはいずれかの新しい辺の両端の節点
        for i in range(2*N):
                for j in range(2*N): 
                        d[i][j] = min(d[i][j],d[i][k]+d[k][j])

というわけで以下のようになりました。

import itertools, copy

MAX = 1000
class BridgeBuildingDiv2:
    def minDiameter(self, a, b, K):
        N = len(a)+1
        d = [[MAX for j in range(2*N)] for i in range(2*N)]

        ## 距離の初期化
        for i in range(2*N):
            d[i][i] = 0

        for i in range(N-1):
            d[i][i+1] = d[i+1][i] = a[i]
            d[N+i][N+i+1] = d[N+i+1][N+i] = b[i]

        ## 節点列A,Bごとに全節点対の最短距離を計算
        for i in range(N-2):
            for j in range(i+2,N):
                d[i][j] = d[j][i] = d[i][j-1] + d[j-1][j]
                d[N+i][N+j] = d[N+j][N+i] = d[N+i][N+j-1] + d[N+j-1][N+j]

        ans = MAX
        ## 新しい辺の加え方ごとにワーシャルフロイドを行う
        for bridge in itertools.combinations(range(N),K):
            tmpd = copy.deepcopy(d)
            for k in bridge:
                tmpd[k][N+k] = tmpd[N+k][k] = 0
            ## 中継点は新しい辺の両端のみ
            inter = list(bridge) + [N+i for i in bridge]
            for k in inter:
                for i in range(2*N):
                    for j in range(2*N): 
                        tmpd[i][j] = min(tmpd[i][j],tmpd[i][k]+tmpd[k][j])

            ans = min(ans, max(max(tmpd[i]) for i in range(2*N)))
        return ans

最悪計算量はN=11, K=6のときの $_{11}C_6 \times (2\times 6) \times (22)^2 = 2683296 \fallingdotseq 2.7 \times 10^6$ 。え？あんまり変わってない？いやpythonは $10^6$ の世界入るととってもシビアなんでちょっとの削減がめっちゃ大事です。

さあシステムテストだ！

f:id:Tawara:20150613123942p:plain

やりました！ワーシャルフロイドは見た目より速いって聞いてたけど $2.7 \times 10^6$ でも通るもんなんですねえ。テストケースに一番最悪のケースが無いのもありますが、手元ではいけてました。いやー満足した！

かに見えた..

ところで、通常のワーシャルフロイドだとシステムテストではどれくらいかかるのでしょうか？まあTLEになるんでしょうけど気になるからやってみましょう！

f:id:Tawara:20150613123946p:plain

って通るんかーい！！僕のここまでの苦労は何だったんでしょうか... システムテストの最悪ケースは N= 11, K=7なので、計算量は $_{11}C_7 \times (22)^3 = 3513840 \fallingdotseq 3.5 \times 10^6$ 、まあたしかに雑魚いから仕方ないか？

と思って、ワーシャルフロイドで解いてるpythonistaの皆さんに手当たり次第N=11, K=6でchallengeしたんですが弾かれちゃいました。色々考えたのに結局単純なワーシャルフロイドで通るとかつらい..

終わりに

結局僕の空回りでしたが、グラフの連結部だけに注目するってのはまた使うことになりそうな気がします。どっかで今回の考察が活きると信じよう。

Hardも解きたいし、C++での実装と全点ダイクストラも一応やっときたい、というところで今回は終わりです。あと全く関係ないですがCodeforces #307が全然解けなくて泣きそうでした。

2015-05-24

ABC024復習

昨日のABC024に参加しました。

<a href="http://abc024.contest.atcoder.jp/">Welcome to AtCoder Beginner Contest 024 - AtCoder Beginner Contest 024 | AtCoder</a>abc024.contest.atcoder.jp

前回(ABC023)に比べるとオーダーの制約は優しかったんですけど、Dが解けなくて残念。でも逆元の話とか勉強になりました。

A - 動物園

動物園の一人当たりの料金(こどもA円、大人B円)が与えられるので、こどもがS人、大人がT人だったときの料金を求める問題。

団体割引さえちゃんと考慮すれば特に問題ないです。

A, B, C, K = map(int,raw_input().split(" "))
S, T = map(int,raw_input().split(" "))
print S * A + T * B - (0 if S + T < K else C * (S+T))

B - 自動ドア

N人のお客さんそれぞれが店を訪れる時刻と自動ドアが開いてから閉まるまでの時間が与えられるので、自動ドアが空いていた合計時間を求める問題。

こういう問題は時間をインデックスにとる配列を埋めていく解法がわかりやすいんですが、制約が $1 \leq A_i \leq 10^6$ , $1 \leq T \leq 10^5$ なのでつらいです。 $10^6 + 10^5 = 1.1 \times 10^6$ の大きさの配列とかなめるだけでTLEの気配が漂ってきますわ。解説の満点解法も $10^6+T$ だけfor文回すので、python的にはギリギリな感じ。

そもそも最初から配列を使う必要は無くて、

f:id:Tawara:20150524032206p:plain

i人目のお客さんが来たときに

まだドアが開いていれば、被っている時間(赤い部分)をTから引いた分だけ加算する
ドアが閉じていればTだけ時間を加算する

という方針で行きました。(図がでかい(^_^;;)) これなら計算量O(N)なのでpythonでも問題なく通ります。

N, T = map(int,raw_input().split(" "))
total = 0
time = 0
for i in range(N):
    A = int(raw_input())
    if A > time:
        total += T
    else:
        total += A + T - time
    time = A + T
print total

あとからよくよく考えると, 自動ドアが開き続ける時間Tが一定だからこんなにシンプルに書けてるんだなあと。ドアの開き続ける時間がバラバラだと、もう少しだけ工夫が必要ですね。

(追記) 解説放送でimos法でやったってコメントがあったのでやってみました。

N, T = map(int,raw_input().split(" "))
MAX = 10**6+T
time = [0 for i in range(MAX+1)]
for i in range(N):
    A = int(raw_input())
    time[A-1] += 1
    time[A+T-1] -= 1
for i in range(MAX):
    time[i+1] += time[i]
print sum(map(bool, time))

計算量はO(10**6+T)、時間は1206msでした。上の配列を使わない方法は376ms。オーダーが一桁違うだけで大分違いますね。

C - 民族大移動

それぞれの民族が目的の街に移動できる一番早い日を答える問題。

幸いにして大移動が行われる日数Dと民族の数Kの制約が $1 \le D \le 10^4, 1 \le K \le 100$ だったため、難しいこと考えずに民族ごとに何日でたどり着けるか求めれば大丈夫でした。さっさと愚直に解いたら良かったorz

解説では貪欲に解けるって話をされていて、言われてみればそうだなって感じです。まあやってたときはそこまで考えが至らなかったので、民族iが現在移動できる範囲 $B_i$ とその日の移動できる範囲 $B_{day}$ について

$B_i \cap B_{day} \neq \emptyset$ であれば、移動できる範囲を $B_i =B_i \cup B_{day}$ に更新
$B_i \cap B_{day} = \emptyset$ なら $B_i$ を更新しない

という操作を繰り返し、 $B_i$ を更新したときに $T(目的地) \in B_i$ であればOKという方針でやっています。

N, D, K = map(int,raw_input().split(" "))
LR = [map(int,raw_input().split(" ")) for i in range(D)]
for i in range(K):
    S, T = map(int,raw_input().split(" "))
    move_L = S
    move_R = S
    for day in range(D):
        L, R = LR[day]
        if L <= move_L <= R or L <= move_R <= R:
            move_L = min(L, move_L)
            move_R = max(R, move_R)
            if move_L <= T <= move_R:
                break
    print day + 1

貪欲な方法もあとからやってみました。

def move_right(S,T):
    H = S
    for day in range(D):
        if LR[day][0] <= H <= LR[day][1]:
            H = LR[day][1]
            if S < T <= H:
                break
    return day + 1
    
def move_left(S,T):
    H = S
    for day in range(D):
        if LR[day][0] <= H <= LR[day][1]:
            H = LR[day][0]
            if H <= T < S:
                break
    return day + 1

N, D, K = map(int,raw_input().split(" "))
LR = [map(int,raw_input().split(" ")) for i in range(D)]
for i in range(K):
    S, T = map(int,raw_input().split(" "))
    print move_right(S, T) if S < T else move_left(S, T)

わざわざmove_leftとmove_right作ってるんですが、pythonはif文が遅いのでこれが大分効いてます。ちなみに範囲でやる方が680ms, 貪欲の方が360msでした。

D - 動的計画法

高橋君が破いてしまった紙が、動的計画法で埋めたマス目の何処に当たるかを探す問題。

最初二分探索で頑張ろうとしてたりしたんですけど、10⁸以上の階乗が必要になってきてどうしようってずっと悩んでました。あとから方程式で求めれるって気付いたときにはもう手遅れ。けど逆元の事分かってなかったのでどっちにしろ無理だったと思います。

(0,0)から(r,c)への右と上にだけ進める場合の行き方が $_{r+c}C_r$ であるので, 入力A, B, Cより

$_{r+c}C_r = A \Leftrightarrow \displaystyle \frac{(r+c)!}{r!c!} = A \ \ \ \ \ \ \ \ \cdots (1) \\ _{r+c}C_r = B \Leftrightarrow \displaystyle \frac{(r+c+1)!}{r!(c+1)!} = B \ \ \cdots (2) \\ _{r+c}C_r = C \Leftrightarrow \displaystyle \frac{(r+c+1)!}{(r+1)!c!} = C \ \cdots (3)$

(1)と(2), (2)と(3)を組み合わせて、

$\displaystyle \frac{r+c+1}{c+1} = \frac{B}{A} \\ \displaystyle \frac{r+1}{c+1} = \frac{B}{C}$

この連立方程式を解いたものがこちら。

$\displaystyle r = \frac{BC - AC}{AC - BC + AB} \\ \displaystyle c = \frac{BC - AB}{AC - BC + AB}$

右辺を $10^9+7$ でmodをとったものが答えになるの実は少し納得いってないんですが、時間がないので割愛。

で、今回一番勉強になったのは逆元の話でした。 $A \equiv a, B \equiv b, C \equiv c$ であったとき,

$A \div B = C \Rightarrow a \times (bの逆元) \equiv c$

が成り立つというもの。加減乗算に関してはmodとっても大丈夫だと知ってましたが、除算だとこんなことするんですね。そしてこの逆元ですが、法が素数pであった場合はフェルマーの小定理により

$X^{p-1} \equiv 1 \\ \therefore X^{-1} \equiv X^{p-2}$

が成り立つそうです。 $10^9+7$ は素数なので使うことが出来ます。

そしてもう一つ勉強になったのは冪乗を高速に求めるアルゴリズム。解説聞いたときにピンと来てなかったんですが、あとから納得しました。

$X^N$ を求めるときに、Nの二進数表示を考えると、

$X^N = \prod_i X^{2^i}$

の形に分解できることを利用してます。例えばN = 11 なら二進表記は1011なので

$X^N = X^{2^0} \times X^{2^1} \times X^{2^3}$

に分解できるわけですね、なるほどなるほど。これを利用すれば $X^{p-2}$ を高速で求められるのでXの逆元を求めれます。

def mod_inv(X, N):
    result = 1
    prod = X
    inc = 0
    while (1<<inc) <= N:
        if (N>>inc) % 2 == 1:
            result = (result * prod) % p
        prod = (prod**2) % p
        inc += 1
    return result % p

A = int(raw_input())
B = int(raw_input())
C = int(raw_input())
p = 10**9+7
r_nume = (B*C - A*C) % p 
c_nume = (B*C - A*B) % p
deno = mod_inv((A*C - B*C + A*B) % p, p-2)
print (r_nume * deno) % p, (c_nume * deno) % p

因みにpythonのpow関数は $X^a \ \% \ b$ を求めてくれる超便利機能があって、

A = int(raw_input())
B = int(raw_input())
C = int(raw_input())
p = 10**9+7
r_nume = (B*C - A*C) % p 
c_nume = (B*C - A*B) % p
deno = pow((A*C - B*C + A*B) % p, p-2, p)
print (r_nume * deno) % p, (c_nume * deno) % p

と書けちゃいます。ただ冪乗の高速計算は他でも使えそうな知識なので覚えていて損はなさそうです。

次のABCこそは全完目指したいなあ。

2015-05-17

ARC039復習 (A,B,C)

昨晩ARC039に参加しました。

<a href="http://arc039.contest.atcoder.jp/">Welcome to AtCoder Regular Contest 039 - AtCoder Regular Contest 039 | AtCoder</a>arc039.contest.atcoder.jp

また死んだよ..orz というわけで復習です。相変わらずARCはDは解くまでに至らないので省略します。そのうちARCボスラッシュならぬDラッシュで復習記事書きたいですね。

A - A - B problem

三桁の整数A, B (100 ≤ A,B ≤ 999)が与えられるので、AかBのどれか一桁を変えたときの(変えなくても良い)A-Bの最大値を答える問題。

一瞬めんどくさいこと考えようとしましたが結局全通りすることに。strでやると楽ですよね。

A,B = raw_input().split(" ")
inA = int(A)
inB = int(B) 
chA = max(int("9"+A[1]+A[2]), int(A[0]+"9"+A[2]), int(A[0]+A[1]+"9"))
chB = min(int("1"+B[1]+B[2]), int(B[0]+"0"+B[2]), int(B[0]+B[1]+"0"))
print max(chA-inB,inA-chB)

Bの一と十の位を0にできることに気付かずにWA出したのは本当にしょうもなかったです。

B - 高橋幼稚園

N人の園児にK個の飴を配るときその幸福度(各園児の持つ飴の数の積)が最大になるような配り方が何通りか求める問題。

N ≤ K の場合は、要は園児に出来るだけ均等に配りましょうって事なんですよね。感覚的には納得できるけど、なぜそれで最大化できるのか？って言われると答えられない..勉強します。

N > Kの場合は、どう配ろうが幸福度が0になるので全通りを求める。即ち重複組み合わせの話になります。B問題はこれを知ってるかどうかで100点取れるか決まったようなもんです。

5人の園児に2個の飴を配る場合は $_5H_2= \ _{5-1+2}C_2 = \frac{6\times5}{2\times1} = 15$ になります。

まあ $_NH_K$ の記号の意味とか覚えなくても、4つの仕切りで飴2つをどう区切るかって話でして、

園児1　園児2　園児3 　園児4　　園児5

　　　| 　　　| 　　　| ◯ ◯ I

これだと園児4が飴を総取りすることになるといった感じに。高校数学は本当に懐かしいです。

from math import factorial as fact
N, K = map(int,raw_input().split(" "))
if N > K:
    print (fact(N-1+K) / (fact(N-1) * fact(K))) % 1000000007
else:
    R = K % N
    print (fact(N)/(fact(N-R)*fact(R))) % 1000000007

偉そうに重複組み合わせの説明したんですけど、実は10⁹+7で割るの忘れてWA出したんですよね。自分の不注意さが情けない。あとpythonだとパスカルの三角形作らなくてよいので実装が楽でした。

C - 幼稚園児高橋君

二次元格子をK回動き回った高橋君の位置を特定する問題。

愚直にシュミレーションするともちろん間に合わないので、さあどうしようって言ってたら時間が終了しました(-_-;) DancingLinksってデータ構造、これからも覚えときたいですね。

pythonでどうにかこうにか通せたんですけど、重要なのは遅延評価ですよね。新しいマスに移動する度に、そこから「右、上、左、下」の4方向に次に進んだ場合にたどり着く先を全部計算していては間に合わない。

ということで、新しいマス(next)に移動してきた際に(例として右に進んできたとする)、

右の近傍は自分の右のマスにする
左の近傍は移動元(here)のマスの左近傍にする
上の近傍は自分の上のマスにする
下の近傍は自分の下のマスにする

とし、加えて

移動元(here)の右の近傍を、移動先(next)の右の近傍にしておく

としました。それで、移動する段階になって初めて、その方向の近傍を繰り返し辿ることで本当の移動先にたどり着きます。

# -*- coding:utf8 -*- #
def update(here, d):
    ## d方向の近傍をひたすら辿って移動先まで行く
    next = (here[0] + dxy[d][0], here[1] + dxy[d][1])
    while next in visited: 
        next = visited[next][d]

    ## 4近傍を設定
    neighbor = [None, None, None, None]                                        ## 移動先の4近傍
    neighbor[d] = (next[0] + dxy[d][0], next[1] + dxy[d][1])                   ## d方向の近傍
    neighbor[(d+2)%4] = (here[0] + dxy[(d+2)%4][0], here[1] + dxy[(d+2)%4][1]) ## d方向と逆方向の近傍 
    for i in [(d+1)%4, (d+3)%4]:                                               ## その他の方向の近傍
        neighbor[i] = (next[0] + dxy[i][0], next[1] + dxy[i][1])

    ## 移動元のd方向の近傍を更新
    visited[here][d] = neighbor[d]
    ## 移動先を訪問済みとして登録
    visited[next] = neighbor
    return next

dxy = ((1,0),(0,1),(-1,0),(0,-1))
direction = {"R":0,"U":1,"L":2,"D":3}
K = int(raw_input())
S = list(raw_input())
here = (0,0)
visited = {here:[(1,0),(0,1),(-1,0),(0,-1)]}
for s in S:
    here = update(here, direction[s])
print here[0], here[1]

時間制約考えると遅延評価って大事ですね。Segment Treeとかもそのうちちゃんと実装しないといけないなあと思います。

結果はボロボロでしたが勉強にはなりました。そのうちDも解こう！

おまけ：Bについて(5/18に追記)

N ≤ K の場合、園児に均等に配ると良いのがどうしてかよくわからんって話だったんですけど、これ普通に計算したら良いんじゃね？と思ったのでやってみることにしました。

園児 $i$ に配る飴の数を $c_i (≥ 1)$ と置くと以下の最大化問題を解くことになります。

$max. \prod_{i=1}^Nc_i \\ \ \ \ s.t. \sum_{i=1}^Nc_i = K$

一つ目の式が最大化したい目的関数、二つ目が制約条件です。さらに、計算を簡単にする為に目的関数を対数を取ったものに変更して、

$max. \sum_{i=1}^N \log c_i \\ \ \ \ s.t. \sum_{i=1}^Nc_i = K$

を考えます。

さて、制約条件の下で最大化するということでラグランジュの未定乗数法を使ってみることにしました。本当は関数の凸性の話とかあるんですが、これについてはまた機械学習の方の記事で書く予定です。なので今回は仕組みの話はスルーで行きます。

ラグランジュの未定乗数法 - Wikipedia

ラグランジュの未定乗数法では新たに変数λを導入し, 以下のラグランジュ関数を考えます。

$L(c_1, .. , c_N,\lambda) = \sum_{i=1}^N \log c_i + \lambda(\sum_{i=1}^Nc_i - K)$

そしてこれを $c_1, .. , c_N, \lambda$ で偏微分することにより以下を得ます。

$\displaystyle \frac{\partial L}{\partial c_i} = \frac{1}{c_i} + \lambda \ \ \ \ \ \ \ \cdots \ (i) \ \ \ \ \ \ \ (i = 1,2, ..., N )\\ \displaystyle \frac{\partial L}{\partial \lambda} = \sum_{i=1}^Nc_i - K \ \ \cdots \ (N+1)$

これらの式(今回はN+1個)を=0としたときの連立方程式を解くことで、目的関数を最大化することができます。ちなみに式(N+1)=0はそのまま制約条件を表してますね。

式(1)~(N)を=0としたものは全く同様の変形を行い,

$\displaystyle c_i = -\frac{1}{\lambda} \ \ \ (i = 1,2,..,N)$

となります. あとは式(N+1)により,

$\displaystyle \sum_{i=1}^N (-\frac{1}{\lambda})- K = 0 \\ \displaystyle -\frac{N}{\lambda} = K \ \ \ \therefore \lambda = -\frac{N}{K}$

したがって

$\displaystyle c_i = \frac{K}{N} \ \ \ (i = 1,2,..,N)$

となり,園児に渡す飴の個数が均等であれば良いことが分かりました！といっても $c_i$ は自然数じゃないとダメなのでこのまま答えにしたらダメなんですけど、できるだけ均等にした方が良いってことは分かりましたね。

最初に言ったようにラグランジュの未定乗数法についてはまた書く予定です。最尤推定とかでほぼ確実に使うのでちゃんと復習しようと思います。

さらにおまけ: Bについてその2(5/18に追記)

上のおまけを更新後、友人から「いやもっと簡単に示せるやろ」と突っ込みを受けたので紹介します。

実数 $x,y$ について,

$「y \geq 2 \Rightarrow x(x+y) \lt (x+1)(x+y-1)」$

が成り立つことを使えば終わりやろって言われました(^_^;)

この証明は以下のように簡単に出来ます。

$(x+1)(x+y-1) - x(x+y) \\ = (x+1)(x+y)-(x+1)-x(x+y) \\ = (x+y) - (x+1) = y - 1 \geq 1 \gt 0 \ \ (\because y \geq 2)$

これを使って例えばN=3、K=10の場合を考えます。

まず園児1に10-2=8個, 園児2,3に1個づつ飴を与えておいて

$(1+7) \times 1 \times 1 \lt (1+6)(1+1) \times 1 \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \lt (2+4) \times 2 \times (1+1) \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \lt (2+3)(2+1)\times 2 \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \lt (3+1)\times3\times3 = 4 \times 3 \times 3 = 36$

のようにすると最大値をとるのは飴を出来るだけ均等にした場合であることが分かります。

聞いたらなるほどって感じです。僕の頭でっかちさが露呈しました。

俵言

しがない社会人が書く、勉強とかのこと。最近は機械学習や kaggle 関連がメイン。

SRM661 Div2(hard)復習

hard(950) : ColorfulLineGraphsDiv2

問題文のおおよその意訳

解法

実装

終わりに

SRM661 Div2(Easy, Med)復習 —ワーシャルフロイドに惑う—

Easy (250) : FallingSand

Med (500) : BridgeBuildingDiv2

かに見えた..

終わりに

ABC024復習

A - 動物園

B - 自動ドア

C - 民族大移動

D - 動的計画法

ARC039復習 (A,B,C)

A - A - B problem

B - 高橋幼稚園

C - 幼稚園児高橋君

おまけ：Bについて(5/18に追記)

さらにおまけ: Bについてその2(5/18に追記)