CODE FESTIVAL2015 参加記
この前の土日(11/14・15)に開催されたCODE FESTIVAL2015に参加しました!
せっかく参加してきたので全体的な感想とか書いていこうかなと思います。写真とっときゃ良かったと後から後悔(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位だったのが悔しい。あともう一問解ければ大満足だったのですが六問目の壁が厚かったです。あと一問解きたかったなあ。
自由行動(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 終わっちゃったけど僕のプロコン人生が終わった訳ではありません。とりあえず早く青くなって人権を得るところから始めたい..
おまけ: 戦利品
またTシャツとパーカーが増えてしまった..。トートバッグが実は参加賞の中では一番嬉しかったり。タンブラー欲しかったのでスタンプラリーは最後らへんかなり強引に回ってしまいました。
KUPC2015復習記(A~G)
KUPC2015にオンサイトで参加しました!KUPCに参加すること自体初で、コンテストにオンサイトで参加するのはindeedなう以外で初めてです。
結果は以下の通りで不甲斐ない結果でした。もうちょい通したかったなあ..特に最後の一時間でFが通せなかったのが一番悔しかったです。 参加記書こうと思いつつ気付けば二週間経ってたので、少し詳しく復習記事を書くことにしました。以降の記事は色々考えたこととかソースコードが載ってるので大分長くなってます。
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匹の鎖頭の配置の仕方はなので、それら全てに対して探索を行っても間に合うそうです。
実装
これ実装やない、ただの出力や。
print ".........." print ".........." print "..C......." print ".........." print ".........." print ".........." print "..CC..CC.." print ".........." print ".........." print ".........."
C - 最短経路
問題文
C: 最短経路 - 京都大学プログラミングコンテスト2015 | AtCoder
解法
エッジの数が指定されてないので、とりあえず与えられた最短距離を持つエッジを全部張ったグラフを考えます。このときに問題が発生するのは、頂点 から別の頂点を経由して頂点 に行く経路の長さが、頂点 から頂点 に直接行くよりも短い場合です。このような場合は条件を満たす有向グラフが存在しないことになります。
要は与えられた最短距離から全頂点対の最短距離を計算し直して、与えられた最短距離より短くなっているところがあったらアウトです。頂点数 の制約は() と小さいので、のワーシャルフロイドの出番ですね!
あと、与えられる最短距離の行列の対角成分は当然0になると思いがちですが、今回はそうでないものも含まれてるので弾く必要があります。単純有向グラフの定義では自己辺は存在しないので、そのために入れたんですかね?
実装
参加時は念のためにC++で通したんですが、計算量が なので冷静に考えるとpythonでも普通に通りますね。
問題設定ではの場合に頂点 から頂点 への経路が存在しないのですが、ワーシャルフロイドで計算して行く都合上MAX( = )に書き換えました。いずれかのに対してがより小さければ有向グラフが存在しないので"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で行けるかな?って思ったんですが、の制約が なため相当厳しい..。i日目に到達できる都市の番号が最大でもi+1であることを勘案しても、計算量が位になるのでC++でも無理でした。部分点の制約はなのでこの方法で部分点が取れます。
実装
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についても が成り立つ」ということだそうです。更にポイントとして、都市 での滞在で得られる は何日目であろうと変化しないこと、都市 から都市 への移動は一回しか起こらない、ということが挙げられそう。
解法としては、最後に居る都市 さえ決めてしまえば が最大となる都市 に出来るだけ滞在することでお金を最大に出来ます。言われてみればなるほどって感じですね。先に都市を決めるって発想に至れなかった..。これを各 について求めてしまえば、その最大値が答えになります。
ただし、条件として「いずれの日にも所持金が負になってはいけない」というのがあるので、都市 を決めたら所持金が負にならずに に到達できる最小の日数を求め、残りの日数はが最大となる都市にずっと滞在するという流れになります。
都市 に最小日数で到達するということは、都市に最小日数で到達してから出来るだけ少ない日数で都市 から都市 への移動を行うということ。(都市 に最小日数で到達したときの所持金) が負でなければ即座に移動が行えますが、そうでない場合は が最大となる都市 に滞在しつづけることで、最小の日数で移動可能な状態にすることができます。
実装
dayは都市へ到達する最小日数, moneyはその時点での所持金です。for文の前半で最後に居る都市が であるときの所持金の最大値を求め、後半で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)。普通の長方形と正方形の二パターンしか想定してなかったんですが(↓みたいなやつ)、ほぼ正方形といってもいい長方形だと結果が変わるみたいです。もっと色々考察したり試したりすべきですね。
解法
厳密な証明が出来る訳じゃないんですが、概ね以下のように考えると納得できそう? ※横の方が長い(or縦と等しい)長方形を想定
三角形ABCが長方形(談話室)の内部にあるなら、内接させた方が大きい三角形ができる。 長方形の内部に三角形ABCがある(または、頂点のうち少なくとも一つが内部にある)場合、図のようにすれば辺の最小値を大きく出来ます。
三角形ABCのいずれの頂点も長方形の角頂点(角)に無い場合、少なくとも一点を角に移動させると大きい三角形ができる。 あんまり厳密ではないですが、いずれの頂点も長方形の角に無い場合は図の3パターンなので言えそう。一番短い辺の端点のうちどちらかを動かせば辺の最小値を大きく出来ます。
長方形の一つの辺に三角形の二つの頂点がありかつ、少なくとも一方がその辺を内分している場合、二頂点のどちらかを動かせばより大きな三角形ができる。 これも怪しいけど言えそう。
- [左] 二頂点に内分されている辺の対辺上にもう一点がある場合。これは図の通りに動かせば三角形の辺の最小値を大きく出来ます。
- [中央、右] 二頂点に内分されている辺の隣接した辺にもう一点がある場合。この場合は、同じ辺にある二頂点(A,B)のうち三つ目の頂点から遠い方を動かすと三角形の辺の最小値を大きく出来ます。ただし、右のような場合は最初からACが最小なので、最小値を変えずに点を移動させることになります。
- 三角形ABCが長方形に内接しているとき、一つの辺を固定すると残りの二辺を等しくすれば辺の最小値が最大になる。 固定する辺の長さが小さい場合は二等辺三角形でなくても良い場合がありますが、図のように、固定する二頂点を長方形の短い方の対辺の組に置けば二等辺三角形が最適です。
以上のことを考えると、頂点の一つは角に固定出来ます。最後に述べたことから、頂点をもう一つ固定すれば自動的に最後の点の最適な位置が分かるので、二つ目の頂点で探索を行えば解けます。 一番下の図で言うとCの位置を探索しますが、Cの最適な位置が辺の端点でない場合は、三角形ABCの辺の最小値は以下のグラフのように上に凸になるはずです(※形がこんな曲線になるかはわかりません)。 上に凸ということで、たまにしか使わない三分探索を使う機会がやって参りました。
実装
Bを(0,0)に、Cを(w, mid)に固定したとき、Aの最適な位置は
()
です。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は正方形になるらしい..正直なんでか分かりません。この事実を利用すると二分探索で解を求めることができ、更に言うとで答えを出すことも可能だそうです。
F - 逆ポーランド記法
問題文
F: 逆ポーランド記法 - 京都大学プログラミングコンテスト2015 | AtCoder
参加時に取り組んだけど解けませんでした(その3)。この問題は最後らへんずっと考えてて、方針は合ってたっぽいのに実装がおかしくて通らないという非常に悔しい結果でした。
解法
解説聞いて感動したのが、構文木で考えるとめっちゃわかりやすいということ。問題自体が構文解析っぽいし、解いてるときに「演算子の階層の深さ」とか考えてたんだからむしろ木構造は思いついてしかるべきですよね。思い至らなかったのがとても悔しい。
たとえば数式"(4+3)-(2+1)"木構造で表すと、以下のようになります。 この数式を評価する場合、演算子を評価する際にはその左辺(左の子)と右辺(右の子)が全て評価し終わっている必要があり、その順序によって記法が変わります。
逆ポーランド記法の順番 "43+21+-" を見ると、木を左からdfsして葉(または子が既に並べられている節点)から並べています。スタックで処理すると、演算子の左辺の評価値をスタックの奥に追いやったまま右辺の評価を行えるからうまく行くみたいです。
一方キューで処理しようと思うと、演算子で評価した結果がキューの一番後ろに入ってしまうので同じ順番では無理です。ぱっと思いつかないんですが、実は計算の過程を終わりから見て行けばどういう順番になっているがすぐにかわかります。
同様のことをスタックでもやるとちゃんと逆ポーランド記法の数式文字列が出ますが割愛。
導かれたキューで処理する場合の順番は、木構造を右から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解こうとしたりしてました(そして無理でした)。プロから言わせると典型問題らしい..。
解説では、「から順に対戦相手を決めて行けばよい」って言われてそれには納得したんですが、それを高速で実現する為にはどうするかってのがよくわかってませんでした。この問題は自力で解くのが難しかったので、他の方の参加記等にパクリにヒントをもらいに行くと、
- から決めて行けば、後はBIT使えばOK
- FenWick Treeでやろうとした
- BIT使った
みたいな声が多数。前々から名前だけ知ってたBIT(Binary Indexed Tree)ですが、ついに習得するときが来たらしい。 以下のスライドで勉強させて頂きました、ありがとうございます!
http://hos.ac/slides/20140319_bit.pdf
"「普通に Binary Indexed Tree を使うだけ」の部分で詰まらないようになる"、まさに今の状況ですね。
さてBITは一応実装したものの、対戦相手の決定にどう使えば良いのか全然分からん..と思っていたら、Twitterで
- 優先度付きキューでやった
というTweetを見かけてやっと解法に思い至りました。
解法
最善の解法がどうなのかは不明ですが、この解法では対戦相手の決定に優先度付きキューを、並べ替えの回数を求めるのにBITを使用しています。 ※説明を簡単にするため高橋くんチーム、青木くんチームの 番目のメンバーを、それぞれ と標記します。
まず対戦相手の決定の仕方について。が成り立っているため、の相手は、なる のうち、が最大となるにすれば交換回数が最小になります。についても同様に決定していけば良いです。
問題はどうやって効率的に決定を行うか。ごとにを後ろから見て行って、かつ がまだ誰の相手にも成っていなければ を の対戦相手に決定するのが愚直な方法ですが、これだと計算量がになります。 制約がなのでこれだと絶対TLEです。(部分点は取れます)
そこでまずを要素とするリスト を用意し、これを第二要素(ワザマエ)の大きい順にソートします。するとの対戦相手の候補は、ある が存在して、を満たすに対応するとなります(添字適当ですみません)。 はワザマエ順に並んでいるので、を越えるワザマエを持つものは絶対に先頭から並んでいるはずです。入力例2で考えてみると、以下のようになります。
ポイントは の対戦候補に挙がったものはの対戦候補にもなるということです。A'を先にソートしておくことで、対戦候補の列挙自体はで済むことに成ります。
あとは対戦候補のうち一番右側に居る人を対戦相手に選べば良いんですが、これを効率的に行うために優先度付きキューを使います。対戦候補に挙がったものを全て優先度付きキューに突っ込んで番号が大きい順に並ぶようにすれば、更新がで出来ることから全体でで対戦相手の決定を行えます(計算量については大分適当に言ってます)。
次に交換回数の求め方について。もっかい入力例2で考えてみます。
Nが小さいので例として微妙ですが、要は今から移動させる の右側に移動していないものが何個あるかで を移動させる為の交換回数が決定します。つまり、を移動させる際の交換回数は ()のうち移動済でないものの個数です。この移動済かどうかの値を区間で効率的に管理するためにBITを使います。
実装
pythonのheapqは要素が小さいもの順に並ぶので、実際にはA'の要素はとしています。また、BITの区間和で求まるのは通常[1,a]の区間和ですが、今回欲しいのは[a,N]の区間和なので対応を逆にする(を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
問題文の要約
幅マス, 高さマスの直方体のマス目が与えられる。直方体を成すようにマスをぬるとき、マス分のインクで最大何マスをぬることができるか?
制限
時間 : 2秒, メモリ : 256MB
制約
解法
全探索をしてしまうと最悪計算量がかかってしまうので幅の方だけ探索を行います。塗る直方体の片方の辺の長さをに固定すると、ぬることができる直方体のマス目は
- のとき
- そうでないとき (""は小数を切り捨てる除算)
となるので、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の自然数列 が与えられる。なるの取り方は何通りあるか?
制限
時間 : 1秒, メモリ : 256MB
制約
解法
もちろん、全組み合わせを確かめようとすると通り、最悪で通りあるので1秒では全探索はキツそう。ってわけでDPを使うことにしました。
DPのためのmapとしてdp1, dp2,dp3の三つを用意し、を左から順にチェックして更新します。をチェックする際に三つのマップは
という状態になっており、dp3[ ]の値を答えに加えたあと、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)
さきほどの解法では, について、先にの組み合わせを作っておき、それとが一致するかどうか確かめていく方法でした。しかしこの方法では掛け算の組み合わせが爆発するらしい..
そこで少し考え方を変えてみます。というのは即ち、
と言い換えることが出来ます。この考え方で、を先に作っておき、と一致するか確かめるよう dp1,dp2,dp3を変更し、を右からチェックしていきます。をチェックするときの各mapの状態は、
- dp1 : のとる値(key)の組み合わせ数(value) ()
- dp2 : のとる値(key)の組み合わせ数(value)()。ただし、
- dp3 : のとる値(key)の組み合わせ数(value)()。ただし、 かつ
となっており、dp3[ ]の値を答えに加えたあと、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しちゃいましたが、掛け算の取りうる値の通り数をチェックするときに割り算で攻めるのはとてもいい知見だと思いました。何らかの機会に生かしたい。 あと、左から、右からの値を作っておいて..といった手法も出来そうな気がしますが、mapが個必要になるので、今回の手法の方が好きかな。 hardについては..そのうち..多分..
SRM661 Div2(hard)復習
ちょっと前にSRM661 Div2のeasyとmedを復習したんですが, hardもやっと解けました.
あとこの前のTCO Round2B で無謀にもチャレンジしたせいでレートが200下がって一気に灰色まで落ちました. 泣きたい..
hard(950) : ColorfulLineGraphsDiv2
問題文のおおよその意訳
ボブは以下の2つの手順でN個の節点からなるグラフを作ろうとしている.
1からNの番号をつけた節点を用意し, それぞれの節点にはK色のうちのいずれか一色で色を塗る.
それぞれの節点i から, 節点iと色の異なる節点j に枝を張る. ただし, ボブは枝を張らないこともある.
N とK が与えられたとき, ボブが作りうるグラフの数を求め, で割った余りを答えよ.
解法
枝の張り方は色さえ決まっていたらO(N)で求められますが, そもそも色の塗り方が, 最悪あるので, 塗り方ごとに枝の張り方を考えて数えるなんて事は到底無理. さてどうするか.
色々悩んだんですが, 最終的にDPになりました. 例えば, K=2として以下のようにN=2のグラフにもう一つ節点を加えてN=3のグラフを作ることを考えます.
まず三つめの節点から枝を張らない場合, 好きな色の節点(赤か青)を三つ目の節点に選べるので2通り作れます. 次に三つ目の節点から枝を張る場合, 一つ目の節点に枝を張りたいなら青以外の色, すなわち赤を三つ目の節点に, 二つ目の節点に枝を張りたい場合は青を三つ目の節点に選ぶ必要があります. よって枝を張る場合も2通り作れて, 合計4通り作れます.
上のことは書いてみると結構当たり前のことなんですが, 枝を張る場合と張らない場合を分けて考えるのが一番のポイントなんじゃないかなーと思います. 三つ目の節点の色を決めてから枝を張れるかどうか考えると非常にややこしいんですが, 分けて考えてしまうととても楽です. 枝を張る先ごとに色を決めるってのが超重要.
因みに3色の場合も同様に以下のように考えられます.
枝を張らない場合は3通りで, 枝を張る場合は張る先の節点以外の色を三つ目の節点の色に使えるので2*2=4通り, 合計7通りです.
もうちょっと一般的にn-1個の節点からなるグラフにn個目の節点を加えてグラフを作ることを考えると, 枝を張らない場合は単純にK通り, 張る場合は枝を張る先の節点i ()ごとにn個目の節点にiと違う色すなわちK-1色のいずれかを選ぶことになるので, 作り方は
通りとなります. よってボブの作りうるn個の節点からなるグラフが通りだとすると, 漸化式
が成り立ちます. あとはこの式で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では制約が恐ろしいことになってて(とか), 単に漸化式作るだけでは無理だったそうな.
なにはともあれ, これでSRM661は終わりです. この調子で今までの宿題も少しずつ解いていきたい.