俵言

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

CODE FESTIVAL2015 決勝 (当日編) (A~E)

code-festival-2015-final.contest.atcoder.jp

なんか今更感ありますが、当日の決勝参加記をば。

本番ではA~Eまでの5問しか解けなくて悔しかったです。復習は復習編で。

A - コード川柳 (2:17でAC)

与えられた文字列の長さが順に5・7・5になってるか確かめるだけ。なのですが焦りすぎて1WAを出す失態を犯しました。

S,T,U = raw_input().split()
print "valid" if len(S) == len(U) == 5 and len(T) == 7 else "invalid" 

B - ダイスゲーム (16:44でAC)

解法聴いてそっかーってなったやつ。ちゃんと考えれば良かったんですが、 1 \leq N \leq 256なのでO(N^2)でも行けるやろってことでDPしました。ただこれもバグる要素ないはずなのに変に単一リストでやろうとして(そして結局やらない)時間かかってしまった。勿体無い。

N = int(raw_input())
dice = [[0]*(6*N+1) for i in xrange(N)]
for i in xrange(6):
    dice[0][i+1] = 1
for i in xrange(N-1):
    for j in xrange(6*(i+1),-1,-1):
        for k in xrange(6):
            dice[i+1][j+k+1] += dice[i][j]
print max(xrange(N,6*N+1), key= lambda x: dice[N-1][x])

C - 寿司タワー (26:01でAC)

シミュレーションしました。タワーの順番を前から見ていって、シャリ・ネタまたはネタ・シャリの順番になっていたらスルー、シャリまたはネタが連続しているときは、既に分解しているパーツがあればそれを使い、なければ寿司を一個分解して使わなかった方のパーツをストックします。

N = int(raw_input())
S = map(int,list(raw_input()))
n = s = cnt = inc = 0
while inc < 2*N-1:
    if S[inc]^S[inc+1]:
        inc += 2
    else:
        if S[inc] == 1:
            if n > 0:
                n -= 1
            else: 
                cnt += 1
                s += 1
        else:
            if s > 0:
                s -= 1
            else:
                cnt += 1
                n += 1
        inc += 1
print cnt

if文多い。解説の解法は頭良いしすっきりしてて良いですよね。

D - 足ゲームII (102:31でAC)

問題見た直後にとりあえずいもす法で累積和取ったんですが、そのあとどうすれば良いか分からない..「絶対 O(N)解あるやろ!」と思ったんですが思いつかず、パーカー欲しさからセグメントツリーで殴ることを決断。

N-1点とるために必要な人数はあるボタンをスルーしたときに必要になる人数の最小値なので、セグツリーで時間の区間ごとの必要人数を管理し、各ボタン(  S_iから T_iの間押し続けると得点がとれる)についてそのボタンをスルーしたときに必要になる人数、すなわち

  • 区間  0 \leq t \lt Sで必要な人数の最大値
  • 区間  S \leq t \lt Tで必要な人数の最大値 - 1
  • 区間  T \leq t \lt 10^5で必要な人数の最大値

の3つのうちの最大値を求めます。その最小値が答えです。計算量は O(NlogN)なのでC++なら余裕で間に合います。

しかしながらバグらせたせいで75分も時間取られました。しかもバグじゃなくて単にinit()呼び出してないだけだったんでめっちゃ悔やまれる..

int n;
int tree[100000*4];
int s[100000];
int t[100000];
void init(int N){
    n = pow(2,int(ceil(log2(100000))))-1;
    rep(i,(n+1)*2) tree[i] = 0;
}
int update(int h){
    if (h < n) tree[h] = max(update(h*2+1),update(h*2+2));
    return tree[h];
}
int query(int a, int b, int h, int l, int r){
    if (r <= a || b <= l) return 0;
    if (a <= l && r <= b) return tree[h];
    return max(query(a,b,h*2+1,l,(l+r)/2), query(a,b,h*2+2,(l+r)/2,r));
}
int main(){
    int N,ans,tmp;
    cin >> N;
    init(100000);
    rep(i,N){
        cin >> s[i];cin >> t[i];
        s[i]--; t[i]--;
        tree[n+s[i]]++;
        tree[n+t[i]]--;
    }
    rep(i,100000) tree[n+i+1] += tree[n+i];
    update(0);
    ans = N;
    rep(i,N){
        tmp = 0;
        tmp = max(tmp,query(s[i],t[i],0,0,n+1)-1);
        tmp = max(tmp,query(0, s[i], 0, 0,n+1));
        tmp = max(tmp,query(t[i], 100000, 0, 0, n+1));
        ans = min(ans,tmp);
    }
    cout << ans << endl;
    return 0;
}

E - ショートコーディング(133:00でAC)

これに関しては順当に考えたというか、--は+になる、!!!は!になる、-のあとに!が来ると-が無効化されるってのを考えて行って、それをそのままシミュレーションした感じです。順番に処理しないとまずいかと思ってわざわざスタックを用意してごちゃごちゃやってます。無効化された場合はポップし、最後まで残ったものを添字順にならべてます。

S = raw_input()[::-1]
m = e = 0
mstk = []
estk = []
for i,s in enumerate(S):
    if s == "-":
        if m == 0: 
            m += 1
            mstk.append(i)
        else: 
            m -= 1
            mstk.pop()
    else:
        if m == 1:
            m -= 1
            mstk.pop()
        if e < 2:
            e += 1
            estk.append(i)
        else:
            e -= 1
            estk.pop()
order = [(j,False) for j in mstk]+[(j,True) for j in estk]
order.sort(key = lambda x: x[0])
print "".join("!" if v else "-" for i,v in order)[::-1]

