dohatsutsu’s diary

日記を書いています。

【No.029】「ICPC 2016 韓国 Deajeon 参加記 ( 書きかけ ) 」

 

2016/11/6/1:25 この記事はまだ書きかけです。

 

0日目

・集合時刻を勘違いをしていて、本来乗る予定だった電車が出発した数分後に会津若松駅に到着。

・チームメイトは本来予定していた電車に乗って先に移動していたけれど、先生は僕のために駅に残ってくれていたので、先生と一緒に成田まで移動してチームメイトと合流。

・飛行機で成田空港から仁川国際空港へ移動した後、そこからさらにバスで大田まで数時間の移動。

・バスの中でツイッターをしていたら、実は飛行機に乗っている間にchokudaiコンテストが開かれていたことに気づく。参加できなくて残念。

・東横インに着いたときにはすでに午前1時ぐらいになっていた。

・近くのセブンイレブンに行ってアイスとぶどうジュースを購入した。

・テレビのチャンネルを適当に変えていたらムーミンが放送されていた。

 

 1日目

・午前中はほとんどホテルの部屋で眠っていた。

・タクシーで会場まで移動してKAISTの食堂で昼食を食べた。

・練習セッションの問題はつくば大会のときよりもずっと難しかった。

・sate君にコンパイルエラー(というよりはwarning)の原因を相談されたのでコードを見てみると、return 文を書き忘れていた。

double dot(P a,P b){ a.real()*b.real() + a.imag()*b.imag(); }

 

・練習セッションが終わった後は京都大学の人たちと一緒に夕飯を食べに行きました。

・そのあとはホテルの部屋に戻ってTypingWarを15回ぐらいプレイして就寝。

 

2日目

・無事に起床して会場へ向かう。

・A問題はkzykt先輩から概要を聞いて少し考えても全く分からなかった。

・B問題はsate君がTLEを出していて大変そうだったので相談して解くことに。

・考察しても全然分からないけれど順位表を見ると結構解かれているので、仕方なく自信がそんなに無い解法を提出した。

・ACしたものの、すぐに思い浮かんだけれど実装する勇気が出なかった解法だったのでACして辛かった。

・C問題は nの最大値が1,000,000で、O ( n  *  log n   *    log  n ) の解法がすぐに思い浮かび書いてみるがTLEしてしまい辛かった。

・定数倍の高速化を行っても TLE が消えなかったので、チームメイトに高速化の案を出してもらうことに。

・sate君が sort関数によって発生する計算量を消す方法を実装してくれてACしました。

 

・D問題はkzykt先輩から概要を聞いたとき、与えられるグラフが2部グラフかどうかが分からなかった。

・2部グラフじゃないと解ける気がしなかったので、問題文を読んでみることに。

・入力で与えられるグラフは2部グラフであることが保証されていたので、ライブラリのbipartite_matchingを写す。

・bipartite_matching 2回分の計算量なのにもかかわらずTLEがでて辛かった。

・定数倍改善をしたらTLEがとれてACしました。

 

・E問題はコンテスト終了2時間前に実装し始めた問題で、すでに体力がかなり消耗していたので辛かった。

・' ) 'の構文チェックを忘れていることにkzykt先輩が教えてくれました。

・何度か見直してもバグっているところがなさそうだったので、ハッシュが衝突している可能性に賭けてみることに。

・ハッシュ値のmod を 2の64乗から 1,000,000,009にするとACしました。

 

・その他の問題は完全にチームメイトに任せていました。

 

 

・最後の5分間が精神的に一番辛かったです。