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$

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

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

2015-05-16

ARC037復習 (A,B,C)

開催は4/18だったので一ヶ月近く前のやつですね。

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

このときもなかなかにボロボロでありました。解説聞いたけどちゃんと復習終わってないからやることに。ただD問題は参加時にそもそも問題を読むことすら出来なかったのでまたそのうちに。

A - 全優

未来視した点数が80点を下回るならその分だけ勉強時間を割いてあげましょうって問題。

まあAはいいですよねAは。

N = int(raw_input())
m = map(int,raw_input().split(" "))
print sum([0 if m[i] >= 80 else 80 - m[i] for i in range(N)])

lambda式使えばさらにまとめられるなーと思いましたけど特に意味はなかった。

N = int(raw_input())
print sum(map(lambda x: 0 if int(x) >= 80 else 80 - int(x), raw_input().split(" ")))

B - バウムテスト

与えられた無向グラフにおいて閉路を持たない連結成分(木)の個数を求める問題。

一応通したものの、見返すと40行ぐらいのなかなかひどいコード書いてました。pythonは可読性が売りなのにこれは無い。

方針としては、木を節点の集合(set())で表すことにして、

辺の両端の二節点のどちらも既存の木に属してない → 新しく木を生成
辺の両端の二節点の片方だけが既存の木に属している → 属してない方をその木に属させる
辺の両端の二節点の両方が既存の木に属している→
- 属している木が同じ → 閉路があるので木ではない
- 属している木が異なる → 和集合をとって一つの木にする

それで最後に木の数と一度も使われてない節点の数の合計を返すって方針でした。

N, M = map(int,raw_input().split(" "))
tree_num = 0
tree_set = []
unused = set(range(1,N+1))
for i in range(M):
    u, v = map(int,raw_input().split(" "))
    if u in unused:
        unused.remove(u)
        if v in unused:
            unused.remove(v)
            tree_set.append([1,set([u,v])])
            tree_num += 1
        else:
            for j in range(tree_num):
                if v in tree_set[j][1]:
                    tree_set[j][1].add(u)
                    break
    else:
        if v in unused:
            unused.remove(v)
            for j in range(tree_num):
                if u in tree_set[j][1]:
                    tree_set[j][1].add(v)
                    break
        else:
            for j in range(tree_num):
                if u in tree_set[j][1]:
                    for k in range(tree_num):
                        if v in tree_set[k][1]:
                            if j == k:
                                tree_set[k][0] = 0
                            else:
                                tree_set[j][0] &= tree_set[k][0]
                                tree_set[j][1] |= tree_set[k][1]
                                tree_set.pop(k)
                                tree_num -= 1
                            break
                    break
print sum([tree_set[i][0] for i in range(tree_num)]) + len(unused)

うん、クソですわ。対比の為に置いたけどこれはひどいw 同じ方針でももっと綺麗に書けると思うんですけどめんどくさくなっちゃいました。

で、解説で説明された方針は幅優先探索(dfs)を行うってものでした。探索済みのものにチェックして行って、探索中に探索済みにものに出会ったらそれは閉路だろって方針。実装してみて分かったんですが、単純に全節点を始点としてdfsを行い、一度も探索済みの節点に出会わなければ1を返すってだけで良かったんですね。

def dfs(here, before):
    is_tree = True
    if searched[here]:
        is_tree = False
    else:
        searched[here] = True
        for next in link[here]:
            if next == before:
                continue
            is_tree &= dfs(next, here)
    return is_tree

N, M = map(int,raw_input().split(" "))
tree_num = 0
searched = [0 for i in range(N)]
link = [[] for i in range(N)]
for i in range(M):
    u, v = map(int,raw_input().split(" "))
    u -= 1; v -= 1
    link[u].append(v)
    link[v].append(u)
print sum(dfs(i,-1) for i in range(N))

さっきより大分すっきりしました。シンプルにかける方が筋が良いって言葉が耳に痛い。

C - 億マス計算

N²マス計算を行ったとき小さい方からK番目の数を求める問題。

1≤N≤3.0*10⁴ であるため当然ながら全部を計算することは不可能ですよね。オンタイムのときは行成分と列成分をとりあえずソートすると何か出来そうな気がする、ぐらいしか思いつかなくてもう何も出来ませんでした。

「小さい方からK番目の値がXである」を「X-1以下の数はK個未満だがX以下の数はK個以上ある」って感じで言い換えるの身に付いてないっすねえ。「X以下の数がK個以上あるような最小のX」を見つければ良いっていうのは言われてみればなるほどなんですけど、その場で思いつくのはなかなか出来ない。早く身につけたい発想ですね。

探索は上の方針で二分探索を行えば良いので、あとは「X以下の数がK個以上ある」判定をどう行うかって話だったんですけど、高橋ジグザグ法も聞いてなるほどーてなりました。答え聞いたら当たり前のことではあるんですけど、ああいうのを思いつける人になりたい。