なんかCでもこんなコード書いたなあと思いつつ提出。AC出てパーカー獲得確定したときすごく嬉しかったです。

解説見てこんな長々と書いて順に処理する必要はないと知ってちょっとショックでしたが、解けたので良しということで。

残り時間

F,G,Hを眺めて、Fが解けそうな気がしたので取り組んでたんですが解けず。結局そのまま時間切れで終了しました。

まとめ

セグメントツリー勉強してて本当に良かったと思いましたね(バグッたけど)、おかげでパーカー取れました。ただ、区間系来てよくわからなかったときにとりあえずせグツリー持ち出しちゃうのは良くない気がする..

6問目解きたかったんですが5問で終わったのは残念でした。ここで6問目を解ける実力を付けたい。

CODE FESTIVAL2015 参加記

この前の土日(11/14・15)に開催されたCODE FESTIVAL2015に参加しました!

recruit-jinji.jp

せっかく参加してきたので全体的な感想とか書いていこうかなと思います。写真とっときゃ良かったと後から後悔(T_T) どう解いたとかは上げるとしたら別口で。

0日目(11/13)

 僕は自宅から3時間半位で行けてしまうので前泊代は出ないんですが、朝早いのはつらいので自主前泊しました。先輩にお会いできたので金はかかるけど悪くない選択肢だった。

1日目(11/14)

 起床フェイズに無事成功し、送迎バスで会場へ。

 受付が完了した後本会場でTシャツとかシリコンバンドとか色々頂きます。このシリコンバンド、僕は何気なく赤色をもらったのですが、よくよく確認すると色が黒、赤、黄、青、白の五色で(もしかしたら他にもあったのかも)レーティング説が浮上。赤をとったのをめっちゃ後悔しました。緑の雑魚に人権は認められないのか

あと壁にTweetを映す為に天井付近にMac Bookが置いてあったのが印象に残ってます。

開会式・ルール説明

 indeed社の方からのメッセージを聴いたりして開会。今回のルールでは何とパーカーの獲得条件が5問ということが判明し、やる気が高まります。

本戦(12:00~15:00 12:45~15:45)

 12:00から遂に本戦開始!!と思ったら通信トラブルが発生して超延長する事態に。12:45に開始した後も通信が不安定で結構怖かったです。

結果としてはA,B,C,D,Eを順番に5問解いて無事パーカーゲットしました!!ただDをバグらせたせいで時間かかったのがたたって129位だったのが悔しい。あともう一問解ければ大満足だったのですが六問目の壁が厚かったです。あと一問解きたかったなあ。 f:id:Tawara:20151117235136p:plain

自由行動(16:30くらい~21:00)

 一日目は本戦が終わったあとは各自自由にブースを動いて良いということで、僕はトークライブに行ってました。用意されているコンテンツは

などなど。同時進行なので全部回るのは不可能だし、食事をゆっくり味わう時間が無かったのが少し残念。

本戦解説 (16:30くらい~17:00くらい)

 通信トラブルがあったため、その分解説は巻きに巻くこととなりました。chokudaiさんの焦りようが半端無く、時間ないから端折り方がひどいww chokudaiさんも仰ってたけど本番時に解けなかったのにあの解説で理解できたら天才だと思う。今現在は解説読んで復習中。

今回の問題では区間DPが学べたことが大きな収穫だなーと思ってます。それと、Hの焼肉の問題はセグメント系の問題かと思ってたのに気付いたらグラフの問題になっててダイクストラ法で解説されててめっちゃびっくりしました。

チームUnagiによるトークライブ(17:15~18:00)

 秋葉さんがICFPPC優勝する為に作ったというチームUnagiの裏事情とか。Red Coder 6人集めるよりもきっと強いと仰っていて(そして本当に強い)、全員が問題を解くのではなくインフラ係とかしっかり役割分担していてチームとして良い働きができてるそうです。チームの人数も計算資源も無制限ってところが面白いですね。是非挑戦して欲しいって仰ってました。マラソン系のコンテストは出たことがないのでちょっとやってみたい。

秋葉さんからのメッセージ「かかって来いやあ!」

続・ペアプログラミング(18:15~19:00)

 "呪いをかけられたせいでコーディングができない秋葉に迫り来る刺客(チョク・ダーイ)からの襲撃(出題)。秋葉はhyonにコーディングしてもらうことで襲撃を退ける(ACする)ことが出来るのか?!"

みたいな設定で始まる秋葉さんとhyonさんによるペアプログラミングこちらの問題を解かれてました。デバッグで嵌る恐ろしさが伝わってくるリアルなコーディングでしたね。

本当に時間内に終わるのか!?ってところで提出して(BGMは例のアレ)見事ACが出たときはちょっと感動しました。

まあ普通に面白かったんですが、これを聴きに行った一番の収穫は名前だけ"は"知ってたオイラーツアーが何なのかを知れたということです。言われた通りちゃんと覚えて帰ってきたので、これから使っていきたいところ。

エキシビジョンマッチ(19:40~20:40)

 本戦の上位5名+スペシャルゲストによるエキシビジョンマッチを観戦(オープン参加も出来る)。参加者の方々もサービス精神旺盛で、画面越しに解説してくれたりメッセージを送ってくるのには笑ってしまいました。

それにしてもゲストのりんごさん全完とか強すぎでしょ..

1日目を終えて

 1日目も終了し、宿に帰って2日目に備えるのかと思いきや、CODE FESTIVAL2015には恐ろしい企画が用意されていました..

