*1模擬国内予選は4完23位で、ちょっとうまくいきすぎたので本番で失敗するんじゃないかと不安になっていました。本番は4完26位でした。CとDの傾向が過去とかなり違っていて動揺しましたが、ほかの2人の活躍によって、かなり早い段階で4完できました。4完した時点ではEを解くのに十分な時間が残っていたので5完したかったのが本音ですが、とりあえず予選通過の目標は達成できそうなので、今回の反省をアジア地区で活かせるように頑張ります。AC)Aは私が早解きするという作戦でしたので、私が担当しました。...」と念じながら問題ページを開いたら、まさかのシミュレーションで動揺しました。印刷したりvimrcやMakefileを書いていたら通すまでに10分くらいかかってしまったけど、これは想定内。AC)B問題はOUDON氏が担当するという作戦でしたが、「問題の解釈がよく分からない」と言われて私が担当しました。問題を受け取って読んでみても、確かによく分からない。去年のJAG夏合宿で解いた問題に似ているけど、あの問題は@peryaudo先生にやってもらったんだよなぁ...なんか下の行から処理していくと簡単そうな感じがしたので実装したら一発で通って拍子抜け。AC)「構文解析よく分からないので引き続きよろしく」と言われて私が担当しました。読んでみると私が得意なパターンの構文解析で、「去年の国内予選Cよりも簡単じゃね?」という感じでAC。AC)電車の路線図を題材にした露骨なグラフの問題。今月に入ってから過去問を解き直して練習していたので、私がPCを奪い取って担当しました。「A社とB社の1dayパスポート(100円)」と「A社とC社の1dayパスポート(200円)」を合成して「A社とB社とC社の1dayパスポート(300円)」を作ったりしたら楽だよね、ということに気づけたのは良かったです。この手の問題は下手にDijkstra法で書くよりもBellman-Ford法で書くほうが楽だということを練習で知っていたので、Bellman-Ford法で書きました。40分くらいで実装できましたが、案の定バグったのでみんなでデバッグすると、23氏が「スタートとゴールの頂点番号を1-originから0-originに直すのを忘れている」というバグを、OUDON氏が「1<<Kと書くべきところを1<<Pを書いている」というバグを見つけてくれて、なんとかAC。(ミスリードその2)解けそうな雰囲気がないので諦めました。F着手できそうな問題がこれしか残らなかったので、みんなで考察。「包除原理で重複をうまく計算する」というようなありきたりなことしか思い浮かばず、時間切れ。G私がCに着手した時点で「観賞用」という報告を受けていたのでスルー。...」と念じていたにも関わらず、解法が思い浮かばなくてかなり焦る。「なんだ、税抜き価格を全探索するだけか」ということに気づいて愚直に実装したら模擬予選よりも早くにAC。OUDON氏から「早すぎるww」的なことを言われましたが、終わってしまったものは仕方がない。AC)OUDON氏に丸投げしました。バグったそうなので23氏と紙デバッグしてもらっているうちにAC。AC)Bと平行で私がコーディングしました。いうか、Bよりも先にACしました。角に太陽の円周が触れる時間の最小値を求めるという方針でコーディングしました。ビルの角の位置を求める処理が少しゴリ押し感がする書き方をしていたので、バグらないか不安でしたが、あっけなくAC。この時点で1時間たっていなかったので、少し余裕ができました。AC)「DPが来るに違いない」と思っていたら、まさかの謎問題が来てかなり動揺しました。23氏に「N<=20だからO(2N)が通るよね」という話をされたけど「どういう探索になるかわからないから問題なんだ!!よ!!」と若干キレ気味に返してしまいました。その後「それぞれの文字についてインクリメントするorしない」で候補を列挙してから実際に暗号化してみる、という解法を23氏とOUDON氏に提案されて、粛々と実装するとサンプルが合う。23氏、正直すまんかった。サンプルが通ったので投げてみるとWA。(setにする前はpriority_queueに最初5つと最後5つを保存していました)。tailfコマンドでD1.outの出力を眺めながら実行が終わるのを待って、その間に順位表を眺めたりしてAC。E23氏が「最初の点と最後の点は遠いほうが明らかにコストが小さくなる」ということを主張してくるが、葉の扱いだけ特別扱いしなければならないあたりで怪しさを感じてしまい、O(N3)の全探索解を書く。1時間以上残っているのだからもうちょっと考察してからかけばよかったのに、いきなりコーディングを始めてしまい、泥沼にはまってしまったので反省しなければならない。F23氏とOUDON氏ががんばってサイコロを製造したりしていたけれど、私は問題を読んですらいません。G「あっ!これ暇な時に3時間くらいかけて解くやつだ!」ということが瞬時に分かったのでスルー。国内予選まとめEはもうちょっと考察してから書き始めれば、確実に解けた問題なので悔しいです。あと、D問題はAOJに収録されてもたぶん通らないので、後で書き直します。参加して32位でした。参加記チームbroken_keyboardで参加して、ABCDFを解いて19位でした。(1)はてなブログをはじめよう!kujira16さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。