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$