短縮王に嵌る

 CODE FESTIVAL2015では、与えられた問題をいかに短いコードで解けるか競うコンテスト(短縮王)が2日目の正午まで開催されており、1日目の夜はずっとこれをやってました。正直Perlに勝てる気がしないのでpython最短を目指して頑張り、B問題でpython一位に並ぶ190byteまで行ったのですが結局言語最短とれず.. eval とか execって知らねえぞ..

ただ副産物としてUnion Findの手軽な書き方が出来るようになったので、これは今後活かせる気がします。寝るのめっちゃ遅くなったけど。

2日目(11/15)

 起床フェイズ..失敗

確かに7:00に目覚めたのに気づいたら9:00過ぎてた。なんで僕は4:00頃まで短縮王やってたんだろう..後悔の念が次から次へとこみ上げる..

あさプロ(9:10~10:40)

 頭が回らない朝からプロコンするというなかなかつらい企画なのですが、時間を見たら分かる通り僕の起床が開始時刻くらいだったので非常にマズい。

焦って準備してタクシーに飛び乗り30~40分遅れ位でEasyに参加。A,B,Cまで速攻で解いたんですが、Dが解けない..あとから人に聞いたら、これあれやん、ペアワイズアラインメントやん、DPやん、知ってるやん.. 頭が回ってなかったなあと言い訳してみる。

ワンランク上に行くプロコン講座(11:15~12:00)

 高橋直大氏によるトークライブ。問題のパターンの話とか、こういう問題のとき何のアルゴリズムを使うかとか勉強になりました。出来ればもう一度見直したいのではやく上がらないかな..

りんごの挑戦状(12:15~13:00)

 rng_58氏によるトークライブで、本戦優勝者などがりんごさんの出題する問題に挑戦する企画。プロコンはあんまり関係なかったみたいですが結構面白かったです。RGB答えるとかむずすぎ

ショートコーディング「短縮王」徹底解説(12:15~13:00)

 スタンプ欲しさに途中からこっちもちょっと聴いてました。僕の起床フェイズ失敗の原因となった短縮王の解説です。Perl強すぎんよって感じですが、Cで短く書く為にレジスタの中身を把握したりとか、短く書く為には言語仕様を把握するのが大事だって事がよくわかります。

太鼓の達人DDR

 スタンプ欲しさに(以下略)。人生で初めてDDRやったんですが、そのあとにランカーによるデモプレイだった為、それを見る為に集まってる人が結構居て「僕やって良いのかな..?」って思わずにはいられなかった。時間無くて太鼓の達人だけランカーの方のプレイ見たんですけど、手の動きおかしいやろ!

ボードゲーム

 スタン(略)。やったことないの沢山あったんでやってみたかったんですが、時間が全然なくて断念。紐をテーブルに置いてその上にメンコみたいなの投げ込む奴がめっちゃくちゃ気になった。

チーム対抗早解きリレー(14:15~15:45)

 2日目のメインイベントです。僕は本戦で129位だったのでチーム09 "すぬけ"のメンバーとして参加しました。プロコンにチームで挑むのも初めてでしかも10人で組むなんてもう初めて過ぎてどうすりゃいいのかわからん笑 とりあえずうちのチームは順位順に問題を振ったので、自分の問題をすばやくちゃんと通すことを最優先して、あとは人の問題一緒に考えたりしてました。

大人数であーだこうだ言って挑むのもなかなか楽しいですね。順位は9位でしたけど一問誰かが通す度にすごく嬉しいかったですし、全員通して全完できたときの感動はなかなかのものでした。めっちゃ楽しかったです!

ハッピーアワー(16:00~17:00)

 最後の交流会的なもの。僕人見知りなので正直あんまり交流できてないんですが、この界隈の人と少しでも交流できたのは良かったかなあと。またどこかのオンサイトで会えると良いですね。あと知り合いをやっと特定できたり。

閉会式(17:00~18:00)

 最後にドローンで記念写真をとって終了。いやあ二日間あっという間だった。

おわりに

上に書いた通り、2日間ぶっ通しで内容盛り沢山の充実した時間で、とても楽しかったです。

思えば去年の10月かそれくらいから先輩に誘われてちゃんとプロコンに参加するようになり、CODE FESTIVALに出るのは一つの目標だったのですが、本当に出れて良かったと思います。残念なのは僕がM2なのでもう二度と出ることは叶わないということです。B4ぐらいから始めとけば或いは..

出られるのが大学(院)生相当のみということもあって本戦に出られる可能性は結構高いので、プログラミング少しでも興味ある学生には是非目指して欲しいコンテストだと思いました。何より自分の金銭的負担がなくこれだけコンテンツが盛り沢山なのが良いところ。まあ一年で無理でも二年くらいあれば行けそうな気がする。

CODE FESTIVAL 終わっちゃったけど僕のプロコン人生が終わった訳ではありません。とりあえず早く青くなって人権を得るところから始めたい..

おまけ: 戦利品

f:id:Tawara:20151118005446j:plain

またTシャツとパーカーが増えてしまった..。トートバッグが実は参加賞の中では一番嬉しかったり。タンブラー欲しかったのでスタンプラリーは最後らへんかなり強引に回ってしまいました。

KUPC2015復習記(A~G)

KUPC2015にオンサイトで参加しました!KUPCに参加すること自体初で、コンテストにオンサイトで参加するのはindeedなう以外で初めてです。

kupc2015.contest.atcoder.jp

結果は以下の通りで不甲斐ない結果でした。もうちょい通したかったなあ..特に最後の一時間でFが通せなかったのが一番悔しかったです。 f:id:Tawara:20151106143825p:plain 参加記書こうと思いつつ気付けば二週間経ってたので、少し詳しく復習記事を書くことにしました。以降の記事は色々考えたこととかソースコードが載ってるので大分長くなってます。