def check(X):
    count = 0 
    j = N - 1
    for i in range(N):
        while j >= 0 and a[i] * b[j] > X:
            j -= 1
        count += j + 1
    return count >= K

N, K = map(int,raw_input().split(" "))
a = map(int,raw_input().split(" "))
b = map(int,raw_input().split(" "))
a.sort()
b.sort()
left = 0
right = 10**18
while right - left > 1:
    mid = (left + right) / 2
    if check(mid):
        right = mid
    else:
        left = mid
print right

この前やったABC002やその前のABC023でも二分探索の復習したんで、次はオンタイムで解けるようにしたいです。今日のARCも頑張ります！

2015-05-15

ABC002

今日のラボプロコンでABC002をやりました。

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

最近の奴に比べると難易度が本当に教育的だって思いましたね。この前のABC023の制約とかもうね(;_;) 定期的に記事書かないと習慣がつかないと思ったので上げることに。D問題が結構ためになりました。

A-正直者

入力二つの大きい方を出力する問題。一行で書きたいなら皆こうなるであろう(pythonなら)。

print max(map(int,raw_input().split(" ")))

B-罠

入力された文字列の母音を取り除いて出力する問題。ちょっとfilter使いたかったので使ってみた。

ban_word = set(["a","i","u","e","o"])
print "".join(filter(lambda w: w not in ban_word,list(raw_input())))

C-直訴

与えられた3点がなす三角形の面積を出す問題。ヒント見ちゃったので乗っかっちゃいましたw (0,0), (a,b), (c,d) で構成される三角形の面積は|ad−bc|/2だっての高校でやった覚えあるなあ。

xa, ya, xb, yb, xc, yc = map(int,raw_input().split(" "))
print abs((xa-xc)*(yb-yc)-(xb-xc)*(ya-yc)) / 2.

D-派閥

N人の議員についてのM個の人間関係から、全員が知り合いであるような最大のグループの人数を求める問題。文章にすると分かりにくいですが、いわゆる最大クリーク*1問題です。

最大クリーク問題 - Wikipedia

「あっこれグラフ理論でやった奴だ」ってちょっと思いましたね笑とは言ってもそもそも最大クリーク問題の最適な解き方とかよく知らなかったんで地道に解くことにしました。

初めにこのD問題が一番ためになったと言ったのですが、なぜかというとプロコンでしばしば見られる問題の言い換えを意識することが出来たからです。「グラフの最大クリークの節点数Kを求める」と言われても僕は困ってしまうのですが、「グラフにK個の節点からなるクリークが存在するようなKの最大値を求める」と考えると話が分かりやすくなります。

「グラフにK個の節点からなるクリークが存在するか？」という問題はK-クリーク問題と呼ばれます。これを解くのは(計算量の話は今回は置いとくとして)簡単です。グラフのN個の節点の内K個の節点を選んでしえば, それらがクリークを成しているかは任意の二節点が辺で結ばれているかを調べてしまえば確かめられます。これをN個の節点から取れるK個の節点の組み合わせ, $_NC_K$ 通り全て調べればK-クリーク問題は解けるわけです。

よって今回の問題は, KをNから1まで動かして行って各KでK-クリーク問題を解き, TRUEだったKの最大値はいくらだったかを返せば良いことになります。こういう解き方を初めて自力でできたので簡単な問題とはいえ結構嬉しかったです(^^)

from itertools import combinations as comb

def k_clique_solve(relation, max_members, k):
    for members in comb(max_members,k):
        for r in comb(members,2):
            if r in relation:
                continue
            break
        else:
            return True
    else:
        return False

N, M = map(int,raw_input().split(" "))
max_members = range(N)
relation = set()

for i in range(M):
    x,y = map(int,raw_input().split(" "))
    relation.add((x-1,y-1))
 
result = 1
for k in range(N,0,-1):
    if k_clique_solve(relation,max_members, k):
        result = k
        break
print result

今回は1≤N≤12なので全然大丈夫ですが、 ARCや最近のABCだと制約が厳しいため二分探索を求めてきます。せっかくなのでやってみました。

from itertools import combinations as comb

def k_clique_solve(relation, max_members, k):
    for members in comb(max_members,k):
        for r in comb(members,2):
            if r in relation:
                continue
            break
        else:
            return True
    else:
        return False

N, M = map(int,raw_input().split(" "))
max_members = range(N)
relation = set()

for i in range(M):
    x,y = map(int,raw_input().split(" "))
    relation.add((x-1,y-1))
 
left = 1
right = N + 1
while right - left > 1:
    mid = (left + right) / 2
    if k_clique_solve(relation, max_members, mid):
        left = mid
    else:
        right = mid
print left

まあNがちっちゃいので2ms速くなっただけでしたね笑今回のは良い練習になったと思うので、次は本番でこういう解き方をしたいなあと思います。

*1:任意の二節点が辺で結ばれているグラフをクリークという

俵言

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