A - 東京都

問題文

A: 東京都 - 京都大学プログラミングコンテスト2015 | AtCoder

解法

一瞬迷ったんですが、前から順番に見て'kyoto'か'tokyo'があれば切り出すのを繰り返せば問題ないだろうということで提出しました。

実装

indexとか使えばもっと簡単に書けるかもしれない。

T = int(raw_input())
for i in xrange(T):
    S = raw_input()
    sl = len(S)
    inc = cnt = 0
    while inc < sl-4:
        if S[inc:inc+5] == 'tokyo' or S[inc:inc+5] == 'kyoto':
            cnt += 1
            inc += 5
        else:
            inc += 1
    print cnt

B - GUARDIANS

問題文

B: GUARDIANS - 京都大学プログラミングコンテスト2015 | AtCoder

解法

方眼紙にひたすら書く。

ってのが参加時の僕の行動です。最終的に鎖頭を5匹配置して下一行を侵入者が通るようにしました。解説で出された4匹解答は衝撃的でしたね。

ちなみに、4匹の鎖頭の配置の仕方は _{100}C_4 = 3921225 \fallingdotseq 4.0 * 10^6なので、それら全てに対して探索を行っても間に合うそうです。

実装

これ実装やない、ただの出力や。

print ".........."
print ".........."
print "..C......."
print ".........."
print ".........."
print ".........."
print "..CC..CC.."
print ".........."
print ".........."
print ".........."

C - 最短経路

問題文

C: 最短経路 - 京都大学プログラミングコンテスト2015 | AtCoder

解法

エッジの数が指定されてないので、とりあえず与えられた最短距離を持つエッジを全部張ったグラフを考えます。このときに問題が発生するのは、頂点  iから別の頂点を経由して頂点 jに行く経路の長さが、頂点  iから頂点  jに直接行くよりも短い場合です。このような場合は条件を満たす有向グラフが存在しないことになります。

f:id:Tawara:20151106172034p:plain

要は与えられた最短距離から全頂点対の最短距離を計算し直して、与えられた最短距離より短くなっているところがあったらアウトです。頂点数  Nの制約は( 1 \leq  N \leq 30) と小さいので、 O(N^3)のワーシャルフロイドの出番ですね!

あと、与えられる最短距離の行列の対角成分は当然0になると思いがちですが、今回はそうでないものも含まれてるので弾く必要があります。単純有向グラフの定義では自己辺は存在しないので、そのために入れたんですかね?

実装

参加時は念のためにC++で通したんですが、計算量が  O(TN^3)なので冷静に考えるとpythonでも普通に通りますね。

問題設定では a_{ij} = -1の場合に頂点  iから頂点  jへの経路が存在しないのですが、ワーシャルフロイドで計算して行く都合上MAX( =  10^7)に書き換えました。いずれかの(i.j)に対して d_{ij} a_{ij}より小さければ有向グラフが存在しないので"NO"を出力します。

最近any()とall()の存在を知ったので使ってみました。

T = int(raw_input())
MAX = 10000000
for i in xrange(T):
    N = int(raw_input())
    a = [map(int,raw_input().split()) for i in xrange(N)]
    d = [[MAX]*N for i in xrange(N)]
    for i in xrange(N):
        for j in xrange(N):
            if a[i][j] == -1:
                a[i][j] = MAX
            d[i][j] = 0 if i == j else a[i][j]
    for k in xrange(N):
        for i in xrange(N):
            for j in xrange(N):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    print "NO" if any(d[i][j] < a[i][j] for i in xrange(N) for j in xrange(N)) else "YES"

D - 高橋くんの旅行

問題文

D: 高橋君の旅行 - 京都大学プログラミングコンテスト2015 | AtCoder

参加時に取り組んだけど解けませんでした(その1)。解法が思いつかず、部分点だけとって放置してました。

部分点解法

問題文見たとき単純なDPで行けるかな?って思ったんですが、 Nの制約が1 \leq N \leq 10^5 なため相当厳しい..。i日目に到達できる都市の番号が最大でもi+1であることを勘案しても、計算量が N^2/2位になるのでC++でも無理でした。部分点の制約は 1 \leq N \leq 10^3なのでこの方法で部分点が取れます。

実装

int main(){
    int N;
    LL ans = 0;
    VLL dp,A,B;
    cin >> N;
    A.resize(N); B.resize(N);
    rep(i,N) cin >> A[i];
    rep(i,N) cin >> B[i];
    dp = VLL(N+1,-1);
    dp[0] = 0;
    rep(i,N){
        for(int j = i+1; j >= 0; j--){
            if (dp[j] >= 0){
                dp[j+1] = max(dp[j+1],dp[j]+A[j]);
                dp[j] = max(dp[j],dp[j]+B[j]);
            }
        }
    }
    rep(i,N+1) ans = max(ans,dp[i]);
    cout << ans << endl;
    return 0;
}

満点解法

解説によると、ポイントは「いずれのiについても  B_i \geq 0が成り立つ」ということだそうです。更にポイントとして、都市  iでの滞在で得られる  B_iは何日目であろうと変化しないこと、都市  iから都市  i+1への移動は一回しか起こらない、ということが挙げられそう。

解法としては、最後に居る都市  iさえ決めてしまえば  B_jが最大となる都市  j  (1\leq j \leq i)に出来るだけ滞在することでお金を最大に出来ます。言われてみればなるほどって感じですね。先に都市を決めるって発想に至れなかった..。これを各  iについて求めてしまえば、その最大値が答えになります。

ただし、条件として「いずれの日にも所持金が負になってはいけない」というのがあるので、都市 iを決めたら所持金が負にならずに iに到達できる最小の日数を求め、残りの日数は B_jが最大となる都市 j (1\leq j \leq i)にずっと滞在するという流れになります。

都市  iに最小日数で到達するということは、都市 i-1に最小日数で到達してから出来るだけ少ない日数で都市  i-1から都市  iへの移動を行うということ。(都市  i-1に最小日数で到達したときの所持金 + A_i) が負でなければ即座に移動が行えますが、そうでない場合は B_jが最大となる都市  j  (1 \leq j \leq i-1)に滞在しつづけることで、最小の日数で移動可能な状態にすることができます。

実装

dayは都市 iへ到達する最小日数, moneyはその時点での所持金です。for文の前半で最後に居る都市が  iであるときの所持金の最大値 {ans}_iを求め、後半でdayとmoneyを更新してます。

N = int(raw_input())
A = map(int,raw_input().split())
B = map(int,raw_input().split())
ans = [0]*(N+1)
day = money = 0
maxB = B[0]
for i in xrange(N):
    if day > N:
        break
    maxB = max(maxB,B[i])
    ans[i] = money + maxB*(N-day)
    day += 1
    money += A[i]
    while money < 0 and day <= N:
        day += 1
        money += maxB
else:
    ans[N] = money
print max(ans)

E - マッサージチェア2015

問題文

E: マッサージチェア2015 - 京都大学プログラミングコンテスト2015 | AtCoder

参加時に取り組んだけど解けませんでした(その2)。普通の長方形と正方形の二パターンしか想定してなかったんですが(↓みたいなやつ)、ほぼ正方形といってもいい長方形だと結果が変わるみたいです。もっと色々考察したり試したりすべきですね。

f:id:Tawara:20151107013115p:plain

解法

厳密な証明が出来る訳じゃないんですが、概ね以下のように考えると納得できそう? ※横の方が長い(or縦と等しい)長方形を想定

  1. 三角形ABCが長方形(談話室)の内部にあるなら、内接させた方が大きい三角形ができる。 f:id:Tawara:20151107024610p:plain 長方形の内部に三角形ABCがある(または、頂点のうち少なくとも一つが内部にある)場合、図のようにすれば辺の最小値を大きく出来ます。

  2. 三角形ABCのいずれの頂点も長方形の角頂点(角)に無い場合、少なくとも一点を角に移動させると大きい三角形ができる。 f:id:Tawara:20151107064225p:plain あんまり厳密ではないですが、いずれの頂点も長方形の角に無い場合は図の3パターンなので言えそう。一番短い辺の端点のうちどちらかを動かせば辺の最小値を大きく出来ます。

  3. 長方形の一つの辺に三角形の二つの頂点がありかつ、少なくとも一方がその辺を内分している場合、二頂点のどちらかを動かせばより大きな三角形ができる。 f:id:Tawara:20151107121635p:plain これも怪しいけど言えそう。

    • [左] 二頂点に内分されている辺の対辺上にもう一点がある場合。これは図の通りに動かせば三角形の辺の最小値を大きく出来ます。
    • [中央、右] 二頂点に内分されている辺の隣接した辺にもう一点がある場合。この場合は、同じ辺にある二頂点(A,B)のうち三つ目の頂点から遠い方を動かすと三角形の辺の最小値を大きく出来ます。ただし、右のような場合は最初からACが最小なので、最小値を変えずに点を移動させることになります。
  4. 三角形ABCが長方形に内接しているとき、一つの辺を固定すると残りの二辺を等しくすれば辺の最小値が最大になる。 f:id:Tawara:20151107034612p:plain 固定する辺の長さが小さい場合は二等辺三角形でなくても良い場合がありますが、図のように、固定する二頂点を長方形の短い方の対辺の組に置けば二等辺三角形が最適です。

以上のことを考えると、頂点の一つは角に固定出来ます。最後に述べたことから、頂点をもう一つ固定すれば自動的に最後の点の最適な位置が分かるので、二つ目の頂点で探索を行えば解けます。 一番下の図で言うとCの位置を探索しますが、Cの最適な位置が辺の端点でない場合は、三角形ABCの辺の最小値は以下のグラフのように上に凸になるはずです(※形がこんな曲線になるかはわかりません)。 f:id:Tawara:20151107041525p:plain 上に凸ということで、たまにしか使わない三分探索を使う機会がやって参りました。

実装

Bを(0,0)に、Cを(w, mid)に固定したとき、Aの最適な位置は

(\frac{mid^2 - 2mid*h + w^2}{2w},h)

です。BCの中点の垂直二等分線と長方形の上の辺の交点なので式を立てれば求まります。このx座標、めっちゃ因数分解出来そうな形してるのに惜しい..

from math import sqrt
lb = 10**(-7)
def side_min(w,h,mid):
    return min(w**2 + mid**2, ((mid**2 - 2*mid*h + w**2)/(2.*w))**2 + h**2)

T = int(raw_input())
for i in xrange(T):
    H,W = map(int,raw_input().split())
    w = max(H,W)
    h = min(H,W)
    l = 0; r = h
    while r-l > lb:
        lmid = (2*l + r) / 3.
        rmid = (l + 2*r) / 3.
        lmin = side_min(w,h,lmid)
        rmin = side_min(w,h,rmid)
        if lmin >= rmin:
            r = rmid
        else:
            l = lmid
    print sqrt(lmin)

図形の辺ってsideで合ってるんですかね?

想定解法

解説によると、三角形ABCの辺の最小値が最大になるときに長方形の角にある頂点が一つだけの場合、三角形ABCは正方形になるらしい..正直なんでか分かりません。この事実を利用すると二分探索で解を求めることができ、更に言うと O(1)で答えを出すことも可能だそうです。

F - 逆ポーランド記法

問題文

F: 逆ポーランド記法 - 京都大学プログラミングコンテスト2015 | AtCoder

参加時に取り組んだけど解けませんでした(その3)。この問題は最後らへんずっと考えてて、方針は合ってたっぽいのに実装がおかしくて通らないという非常に悔しい結果でした。

解法

解説聞いて感動したのが、構文木で考えるとめっちゃわかりやすいということ。問題自体が構文解析っぽいし、解いてるときに「演算子の階層の深さ」とか考えてたんだからむしろ木構造は思いついてしかるべきですよね。思い至らなかったのがとても悔しい。

たとえば数式"(4+3)-(2+1)"木構造で表すと、以下のようになります。 f:id:Tawara:20151107140337p:plain この数式を評価する場合、演算子を評価する際にはその左辺(左の子)と右辺(右の子)が全て評価し終わっている必要があり、その順序によって記法が変わります。

逆ポーランド記法の順番 "43+21+-" を見ると、木を左からdfsして葉(または子が既に並べられている節点)から並べています。スタックで処理すると、演算子の左辺の評価値をスタックの奥に追いやったまま右辺の評価を行えるからうまく行くみたいです。

一方キューで処理しようと思うと、演算子で評価した結果がキューの一番後ろに入ってしまうので同じ順番では無理です。ぱっと思いつかないんですが、実は計算の過程を終わりから見て行けばどういう順番になっているがすぐにかわかります。

f:id:Tawara:20151108004433p:plain

同様のことをスタックでもやるとちゃんと逆ポーランド記法の数式文字列が出ますが割愛。

導かれたキューで処理する場合の順番は、木構造を右からbfsして葉(または子が既に並べられている節点)から並べていることが分かります。よって解法としては、逆ポーランド記法から構文木を形成して、深いノードのうち右から順に並べて行けばよいです。

実装

一旦木を作ってしまい、そのあと深いかつ右にあるもの順で並べて行きます。木構造はクラスとかで作るのも可能ですが、セグメントツリーみたいに配列を用意してkの左の子の添字が2k+1、右の子の添字が2k+2になる定番のやり方が楽(このインデックスの仕方って名前ありましたっけ?)。こうすると並べるときに添字の大きい方から並べるだけで済むのでめっちゃ楽です。 ただし数式の構文木は平衡木になっているとは限らないので(配列を本当に用意すると余裕でTLEしました)、代わりにディクショナリを使って必要な部分だけ用意するようにしています。

dfsで書いてますが、bfsの方が簡単に書けるらしいです。逆ポーランド記法は一番後ろから読んで行くと木構造が分かりやすいので処理も後ろから行っています。

A = list(raw_input()[::-1])
N = len(A)
tree = dict()
def make_tree(h,pos):
    if pos >= N:
        return
    tree[h] = A[pos]
    if not A[pos].isdigit():
        pos = make_tree(h*2+2,pos+1)
        pos = make_tree(h*2+1,pos+1)
    return pos
make_tree(0,0)
print "".join(tree[k] for k in sorted(tree.keys(), reverse = True))

けっこう綺麗に書けたので個人的には嬉しい。

G - ケンドー

問題文

G: ケンドー - 京都大学プログラミングコンテスト2015 | AtCoder

参加時には読んだけどよくわからなくてH解こうとしたりしてました(そして無理でした)。プロから言わせると典型問題らしい..。

解説では、「B_Nから順に対戦相手を決めて行けばよい」って言われてそれには納得したんですが、それを高速で実現する為にはどうするかってのがよくわかってませんでした。この問題は自力で解くのが難しかったので、他の方の参加記等にパクリにヒントをもらいに行くと、

  • B_Nから決めて行けば、後はBIT使えばOK
  • FenWick Treeでやろうとした
  • BIT使った

みたいな声が多数。前々から名前だけ知ってたBIT(Binary Indexed Tree)ですが、ついに習得するときが来たらしい。 以下のスライドで勉強させて頂きました、ありがとうございます!

http://hos.ac/slides/20140319_bit.pdf

"「普通に Binary Indexed Tree を使うだけ」の部分で詰まらないようになる"、まさに今の状況ですね。

さてBITは一応実装したものの、対戦相手の決定にどう使えば良いのか全然分からん..と思っていたら、Twitter

  • 優先度付きキューでやった

というTweetを見かけてやっと解法に思い至りました。

解法

最善の解法がどうなのかは不明ですが、この解法では対戦相手の決定に優先度付きキューを、並べ替えの回数を求めるのにBITを使用しています。 ※説明を簡単にするため高橋くんチーム、青木くんチームの  i番目のメンバーを、それぞれ  a_i, b_iと標記します。

まず対戦相手の決定の仕方について。 B_i \leq B_{i+1}  (1 \leq i \lt N)が成り立っているため、 b_Nの相手は、 A_i \geq  B_Nなる i ( 1 \leq i \leq N)のうち、 iが最大となる a_iにすれば交換回数が最小になります。 b_{N-1}, b_{N-2}, ... , b_{1}についても同様に決定していけば良いです。

問題はどうやって効率的に決定を行うか。b_iごとにAを後ろから見て行って、 A_j \geq  B_iかつ a_jがまだ誰の相手にも成っていなければ a_j b_iの対戦相手に決定するのが愚直な方法ですが、これだと計算量が O(N^2)になります。 制約が 1\leq N \leq 10^5なのでこれだと絶対TLEです。(部分点は取れます)

そこでまず (i,A_i)を要素とするリスト  A'を用意し、これを第二要素(ワザマエ)の大きい順にソートします。すると b_Nの対戦相手の候補は、ある kが存在して、 1 \leq i \leq kを満たす A'_iに対応する a_jとなります(添字適当ですみません)。 A'はワザマエ順に並んでいるので、 B_Nを越えるワザマエを持つものは絶対に先頭から並んでいるはずです。入力例2で考えてみると、以下のようになります。

f:id:Tawara:20151118014354p:plain ポイントは  b_{i+1}の対戦候補に挙がったものは b_iの対戦候補にもなるということです。A'を先にソートしておくことで、対戦候補の列挙自体は O(N)で済むことに成ります。

あとは対戦候補のうち一番右側に居る人を対戦相手に選べば良いんですが、これを効率的に行うために優先度付きキューを使います。対戦候補に挙がったものを全て優先度付きキューに突っ込んで番号が大きい順に並ぶようにすれば、更新がO(logN)で出来ることから全体でO(NlogN)で対戦相手の決定を行えます(計算量については大分適当に言ってます)。

次に交換回数の求め方について。もっかい入力例2で考えてみます。

f:id:Tawara:20151108012317p:plain

Nが小さいので例として微妙ですが、要は今から移動させる a_iの右側に移動していないものが何個あるかで a_iを移動させる為の交換回数が決定します。つまり、a_iを移動させる際の交換回数は  a_j ( i+1 \leq j \leq N)のうち移動済でないものの個数です。この移動済かどうかの値を区間で効率的に管理するためにBITを使います。

実装

pythonのheapqは要素が小さいもの順に並ぶので、実際にはA'の要素は (-i, A_i)としています。また、BITの区間和で求まるのは通常[1,a]の区間和ですが、今回欲しいのは[a,N]の区間和なので対応を逆にする(a_iをN-iに対応させる)ことで処理しています。

from heapq import heappush,heappop
N = int(raw_input())
bit = [i&(-i) for i in xrange(N+1)]
def bit_add(a,w):
    while a <= N:
        bit[a] += w
        a += a&(-a)
def bit_sum(a):
    ret = 0
    while a > 0:
        ret += bit[a]
        a -= a&(-a)
    return ret
A = [(-i,v) for i,v in enumerate(map(int,raw_input().split()))]
A.sort(key = lambda x: x[1],reverse = True)
B = map(int,raw_input().split())
pos = cnt = 0
Q = []
for i in xrange(N):
    while pos < N and B[N-1-i] <= A[pos][1]:
        heappush(Q,A[pos])
        pos += 1
    if not Q:
        print -1
        break
    idx = N + heappop(Q)[0]
    cnt += bit_sum(idx)-1
    bit_add(idx,-1)
else:
    print cnt

終わりに

復習記事久々に書いたら何かすごい長さになってしまった。解けるのとちゃんと説明できるのは別だなあと思います。A~Gはなんとか解けましたが、H以降は厳しそう。Hは桁DPらしいのでまだ行ける気がするんですが、I以降の問題は解説から全然意味が分からなかった..。マヤノルム?知らない子ですね..

別件ですがCodeFestival通りました!もうあと一週間ですね。参加できる最初で最後の機会なので思いっきり楽しもうと思います!

SRM671 Div2(Easy,Med)

いったいいつぶりの投稿だろうか..

Medで少し学ぶことがあったのでいい機会だと思って復活しました。hard時間内で解こうと意気込んでたら全然出来んかった..クマさんにいじめられる回です。

Easy (250) : BearPaints

問題文の要約

 Wマス, 高さ Hマスの直方体のマス目が与えられる。直方体を成すようにマスをぬるとき、 Mマス分のインクで最大何マスをぬることができるか?

制限

時間 : 2秒, メモリ : 256MB

制約

 1 \leq  W,H \leq 10^6, 1 \leq M \leq 10^{12}

解法

全探索をしてしまうと最悪計算量が 10^6 * 10 ^6 = 10^{12}かかってしまうので幅の方だけ探索を行います。塗る直方体の片方の辺の長さをi (1 \leq i \leq W)に固定すると、ぬることができる直方体のマス目は

  •  i * H \leq Mのとき  i*H
  • そうでないとき  i*(M / i) ("/"は小数を切り捨てる除算)

となるので、iを動かしていけば最大値が見つかります。

実装

実際の実装では幅と高さのうち小さい方を動かすようにしてます。

class BearPaints:
    def maxArea(self, W, H, M):
        l = min(W,H)
        h = max(W,H)
        return max([i*h if i*h <= M else i*(M/i) for i in xrange(1,l+1)])

Med (500) : BearDartsDiv2

問題文の超要約

長さNの自然数w が与えられる。 w_i * w_j * w_k = w_l (0 \leq  i \lt j \lt k \lt l \lt N)なる (i,j,k,l)の取り方は何通りあるか?

制限

時間 : 1秒, メモリ : 256MB

制約

 4 \leq N \leq 500, 1 \leq w_i \leq 10^6

解法

もちろん、全組み合わせを確かめようとすると _NC_4通り、最悪で _{500}C_4 = 2573031125 \fallingdotseq 2.6*10^9通りあるので1秒では全探索はキツそう。ってわけでDPを使うことにしました。

DPのためのmapとしてdp1, dp2,dp3の三つを用意し、 wを左から順にチェックして更新します。 w_l (0 \leq l \lt N)をチェックする際に三つのマップは

  • dp1 : w_iのとる値(key)の組み合わせ数(value) ( 0 \leq  i \lt l)
  • dp2 : w_i * w_j のとる値(key)の組み合わせ数(value)(0 \leq i \lt j \lt l)
  • dp3 : w_i * w_j * w_k のとる値(key)の組み合わせ数(value)(0 \leq i \lt j \lt k \lt l)

という状態になっており、dp3[ w_l ]の値を答えに加えたあと、dp3, dp2, dp1の順番で更新します。これなら掛け算の組み合わせがまとまるので多分行けるはず。

実装

今回は制約が厳しそうだったのでC++で実装することにしました。超シンプルに書けたので満足。

class BearDartsDiv2 {
    public:
    LL count(vector<int> w) {
        LL ans = 0, N = w.size(), wi = 0;
        map <LL, LL> dp1, dp2, dp3;
        map <LL, LL> :: iterator it;
        for(int i = 0; i < N; i++){
            wi = (LL) w[i];
            ans += dp3[wi];
            for(it = dp2.begin(); it != dp2.end(); it++) dp3[(it->first)*wi] += it->second;
            for(it = dp1.begin(); it != dp1.end(); it++) dp2[(it->first)*wi] += it->second;
            dp1[wi] += 1;
        } 
        return ans;
    }
};

だがしかし..

「hardは解けなかったけど、med綺麗に解けたから満足!」っとか言ってたら、落ちましたorz。TLEでした。行けると思ってたんですがどうやら1秒は思ったより厳しかったらしい.. しかしこの方針自体は気に入ってるのでどうにか通したい..

解法(その2)

さきほどの解法では,  w_i * w_j * w_k = w_l (0 \leq  i \lt j \lt k \lt l \lt N)について、先に w_i * w_j * w_kの組み合わせを作っておき、それと w_lが一致するかどうか確かめていく方法でした。しかしこの方法では掛け算の組み合わせが爆発するらしい..

そこで少し考え方を変えてみます。 w_i * w_j * w_k = w_l (0 \leq  i \lt j \lt k \lt l \lt N)というのは即ち、

 w_i = w_l \div  w_k \div w_j (0 \leq  i \lt j \lt k \lt l \lt N , w_l  \% w_k = 0,  (w_l \div w_k) \% w_l = 0)

と言い換えることが出来ます。この考え方で、 w_l \div  w_k \div w_jを先に作っておき、w_iと一致するか確かめるよう dp1,dp2,dp3を変更し、w右からチェックしていきます。 w_i (0 \leq i \lt N)をチェックするときの各mapの状態は、

  • dp1 : w_lのとる値(key)の組み合わせ数(value) ( i \lt  l \lt N)
  • dp2 : w_l \div w_k のとる値(key)の組み合わせ数(value)(i \lt k \lt l \lt N)。ただし、  w_l \% w_k = 0
  • dp3 : w_l \div w_k \div w_j のとる値(key)の組み合わせ数(value)(i \lt j \lt k \lt l \lt N)。ただし、  w_l \% w_k = 0かつ  (w_l \div w_k) \% w_j  = 0

となっており、dp3[ w_i ]の値を答えに加えたあと、dp3, dp2, dp1の順番で更新します。最初の解法だと掛け算の取りうる値は全てmapに記録されましたが、この解法だと割り切れないものは弾かれるので計算量が大幅に減少します。

実装

実装自体はほとんど一緒です。右からチェックするのと、割り切れるかのチェックが加わっているだけなので。

class BearDartsDiv2 {
    public:
    LL count(vector<int> w) {
        LL ans = 0, N = w.size(), wi = 0;
        map <LL, LL> dp1, dp2, dp3;
        map <LL, LL> :: iterator it;
        for(int i = N-1; i >= 0; i--){
            wi = (LL) w[i];
            ans += dp3[wi];
            for(it = dp2.begin(); it != dp2.end(); it++) if ((it->first) % wi == 0) dp3[(it->first)/wi] += it->second;
            for(it = dp1.begin(); it != dp1.end(); it++) if ((it->first) % wi == 0) dp2[(it->first)/wi] += it->second;
            dp1[wi] += 1;
        } 
        return ans;
    }
};

結果

ちゃんと通りました!やったね!最初の解法だとTLEだったcaseもこの解法なら数十msぐらいで行けるという。割り算って偉大だ。

ちなみに、もしかしたらこの方針ならpythonでも行けるかも?と思ってやってみると..

class BearDartsDiv2:
    def count(self, w):
        ans = 0
        dp1 = collections.defaultdict(int)
        dp2 = collections.defaultdict(int)
        dp3 = collections.defaultdict(int)
        for wi in reversed(w):
            ans += dp3[wi]
            for k,v in dp2.iteritems():
                if k % wi == 0:
                    dp3[k/wi] += v
            for k,v in dp1.iteritems():
                if k % wi == 0:
                    dp2[k/wi] += v
            dp1[wi] += 1
        return ans

通りました!こちらも最悪ケースが数十msぐらい。割り算すげえ..

まとめ

本番ではTLEしちゃいましたが、掛け算の取りうる値の通り数をチェックするときに割り算で攻めるのはとてもいい知見だと思いました。何らかの機会に生かしたい。 あと、左から w_i*w_j、右から w_l \div w_k (w_l \% w_k = 0)の値を作っておいて..といった手法も出来そうな気がしますが、mapが2N個必要になるので、今回の手法の方が好きかな。 hardについては..そのうち..多分..