The 2015 ACM-ICPC Asia Daejeon Regional Contest 参加記(コンテスト)

今度はコンテストの方です．コンテスト以外は→The 2015 ACM-ICPC Asia Daejeon Regional Contest 参加記(コンテスト以外) - kyuridenamidaのチラ裏

毎回敬称が消えるのでまーすさんとustimawさんについては開き直って敬称略とします．敬称は心のなかで付いています．心のなかで．

タイムスタンプから記憶復元してるんで，結構細かい時系列バグってるかも．

順位表のリプレイ

問題文

コンテスト前

  • 日本語キーボードが使えるかどうかだけがめっちゃ心配だった．
  • 10時から開始となっていたけど，少しだけ開場が遅れている．
  • 大丈夫かなあと思ったけどちゃんと始まった．

[00:00]コンテスト開始

  • 開始後ただちに僕がキーボードを繋ぐ．
  • 開始後，まーすがVSの設定をする ∧ キーボードの設定を行うことにする．
  • ちゃんとキーボード日本語で使えてるっぽい．
  • コンテスト問題1部しかない...千切る．僕はA,B,C,Dを読む．ustimawがI,J,K,Lを読む．
  • Aはフローっぽい，Bは物理っぽくてエグそう，Cはめっちゃフローっぽい，Dは読めない
  • AとかCの題意をまーすに説明したりする．少なくともCはフローですねとなる．
  • 少しして一部の問題の読解が終わる．ustimawがJ解ける?と言う．
  • J問題の題意は「整数K(7≦K≦1000)を3つの素数の和で表せるなら具体的な構成を1つ，そうでないなら0を出力する」
  • (これは弱いゴールドバッハ予想不可避ですね...(しかも最近CF Div2で出た))
  • まーす「余裕やで」
  • まーすがパパッと実装して，きちんといくつかのテストケースを手元で試す．少々バグるがVSの力でデバッグが30秒くらいで終了．それでも割と慎重に試す．

[00:19]J AC

  • 僕がA考えてたらustimawが「L簡単そうやし読解してくれん?」と言う．
  • 順位表を見ると既に3完してるチームがいる...やばいやばい．
  • とりあえずustimawがIにとりかかる．Iは株を売買する問題．
  • サンプル合ったので出してもらう

[00:28]I AC

  • Eの解法は詰まっているらしいのでEはまーすが書く．
  • Lは本当に記述量の短いやるだけだったので，僕はL誤読してないか再確認して，具体的にどうタイピングするかを完全にイメージする．
  • まーす「サンプル合ったので出してみる」

[00:33]E AC

  • 当然結果が返ってくる前にバトンタッチ，僕はLを書く．書いてる途中にEがACしてることが分かる．
  • 実装が終わる．手元でサンプルが通る．とりあえずPC^2でも通ることを確認．

[00:36]L AC

  • よしよし4完．11位くらい．でも全員4完で止まっている…．
  • Cとかがフローっぽいのに上位チームが4完で止まっているのは不思議な感じがする．ライブラリ貼れないからかなあ．
  • まーすにフローだね，と承認を受けたのでとりあえず僕は最大流のライブラリを写す．
  • 僕がライブラリ写してる間にまーすが「HはFaulhaber's Triangleそのままで数論ライブラリに有るから貼るだけ」と言い出す．
  • ustimaw＆ぼく「！？」
  • まーす「入れてて良かった数論．まさか役に立つとは．」
  • フローを写した後，Cがグリッドグラフだから二部マッチング的なフローというのは分かるのだけれど，辺を何回も使えるし，いまいちどう辺張ればうまくいくのかただちに思いつかなかったので実装をまーすに任せる．
  • その間に写経したソースを印刷して間違い探しを行う．いくつか見つかる．
  • とりあえずサンプルが一致．提出する．

[00:54]C AC

  • 2位になる．
  • とりあえずまーすがHのライブラリ写経する．
  • その間Aの解法について話す．
  • ustimaw「A，最小費用流で行けないかなあ」
  • ぼく「交差するケースないかなあ...あーーーいや無いか..なさそう．それで上手くいきそう？」
  • ustimaw「Kなんですが，木の編集距離って一般的な概念ですかね？知ってますか？」
  • まーすとぼく「知らないなあ...」
  • まーす「サンプルが1あわへんねんけど手計算を...いやこれは俺がやったほうがいいか」
  • (数分後)まーす「あっ，これ総和がk=0からだ．ライブラリと少し違う．」
  • サンプル一致した．出します．
  • ジャッジ待っている間慶應にタイムペナルティで負けていることに気づく．やばいなあ．

[01:18]H AC

  • 6完きたー！！1位だうおお！！
  • ぼく「ナイス！！(大声)」
  • まーす「うるせえぞ騒ぎすぎ」
  • ぼく「すまぬ」
  • 僕たち「話し合ったんですけどA問題，WFして最小費用流で行けそうじゃないですか」
  • まーす「いけると思う」
  • ぼく「WFのO(n^3)，この制約で最悪ケースが大量に来たらTLEするかもですけど定数倍軽いし韓国大会だし大丈夫ですよね..?そもそも最小費用流でもそれくらいかかりそうだし..(ただ二部グラフの最小費用流なので最悪ケースを達成しそうにもないなとは思っていた)」
  • まあ大丈夫だと判断して最小費用流を写す．10分くらいして写経が終わる．
  • ぼく「あの，フローのグラフ，構築するの苦手なんですけど」
  • まーすたち「え～」
  • ぼく「これワーシャルフロイドして二部グラフにしたらいいんですよね．ソースから左に繋いで，右からターミナルに繋いで，真ん中はそのワーシャルフロイドグラフで...誰かやりませんか？」
  • まーすたち「せやで．自分でやりゃええやん」
  • ぼく「やります．ライブラリチェックustimawさんお願いします」
  • ustimaw「こことここが間違ってますね」
  • ワーシャルフロイド書いて黒い頂点対にだけ辺を貼る．
  • バグる．まーすにデバッグバトンタッチ(なぜなら彼はVisualStudioマスターだから)
  • ステップ実行してたら配列のインデックスがバグっていることに気づく．修正してみる．サンプルが合う．
  • 出してみる．TLEしたらワーシャルフロイドの部分を幅優先探索に書き直そうとか思う．
  • 自分の担当分だし，通って欲しくてめっちゃ祈る．

[01:40] A AC

  • よっしゃー！！！首位維持！まーすのHのアドバンテージがかなり利いている．
  • ここから解法が判明しているやつが少し怪しくなってくる．
  • Fはみんな考えたけどいまいち上手く行く確証がないし上位校でさえWAしてるチームが多すぎてかなり危険問題と判断していた．
  • ustimawと息抜きに別の問題考えてみない？と考える問題を入れ替えたりしてみる．
  • Dは誤読の可能性があってまだだらだら読んでいた．
  • ustimawとBは連立方程式系だけどサイズがでかすぎるから反復法等の近似計算で成り立つ系じゃない？みたいな話をする．ただし連立方程式が本当に収束するかどうかは分からない．
  • Kは僕らはさっぱりだったが，まーす曰く「O(n^3)っぽいんやけど書いてみたら速い系かも，それしか思いつかんのよね」
  • まーす「とりあえずそれでいこう．詰めとくからきゅうり入力を木に直す部分書いてくれる？」
  • ぼく「はい」
  • とりあえず書けたらまーすにバトンタッチ．
  • まーすがKを書いている間Dとかを考えたりしてみる．ustimawの仮説に意見を求められたりするけどいまいちピンと来ない．苦手なタイプの問題だなあ．Fについても，お互いにFを考えたときに得られた知見を共有してみるが進展無し．
  • Gは僕は問題概要を聞いただけでノータッチ．「なんか無駄な角を取り除く感じで，嬉しい列を持つテクみたいなやつでは？」みたいな適当な提言だけして終わる．
  • Kが書き上がったみたいで，まーすがKをVisualStudioの力でパパッとデバッグしている...
  • サンプルが一致したらしい．出してみる．

[02:22]K AC

  • まーすのテンションが上がってくる．
  • うおおおすごい！！！
  • 解ける問題もうなくなってきたなあ...残るはB,D,F,G
  • まーすがG問題分かったけどこれ実装重いなあ...と言う．1時間くらいあれば通せるかも...と言っている．
  • まーすにGの実装を任せる．
  • 横から見てて境界とかがめっちゃ面倒くさそう...頑張れまーす．
  • まーす「あれ，G問題これベースセグメントってx軸通らへんの？」
  • ustimaw「そうとは限らないっぽいよ．サンプルがこんな感じっぽいよ(図示)」
  • 実装量が多い分僕は無駄に不安になり，ちょいちょいまーすさんが「こんがらがってきた...」とか「誤読してた...」とか言う度に「破綻とかはしてへん？」「解法は確信あるん？」とかクソリプを飛ばすマンになっていた．
  • まーすが「いや破綻とかはしてないよ．実装仕切ったら絶対通ると思う．」と言ってくれて安心する．
  • とりあえず昼食とりつつ僕はB問題についてどういう性質があるか考える．ていうか勘違いを防ぐためにBの入力部分が具体的にどうなっているのかをちゃんと頭に叩き込む．インデックスに負の値が発生してたりしてビビる(物体のidか固定点のidかを区別するためにそういう入力らしいｗ)
  • 「Bの連立方程式を成分毎に考えるのしんどいしなんか√とか出てきて一次連立方程式じゃないやん～～」とかよくわからんこと言っていたらustimawが「ベクトル使えへんかなあ」と言ってくれて電流が走る．当たり前のことになぜ気付かなかったんだ．少し怖かったので実際に成り立つことを確認．
  • 実際にBのサンプルの行列書いたりしてみる．手書きの行列の上では固定点の座標を定数として扱っていてやや絶望感が漂う．
  • 「Bはやってみなきゃ分からない系」だと主張しまくる
  • Bを反復法(加速するやつ)でやるとして，収束速くするにはどういう嘘改善をすると良いかみたいな話をustimawさんとする．
  • Bの改善案として出たのは，固定点から芋づる式に位置の変化が伝搬するようにソートしておくとか，初期値をうまく決めるとか...．
  • まーすがGを書き上げたっぽく，Gのデバッグをしている．手計算結果とステップ実行における変数の値を逐一確認しながら手際よくデバッグしている．すごい．
  • サンプルが一致したらしい．
  • まーす「まあサンプルは合ったんだけどうーん...」
  • かなり実装量が多そうだなあ．出してみるしかないので出す．
  • まーす「トイレ行きたいけど結果見てからじゃないとトイレ行けねえよ～～」

[03:41]G AC

  • チーム内でめっちゃ湧く．
  • まーす「よっしゃあああ！！！！！！」
  • チーム「うおおお」
  • まーすのテンションが最骨頂に達している．いつも冷静なustimawさんも珍しくめっちゃテンション高い．
  • ぼく「テンション高ない？ｗ」
  • まーす「テンション上がらざるを得ないでしょこれは...疲れたからあとは任せたゾイ」
  • これスロットほぼ確定では，今までWA0でペナルティでは負けないしみたいな話をする．
  • ustimaw「まあ油断はしないほうがいいよね」
  • とりあえず残り何やるかというと，Bが一番簡単そうに見えるので，半分ダメ元で書いてみる．なんか制約多いし，物理的な題材だし，勝手に嬉しい性質成り立ってくれやと願う．
  • なんかみんなトイレ行ったり食べ物取りに行ったりしていて気づいたら僕一人が席に座っていたりする．

[04:00]順位表凍結

  • 同完数で2位のKAISTがFに提出した結果が返ってくる前にstandingsが凍結される．
  • Bで，固定点を変数として置いたりしたほうが実装が楽だということに気づいて置いたりしつつ，とりあえずソースを書き上げる．
  • なんか普通にセグフォる．まーすにデバッグしてもらう．
  • 入力ミスだった．それでも答えが合わない．うーん実は連立方程式が間違ってんのかなあ...
  • サンプルが実は合わないからみんなだしてないだけでは...???
  • いや，連立方程式にサンプルの答えを入れたら連立方程式が正しくないということはなさそうということが分かる．
  • よくみると反復法の式を間違っていた--;
  • それを修正したらサンプルが合う．
  • ってことは，みんな敬遠してるだけか(確信)
  • あとは完答数の戦いになると思うから，WAいくら出してもええんちゃうかみたいな話になる．
  • とりあえず変数N≦1100としてO(N^2*反復回数)の反復法を反復回数を100にして出してみる．
  • 一回の反復における変更幅の最大値がε以下になったら打ち切りみたいな条件にもしたかったけど，とりあえずどれくらいループが回ったらTLEするのか気になるのでそれはしない．

[04:21] B Wrong Answer

  • あ，TLEではないんだ．まあWAですよねえ．
  • ustimaw「芋づる改善入れてへんのか．容易に反復時間かかりそうなケースが作れるんだから入れたほうがよさそうじゃない？」
  • きゅうり「どうしようかなあ．実装だるいなあ．」
  • まーす「まあ面倒くさいならお手軽改善からはじめない？」
  • まーす「行列は疎？疎なんやったらうまくデータ構造持てばよくない？ていうか疎なんやったら本質的に反復法のオーダー改善せえへんか？」
  • とりあえず疎行列を持つデータ構造にしてみる(普通に非ゼロ要素だけ持つだけ)．
  • オーダー改善してる気分だったので1000回反復にして出してみる．

[04:33] B TLE

  • チーム「あれ，1000倍速くなったと思ったんだけどなあ．うーん．ちょっと変えてみるか．」
  • 反復回数300にしてみる

[04:34] B TLE

  • あれれ...100回にしてみる．

[04:36] B WA

  • 200回にしてみる．

[04:37] B WA

  • よく覚えてないけど適当な改善してみる

[04:38] B WA

  • やっぱ収束してないっぽい...?
  • 適当に全ての物体の初期点を重心に置いてみる．
  • まーす「定数倍改善は任せろ～～」
  • まーすがvectorとかをうまく減らして定数倍改善を試みる．
  • ぼく「全部のケースで何百回も回す必要はないし，TLEしなかったら収束してることがわかるし，epsによる判定がいいと思うなあ」
  • epsをサンプルが通るくらいの適当な値にしてみる．
  • なんか色々やったなあと思いつつ提出．

[04:43] B WA

  • あ，収束を誤判定してるっぽいな？
  • もう少し適当に弄る．
  • 出してみる．

[04:46] B WA

  • まだ収束を誤判定してるっぽいなあ．
  • さらにもう少し適当に弄る．
  • とりあえずダメ元で出したので，芋づる式実装しようかなあという話になる．

[04:47] B AC

  • まーす＆きゅうり＆ustimaw「！？！？？！！？！？！？！？！！！！！！！！！！！！！」
  • ｷﾀ─ｗﾍ√ﾚｖ～(ﾟ∀ﾟ)─ｗﾍ√ﾚｖ～─!!!!
  • チームがめっちゃ湧く
  • 残りの時間はもうどうしようもないので，順位表を見て，最悪ケースで自分たちがどうなるかの見積もりを行う．
  • このチームにはペナルティで勝てるだとか，SNUのCompCertが提出しているものを全て通していたらヤバイだとか，そんな感じのことを話す．
  • ひたすら祈る．

[05:00] コンテスト終了

  • あとは祈り

感想

  • 9完で油断してたけれど，結果として10完が結構多かったので，B通してなかったらかなりやばかった説がある(それでも3番手なのでいくらかスロットがもらえたかもしれないけれど，割り当てられてるスロットが2.2とかだと1.0ずつ消費されて多分かなり厳しかった．
  • 韓国で色んな運を使い果たした気がする．
  • まーすライブラリヤバイ
  • ていうかチームメイトの一発AC力ヤバイ
  • ustimawさんのベクトルで考えようぜの一言がなければ多分B解けてなかった．
  • 割とチーム練習とかあんまりしてなくて日常的に会ってないと，お互いがお互いに遠慮して声かけづらくなるんだけど，チーム練習とかのおかげで気軽に何かしら指摘できるようになっていたのは大きかったかもしれない．
  • 特に息抜きに問題交換しようと言ってくれたおかげで色んな問題を読んで考えることができた．個人でコンテストに参加してると絶対こういうことはできないのでうまく働いた気がする．
  • 途中まででもここまで1位をキープできたのはチームで初めてだと思うし，今までの練習よりも遥かに良いパフォーマンスを出せた気がする．それは問題の相性が良かったからなのかstandingsがあったからなのかはまだ分かんないなあという感じ．いや，多分まーすがVS使えたからだと思う．多分そう．
  • B，0WAは無理だけど少なくとも5WAくらいには抑えれたんじゃないか説はある（ただたくさん投げて完答数が増やせたら嬉しいという状況だったし，後からなら何とでも言えちゃいますね）

The 2015 ACM-ICPC Asia Daejeon Regional Contest 参加記(コンテスト以外)

※ろくに推敲してないんで誤植っぽいのあったらtwitterで教えてください．

11/5-11/8に，@ustimawさん(M2),@__mathさん(M2),@kyuridenamida(B3)，コーチの@mitaki28さん(M2)の4人で，チームchikOkUとして韓国大会に行ってきました．全体2位，大学別2位でした．一大快挙です．

韓国予選に参加するまでの流れ

最初は台湾か韓国かで悩んでいたのですが，台湾はそもそもスロットが少ないしNTUがメダル取ってないのでかなり厳しいと台湾のICPCerに教えてもらったのにも加え，夏合宿あたりでもそういう話が出ていたので，韓国予選に参加することに決定しました．9月の出来事です．

僕は去年府大高専のチームとして台湾の地区予選に参加したのですが，その時は参加費が必要ではあるがホテルや送迎バスも手配してくれるという至れり尽せりな対応でした．

韓国予選はそういう感じではなく，参加費は一切ないが自分たちでホテルを手配して自分達で会場に着てくださいという方針でした．この辺のおもてなしみたいなのは地区予選によってかなり異なりそうです．

コンテスト環境の発表は遅くて，10月末にコンテスト環境の詳細が公開されました．

なんとキーボードが持ち込めるそうなので日本語配列キーボードを持って行きました．

しかもVisualStudioが使えて，うちのチームはVisualStudioのプロ(@__mathさん)がいるので相性は最高そうでした．

ここ数年はずっと大田(Daejeon)のKAISTという学校で開催されていて，ソウルの仁川国際空港からバスで3時間弱かかります．コンテストが金曜日(練習)と土曜日(本番)なので，前泊と後泊をすることにしました．

持ち物

  • 髭剃りと歯ブラシ(韓国は法律で使い捨てでこれらを提供することが禁止されているらしい．ただ色々実情は複雑っぽいので調べてください．)
  • パスポート・学生証(コンテスト会場で学生証を見せることはありませんでしたが一応．パスポートで全ての身分証明を行いました．)　追記:筑波の人たちは学生証とパスポートをどちらも見せたそうです．
  • クレジットカード(楽天VISA)
  • 海外WiFiルーター(1台)　←海外旅行の際はとてもおすすめ!
  • 海外旅行保険
  • 現地地図（乗りたいバスの情報やコンテスト会場の住所やホテルの住所が書かれたもの）　←超重要
  • キーボード(RealForce)
  • 辞書・ライブラリ(25ページ)
  • ノーパソ・携帯充電器
  • 電源変換アダプタ・たこ足(ただ東横インには110V電源の口があったので必要なかったかも．びっくり．)
  • 手荷物で持ち込める程度の荷物．(ただ余裕があればスカスカのキャリーバッグを持っていったほうが，お土産やコンテストで貰ったスポンサー景品をぶちこめて良いと思う)

宿泊施設・移動手段

  • 宿泊施設には東横インを選んだ．3泊で，1人あたり日本円で合計12000円相当しないくらいの値段で泊まれた．設備も普通に泊まるには全く問題ないし，フロントは日本語が通じるし朝飯は出るし最高だった．
  • 大阪⇔韓国の移動手段としては，関西国際空港から仁川国際空港まで飛んでいるピーチ航空を選んだ．金子先生の記事によるとLCCはオススメしないそうではあるが(それはスケジュール通りに着かないと参加できないからそう)，学校からの補助等がある場合は絶対普通の飛行機のほうが良いと思う．
  • 大阪⇔韓国のフライトは2時間かからないくらいでたどり着ける．本当に近い．時差もゼロです．
  • 仁川国際空港⇔大田は直通の空港バスが存在するのでそれを使う．乗車時間は3時間程度で，価格は1人あたり23000ウォンくらいだったはず．学生証を見せたら5000ウォンくらい安くなった可能性があったらしいが我々は知らなくて…．ありゃま．
  • 英語の普及率は日本と同じくらいなので，空港のバスの運転手とはいえど全く英語が通じない場合もあった．「自分の降りたいバス停名を印刷した紙を見せて指を指す」のが一番良いと思う．
  • バス停⇒東横インまでは頑張って歩いた．迷いながらだったので15分くらい．事前に地図を印刷するか，スマホがあればたどり着けると思う．我々はスマホで頑張って辿り着いた．後述の通りタクシーが安いので，どうしても辿りつけなければタクシーを捕まえるというのも選択肢かもしれない．
  • 東横イン⇒KAIST(ムンジキャンパス)はフロントでタクシーを呼んでもらった．KAISTとしか伝えなかったせいで最初のタクシー運転手にはメインキャンパス(ムンジキャンパス)ではないところに連れてかれて焦った．後から考えれば当たり前だった．余裕を持った行動をしていたのでなんとか別のタクシーを捕まえることが出来，辿りつけたから良かったのですが…．自分の行きたいところの住所の書いた紙を運転手に見せるのは超重要です．怠ると痛い目にあいます．ちなみにタクシーは非常に安く，20分くらい乗っても全員で一回6000ウォンとかだった気がします．割り勘すれば1人あたり150円とかです．
  • KAIST⇒東横インはスタッフの人にタクシーをコールしてもらいました．今年は日本語が流暢なスタッフが居て助かりました．毎年居らっしゃるかは分からないですが．ただ，なかなか時間帯的と立地的にタクシーが捕まらないことが多いらしく，かなり苦労されていました．
  • 大田⇒仁川国際空港の帰りのバス停は，降りたところとは異なっていて，感覚的にホテルから結構遠かった．雨が降っていたから動きにくかっただけかもしれないけど．バス停で当日チケットを買おうとしたんだけど，本当に全く英語が通じず焦ったので，やはり行き先と買いたいバスの出発時刻を指さしで伝えるくらいのことは重要だと感じた．韓国語で何かを確認されても分からないというのはお互いに困る．言語はお互いが出来ないと意味が無いということをしっかり頭に入れて，英語に頼り過ぎないこと．僕らの場合は突然背後から親切な方が現れ英語⇔韓国語の翻訳をしてくれたので事無きを得たのですが……．空港のバス受付では英語が通じたから大丈夫だろうという慢心が仇になった．
  • 行き，帰りどちらもバスは大体の時間帯で20分おきに運行してました．

ご飯

  • 韓国の飯は総じて美味かった．東横インの朝飯はバイキングで，朝飯としては十分だった．キムチが辛すぎず口にあった．これは韓国でも辛くないキムチがあるということなのか，それとも東横インだからやや日本人向けの味付けになっているとかなのかは定かではない．
  • 知り合いの韓国人に聞くとみんな「チキンは最高」と口を揃えて言うので，ホテルのフロントにオススメのチキン屋さんの場所を聞いて，近くにあるBBQというチキン屋さんに慶應大学チームと一緒に行った．チキン，最初一人で1つ頼もうとしてて，メニュー1つ2万ウォンとかして高いなあ，と思ってたら量がめっちゃ多くて3～4人で1つ頼めば十分なタイプだった．まあBBQはどうやら結構お高めらしいが．とにかくとても美味しかった．
  • プラクティスの夜には台湾チームに誘われて東横インの近くで焼き肉を食べた．僕の行ったところは，焼き肉の味自体は日本の焼き肉とそんなに変わらなかったけど，サイドメニュー(チヂミとかキムチとか)が無料でおかわりできるシステムで良かった．
  • コンテスト中には軽食が提供された．巻き寿司とかサンドイッチを取って自分たちのコーディング席で食べる感じだった．
  • コンテストの表彰後にはレセプションがあった．あんまり食べなかったけど結構シェフがリアルタイムに肉焼いてたりしてよかった．
  • コンテストが終わった後，筑波大学のコーチにボングス・ライスバーガーというお店に連れて行ってもらった．KAISTからゆっくり歩いて10分くらいのところにある．ファストフード的立ち位置の食べ物で，かなり手頃な価格かつ安くてうまい．2500ウォンとかで食べれた．これはチキン並におすすめ．

出発日(11/5 木)

  • 12:40発なので，天王寺に9時集合で空港に向かい，10時20分頃に到着しご飯を食べる．無難に蕎路坊．
  • 食い終わったらLCCターミナルに移動してチェックイン．
  • 飛行機では寝て過ごす．
韓国到着
  • 14:35に空港に到着し早速バスに乗る．バス運転手さんが韓国語で何かを確認してくれるんだけど分からなくてみんな辛い気持ちになる．後で考えると荷物をトランクに入れるときに「どこのバス停で降りるのか」を聞いてくれていたんだと思う．
  • バスでの3時間，寝たり問題解いたり色々する．バスは普通．
  • 畑にでかいマシュマロみたいなのがたくさん転がっていて，奇妙な光景に__mathさんと盛り上がるけど，肥料であることをtwitterで教えてもらい世間知らずだったことを思い知らされる．
ホテル到着
  • デジョンに到着．ちょっと道に迷いながらも東横インに到着．
  • 東横インの人は日本語がめっちゃ通じて最高．
  • 慶應の人たちも同じホテルに泊まっている．合流，BBQで飯を食う．チキンうますぎて感動．
  • とりあえず早寝する．

レジストレーション・プラクティス当日(11/6 金)　

  • 飯食った後，12:00くらいまでだらだらしてロビーで集合．チームでBBQに再度行き飯を食う．僕はチキンだけ食う．
  • 食い終わったらホテルに戻りフロントでタクシーを呼んでもらう．
  • KAISTに到着...と思いきやどこに建物があるのか分からない．
  • 適当な学生を捕まえて地図見せて建物がどこか英語で尋ねたところ，「違うキャンパスで遠いですね..ここはメインキャンパスで，そこはムンジキャンパスです．シャトルバスが走ってますよ．」と言われて唖然．
  • めっちゃ焦ったもののレジストレーション受付時間には余裕があったのでとりあえずシャトルバスを探す．
  • シャトルバス停でバスが1時間に1本しか走っていないことを知る．かなり焦る．とりあえずタクシー用の電話ボックスがバス停の横にあり，それを用いて呼ぶか悩んでいたところ，ちょうどタクシーが目の前で一時停止してきた．「このタクシーに乗ることができるか?」みたいなのを身振り手振りで伝えたら「カモンカモン」みたいなジェスチャーをしてくれて乗せてもらう．
KAIST到着
  • なんとかKAISTのムンジキャンパスに到着することができ，レジストレーションに成功する．
  • 開会式に参加する．審判長？の"DO NOT TOUCH ANYTHING!!"がめっちゃ印象的．
プラクティスセッション
  • プラクティスではとりあえず持ち込んだキーボードのセッティングをする．日本語配列がインストールされていなくて，予想はしていたが使えない．筑波大学も同じ症状で困っている．
  • とりあえずダメ元でスタッフの人に使えないか交渉してみる．普通にできるよう取り計らってくれる．
  • 汎用日本語キーボードドライバを入れるのに失敗しまくったんだけど，関係ない東芝のドライバーを入れたら使えるようになった．
  • 明日の本番でも使えるよう設定しておきますと言ってくれた．もし出来なかったときはメールを寄越すそう．
  • キーボードの設定に時間を取られすぎて，肝心のTLE等がどう扱われるかのチェックをすることなく練習が終了．その理由が練習システムがぶっ壊れたらしく12分くらい早く終了したこと...orz
  • 練習のB問題が練習というレベルでは全く無くて，どうやって解くのか悩む．KOREA UNIVERSITYが爆速で解いていてびっくりしたけど，後で調べて見たら今年の韓国の国内予選の難しい問題だったらしい．
夕飯
  • 夕飯直前に，韓国委員会からちゃんとキーボードセッティングできました！というメールがきて感動する．
  • 練習が終わった後，台湾チーム(NCTU)も東横インに泊まっているということで，ホテルのロビーで夕食の待ち合わせの約束をする．あちらが焼き肉のお店に連れて行ってくれた．
  • 焼き肉屋では色々話す．NCTUのICPC事情とかもいろいろ聞く．なんか日本は台湾とほとんど同じ漢字だけど微妙に違うものとかあって面白いよねみたいな感じで，自国語でどう漢字で書くかみたいなことをして盛り上がったりする．あとはICPC過去問の解法とかについて話したりする．NCTUの人たちはすごくやる気に満ちあふれていてすごい．英語は聞き取れないが@ustimawさんが神なので聞き取ってくれる．
  • その後ホテルに帰ってからは部屋でゴロゴロする．ゴロゴロしてたらNCTUの人が「バナナジュース多く買っちゃったんですけど1本いかがですか」みたいな連絡をくれて，バナナジュースをもらう．結果として美味しかった．最高．
  • 明日は早いのでよく寝る

コンテスト本番当日(11/7 土)

  • 朝8時までに朝飯を済まして，朝8時くらいにホテルでタクシーを呼んでもらおうみたいな流れになる．呼んでもらった．
  • 今度はきちんと目的地を伝えた．移動の間，「日本人？」と聞かれそうだと答えると，長崎旅行に行った話をされ，写真をめっちゃ見せてもらう．
  • 挙句の果てに運転手の友達に電話をかけ，なぜか雑談させられるｗ相手は日本語が通じる人だった．「最近は中国ばっか行ってるけど昔はよく大阪城とか行きましたよ」等話される．
  • 雑談しているうちにキャンパスに到着する．とりあえず待機室みたいなホールでコンテストサイトの開場を待つ．
コンテスト開始
コンテスト終了後
  • 15時10分くらいにコンテストが終了する．凍結前の順位は1位．
  • 阪大に留学しにきている競プロやってる韓国人の友達(@nbkwon)がいるんだけど，その子の元の大学の友達が本戦にきているらしく，話しかけに行く．なんと面白いことに真後ろのチームだった．相手はこちらを認識していたみたい．どうやらフローアルゴリズムを用いるべき問題で貪欲方針に走りハマっていたらしい．悲しい．
  • NCTUのコーチや筑波のコーチからъ(ﾟДﾟ)ｸﾞｯｼﾞｮﾌﾞみたいな感じのことを言われる．
  • とりあえず，下から激ヤバ浮上してくるチームが無い限り2位は取れるのではみたいな見積もりをコンテスト中にしていたのでかなり嬉しくなる．SNUのCompCertに完数で負けたりする不安はあった．ただ，KAISTに勝てるかどうかが気になっていた．
  • 筑波の話を聞くと，日本語キーボードが使えなかったらしい．マジかよ…．それなのに途中あんなに追い詰められていたのか...みたいな感じでびっくりする．
  • ここからは韓国語による講演が2時間程続いて，その後順位表発表らしく，おそらく開場にいても何も分からず終了してしまうということで，ライスバーガーを食べに行く．
  • ライスバーガーを食べる．美味い．セブン-イレブンで飲み物を買う．「男」と書かれた変な飲み物を飲んだらすごくまずかった．
  • 5時に順位表発表やるので戻ってきてくださいと言われていたので，ライスバーガーを食べ歩いて4時40分くらいに発表会場に戻ったら，すぬけが腹減ったらしく食べに行くところはないかみたいなことを言っている．
  • 仕方がないのでライスバーガーに一緒に行く．
  • 慶應は色々な問題でハマりまくってめっちゃ辛かったらしいという話をする．我々はまらなかったの本当に奇跡では...
  • なんか食べたかったので僕ももう1つライスバーガーを買う．
  • コンテスト会場に戻ってるとき，すぬけに会計直後くらいからリュックサックを奪われていることに気づく．さすがにセキュリティ意識が低すぎる．猛省．
順位発表
  • 凍結した順位表の解凍は下のチームから行われる．凍結まで0完で，全部提出しているKAISTとSNUのチームがあってビビる．しかもSNUのチームは"up team is up"という名前(後で留学生の友達に教えてもらったですが，韓国のやきうネタで，とある選手が残した名言(迷言?)の一つに"down team is down(下がるチームは下がる)"というものがあるらしくそれを意識したネタらしいｗ)
  • 海外チームはスキップされ，まずは国内で順位をつけるらしい．
  • そのヤバイ2チームがどんどん浮上していく．
  • KAISTのサブマリンチームは残念ながら33位で止まってしまったが，up team is upは最終的に8完して8位まで浮上するｗ面白すぎる．
  • 2位にいたKAISTのチーム[A-Za-z0-9]+が解いた問題数がどうなるか緊張していたけれど，さすがのKAIST，11完で1完差を付けられ1位に躍り出た．
  • その後海外チームの順位も公開される．香港大学の大学別順位は分からないけど，慶應が大学別10位，NCTUが9位，筑波が5位，大阪が2位という形になった．
  • 筑波が5位だったのはスロット的にとても惜しくて，KAISTもSNUも強豪大学にしては珍しく海外に全然行かないのでスロット消費が1.0ずつで，4位だと厳しそうだった．キーボードトラブルで初動が遅かったものの，彼らも我々同様WAを最後の方まで一切出してないので，もし初動が早く数論の問題を解く余裕が発生していたら負けていた可能性もあった．
  • 途中まで首位を走っていたこともあり，天狗になっていたのだが，蓋を開けてみれば9完だとちょっぴりスロット的に危なかったので，最後にBを通し，10完できて本当に良かった．
  • ていうか数少ない担当問題なのにも関わらず僕がB担当していることがなぜかツイッターの民にバレていて，その上たくさん提出してたら「きゅうり不正」とか言われてて人々心なさすぎでしょｗｗｗｗってなる．(提出当時から不正と言われていた事実をよすぽさんに訂正されました．ありがとうございます．)

f:id:kyuridenamida:20151109205255p:image

レセプション
  • 表彰式の後はレセプション．座る席が無いと困っていたら，筑波の先生がスタッフの人に掛けあってくれて，なんかワインとかがある良さそうな席に座らせてもらうことを許可される．
  • コーチの先生とかスポンサーとかが座る席だった．その先生が荷物見といてあげるから食べ物取っておいでとか言ってくれたりありがたい(バイキング形式なので)．
  • NCTUの人たちが現れ「今回のコンテスト問題の解法教えて～～」と言ってくる．ガバガバ英語で@__mathさんの解法を通訳する．というかあっちも賢いので大体図を描けば察してくれて，多分そっちの情報量の方がでかい．なお相手の言っていることは聞き取れない．
  • その後，相変わらずのタクシー事情の中スタッフの人が頑張ってタクシーを呼んでくれている間，しばし歓談する．
  • NCTUの人で日本語の授業結構取ってるみたいな人がいるらしく少し日本語で会話しようとしたけど咄嗟に出た僕の言葉が「初めまして(初めましてではない)」だったので人々にツッコまれ会話が即終了してしまった．
ホテルに戻る．
  • その後，タクシーが捕まったらしくて，スタッフの人に深く感謝しホテルに戻る．
  • 筑波の先生に夜どこか行きますか?って誘って頂いたのですが，疲れがドッと来たのでダウンしてしまい，断りの連絡を入れた．
  • 興奮冷め止まぬまま，部屋でダラダラし睡眠．

帰国日(11/8 日)

  • 朝8時分くらいにホテルを出てバス停に向かうスケジュールなので朝飯を食う．
  • 部屋に置いていた白いシャツがなくなっていることに気づく．どこかで紛失した可能性は考えにくいし，手違いで掃除されてしまったかなんだろうけれど，まあいいやって気分になる(本当はフロントで尋ねれば良かったんだけどややこしいかなと思った)．
  • とりあえずバス停に到着．8時30分くらい．
  • チケットをどうやって買うか悩む．窓口に行ったら英語が通じなくて慌てる．救世主が現れて通訳してくれる．本当にありがとうございました．
  • なんとか仁川国際空港に到着．ただ15時15分の便だけど11時台に着いたからだいぶ空港でだらだらする．
  • みやげ屋で韓国のりとか色々買う．
  • ロッテリアでプルコギバーガー食う．ここでも英語が通じなくて少しだけ苦労したけどさすがに指さしでなんとかなる．
  • いろいろしてるうちに飛行機乗る時間が来る．少し遅延してるらしいけど特に問題ない．
  • 5時30分くらいに関西空港到着．
  • 帰宅
  • 楽しかった……．食べ物めっちゃうまいのでまた旅行で行きたいですね．

TTPC 2015 参加記

お久しぶりです．JAG合宿→アメリカ(一週間)→TTPCオンサイト→帰宅というハードスケジュールで過ごしてました．

TTPC楽しかった．

前日

  • 人生初カプセルホテル．セキュリティに不安ニキ．

起床(09:30)

  • よすぽと10時にギロッポンで飯食う約束してたのに起きたの09:30．許して欲しい．

六本木ヒルズ到着(10:50)

  • よすぽ&TTPCwriterの人たちに会う．
  • 飯を食う．

飯食い終わって森タワーへ(11:10)

  • とりあえず当然ながら関係者以外は12時まで待っちくりと言われる．
  • 近くのスタバで50分時間を潰す
  • 時間を潰しているとみさわさんとかキャットアッパー・サタシュンが現れる

コンテスト開始前

  • だらだらする．
  • 後ろにとざん・横にsemiexp・前にrngさん(デデドン)

コンテスト開始(00:00)

  • FAを狙いたい気持ちでいっぱいだったからA,B,C,D(50点問題集)を開いて解けそうなやつを読む．
  • D読む．実装の軽いやるだけだ，絶対通すからな．素数判定ライブラリを保管しているローカルwikiがぶっ壊れているので泣きながら素数判定を書く．

D提出(1WA) (04:14)

  • いうて10^10とかほざいとるけどintでええやろｗ10^10規模のやつは多分素数になりえない(意味不明考察)
  • とりあえずろくにテストせずに出す．
  • 提出中にダメなことに気づいて急いで素数判定関数の引数をintに修正
  • いくつかWAする．

D再提出(2WA) (04:44)

  • 提出中にforの中身もintにしないとWAすることに気づく

D再々提出(AC) (05:26)

  • 絶対終わったと思ったけどこの問題から着手してる人がいなくて助かった．FAゲット．

Fを読む

  • 強い人がEから読むみたいなことを言っていた気がするのでFを読んだ
  • よくわからんけど少し紙に書いてみて考える．制約はどうみても桁dp．でもちょっとよくわからん．むずくない？
  • 筆算しながら決めていけばよくない？ｗってなるけど，筆算が下手くそすぎて失敗しまくる．
  • 慌てていたので繰り下がりがわからなかったりしまくる．なぜか繰り下がりが0~9の値をとっていて小学生からやり直したくなる．
  • とりあえず書く．
  • サンプル一発で合う．メモ化してなかったのでメモ化して提出．

F提出(1WA) (23:19)

  • 提出中にメモ化したのはいいけど，メモ化用の変数を-1初期化してなかったことに気づく．
  • ジャッジ終わる前に再提出

F再提出(AC) (23:34)

  • やったぜ．でもこれはさすがにFAではないよなあ...と思っていた
  • 順位表見たらFAだった．思わぬ収穫．
  • もうFAは諦める．順位表から得られる次に解くべき問題みたいなのはあんまり参考にならなかった．
  • いちおうざっと他の問題(100点以上)を眺めて，どれもパッと解け無さそうなので50点をやっつけることにする．
  • とりあえずA読む．さすがに書くだけ．

A提出(AC) (29:05)

  • テスト1だけ試して出したら通ったやったぜ
  • B読む．思考停止dpが楽かなと思ったけど，Bでそんなわけがないと思い数秒思考したら貪欲だということに気づいたので(しかもありがたい形で与えてくれてる)それで書く

B提出(AC) (32:30)

  • テスト1だけ試して出したら通ったやったぜ
  • Cを読む．規則性を見つけるために紙に書くorゴリゴリ書くのどちらかだと思ったけど，どうせそんなに実装辛くないでしょと思ったので書く
  • 10分くらいで書いて，これだけは不安なので全部テスト試す．なぜか全部通り逆に不安になる．

C提出(AC) (43:42)

  • なんで文字列系が一発で通るんだ．我ながら自画自賛したくなる．
  • E読む．O(n^3)でええかな？←ダメです．ハイ座圧...
  • ただ方針が2コ隙間があったら埋めるみたいな方法で最初書いてて，それよかは与えられる座標xに対し，x+1,x,x-1を全部試すほうが楽ということに気づき，書く．

E提出(AC) (58:33)

  • 意外とF解かれて無くて，正答数的にペースよくない？となる．
  • titech読む．以前に@kagamizと開催したCTPCの問題に似ているなあと思う．というか，それの一般化としてこういうものについて考えたことがあるなあと思う．
  • とりあえずtが2つだし少しアドホックな方法について考えた後，よい方法が思いつかなかったので思考停止状態遷移DPを書く．状態変数は多いけど状態数としては少ないことは知っていたのでmapにぶち込む．投げる．

G提出(AC) (75:00)

  • 結構調子が良い．
  • H読む．少し手元で試してみる．うーん解ける気がしない．あ，全部点を使わなくてもいいのか．それでも解ける気しないなあ．三角形・四角形になるのかな．それも嘘かなあ．通してる人いるしなあ．とりあえず放棄しJ読む．
  • Jの答えがOEISにあるわけがないので思考する．自己ループのケース数え上げているしなんかクッソ怪しいdpになる．自分の思考力に見切りをつけて実験フェーズにうつる．
  • 実験コードを書いてとりあえずOEISに投げる(何かしら弄ったらあるやろと思う)
  • とりあえずダメ元でn=8,k=1..8の値を入れてみたら，まさかの問題文そのままド直球数列が見つかり変な声が出る．mapleのコードぱっと見O(n^3)なんだけど，遅かったら改善しようと思う．
  • そのコードをC++に予想しながら直すと(mapleわからず)，となぜか各nについて，f(n,k)ではなくf(n,1)+f(n,2)+..f(n,k)が現れる．とりあえず差取ればええわという気持ちになり差を取って終了．
  • 3乗系のオーダーに見えるけど嬉しいことが起きて実行が速かった．そのままだそう．

J提出(RE,1WA) (121:26)

  • ランタイムエラーばっかやんなんで．n=1000,k=1000のケースは試したやん．
  • うわ配列外参照してる．なんでローカルこれで正しく動くんや．
  • 絶望しながら再提出

J提出(AC,1WA) (123:28)

  • やったぜ．またOEISに頼ってしまった...ダメですね．．．
  • H再び読む．いややっぱこれ3点or4点で十分で，適当な単純多角形考えても無駄な部分削れば4角形or3角形になることが分かる．頂点候補に原点はこないことが保証されているのでそれが言えそう．
  • O(n^4)だなあ...
  • 4点必要なのは線分上に原点がある場合のみ．対角線を固定してみたとき，異なる2点の四角形(面積最小)を使えば良い(少し嘘)
  • とりあえず書いてみる．サンプルが合う．

H提出(1WA) (145:56)

  • うーん10コくらいWA．なんでだろ．誤差かなあ．適当にlong doubleにしたり内外判定の関数を弄ったりeps弄ったりして出してみる

H提出(2WA,3WA) (152:38,156:32)

  • ダメだWA減らん．あ，"""三角形"""って面積が無いとだめじゃん．面積0を弾く．

H提出(4WA) (156:37)

  • 2コWA減った．他にコーナーケースあるかなあ．とりあえず誤差の部分弄って出してみよ

H提出(5WA) (163:20)

  • あっ，明らかに対角線分の左側と右側で三角形を作らなあかんやん．
  • 外積で左右判定するよううまく修正．

H提出(6WA,TLE) (170:23)

  • なんでTLEやねん....long doubleがどうせ原因なので提出．

H提出(AC,6WA) (172:12)

  • やったー．コーナーケース多いなと思ったけど，これ僕の頭が悪かっただけやない？
  • 麻雀(K)とかそーっとソート(I)とかグラフ色塗り(L)とかいろいろ考える．
  • 麻雀については，大きいほうから貪欲でよさそうということを考えたけどまとまらない
  • そーっとソートは良い戦略が思いつかない．
  • グラフ色塗りをたくさん解いている人がいるので，グラフ色塗りを考える．
  • わからないけどマトロイドで実は青い辺貪欲に追加して，毎回フローして確認したらいけるんちゃう？ｗ→明らかにいけないケースがすぐに作れます
  • でもそういうすぐに思いついたそういうケースは，青い辺ランダムシャッフルして大体うまくいくケース（多数の入辺と1本の出辺みたいなケース)．
  • ランダムシャッフルしてみよｗ20回くらい試行すればACするやろｗDinicが速く有りますように．
  • テストケースの数が多くありませんように...ありませんように
  • 25コだけｷﾀ─ｗﾍ√ﾚｖ～(ﾟ∀ﾟ)─ｗﾍ√ﾚｖ～─!!!!

L(AC) (217:47)

  • はいACやったぜ
  • Iを再び読み考える．良い戦略思いつかん．悩む．
  • とりあえず遷移できない状態がないことを確かめたいので実験する．たしかに存在しないことが分かる．
  • よって順列の中で一番でかい数を後ろに持っていけば，後はその数を使わず先頭の部分順列で繰り返せることが帰納的に分かる．
  • 後ろに来させる方法を考えていたら，乱択して後ろに来るまで待てばいいことに気づく．
  • 10万回以下だし通るやろと思い書く．

I(AC) (255:14)

  • ウオマジか．乱択2連続やんやん．
  • K読む．再び貪欲を考えると，でかい人から，まだ未確定の試合数を算出し，過去の人が現在以降の人に過去の試合で負けたことがわかっているので，その負けの数とかを考慮しながら貪欲するといいことが分かる．
  • 紙に書いてまとめる．投げる．

K(AC) (270:15)

  • ウェイソイヤ．こんなんでええんか！？ていうかサンプル弱すぎてこわかったけどええんかこれでホンマに．
  • コンテスト終了30分．牛っぽいNと通してる人が多いMがある．牛は苦手だからMを考察することにする．ゲームは苦手だけど調子がいいからいける！
  • コインが全部頂点0にある状態から考えてみると，nimすればよさそう．どうやればいいかはわからないけど，繋がってる辺に対してnimすればいいでしょｗ←（嘘っぽさ満載）
  • とりあえず実装して投げる．

M(1WA) (291:49)

  • 71コ中5コWAする．部分点も部分点データセット中2WAしてて取れない．ダメ．証明抜きだから多分嘘っぽい．為す術なし
  • その後適当にいじったサブミットを2回するも撃沈．

成績

  • I～Lまでのお行儀の良い12完で1250点，15位でした．250点問題がぜんぜん解けなかったので悔しいです．100点問題をもっと配点上げてくれ．

感想

  • 今回は久しぶりにかなり調子が良かった．ちゃんと考えるようにしたからかもしれない．FAのためにいろいろ犠牲にはしたけど．
  • こういうたくさんACがもらえるとても楽しかった，上位陣はおかしいなと思った．
  • 来年も開催して欲しいです．
  • 解説があのひどい名前でFA取ったことになってたの結構すき．yosupoごめん．

Cocos2d 空プロジェクト生成失敗[Errno 13]

問題

cocos.pyで空プロジェクト(empty project)生成するの，「cocos new MyGame -p testpackage.package -l cpp -d hogedir」でやるとCygwinでなんかうまくいかない．

作ったslnファイルクリックしても，「有効な Visual Studio ソリューションではありません。 」って言われちゃう．

ていうか，そもそも生成のときに，

> Copy template into /kyuridenamida/hogedir/MyGame

> Copying cocos2d-x files...

> Rename project name from 'HelloCpp' to 'MyGame'

> Replace the project name from 'HelloCpp' to 'MyGame'

[Errno 13] Permission denied: u'/kyuridenamida/hogedir/MyGame/proj.win32/MyGame.vcxproj'

みたいに怒られてプロジェクトのコピーに失敗する．

解決方法

cygwinを管理者権限で実行するとプロジェクトのコピーには成功する．でもやっぱりslnファイル見れない．

そこでhogedir以下のファイル・ディレクトリにすべてchmodで権限を付加してやる．つまり，

「chmod +rwx hogedir -R」

を実行するとよい．割とバッドノウハウかも．そもそもcygwinでやるなという話だと思った（？）．

ICPC 2015 日本国内予選

チームchikOkU(@__math,(M2),@ustimaw(M2),@kyuridenamida(B3)の3人)で出てました．

戦犯は大体僕です．

全体9位で通過はしましたが，チームに迷惑をかけてしまって，かなり落ち込んだ予選でした．

--

--

これかなり本心です．実際，3完だとうちから出てる他のチームに負ける可能性が高かった．

あんまり詳細覚えてないので，流れだけ書きます．

コンテスト開始前
  • うちからは4チームいて，同じ部屋で受験する感じでワイワイ．
  • USBポートが足りなくて，USBハブが欲しくなって生協に買いに行くか...と思っていたら，別チームのきひろちゃんがHHKB使わないから貸してあげると言って貸してくれ，HHKBが高級USBハブになった(※)．

(※HHKBにはUSBポートが2つあるので，つまり1つだけポートを増やせます．)

コンテスト開始(0分)
  • ネットに繋がる．
  • プリンタで問題文印刷するものの，他の2チームだけはうまく印刷できて，僕ら含めた2チームでキューがつまってうまく印刷できない．
  • その間にまーすさんにAを解いてもらう．
A AC(5~6分)
  • 多分4位くらいでFAとるぞ～と意気込んでいたまーすさんが落ち込んでた．
  • ようやくプリントできたと思ったら，なぜか裏表印刷してしまった．3部は印刷できてないので引き続き印刷したくなる．
  • 仕方ないのでBをまーすさんに解いてもらう．
  • 印刷待ってる間にCを少し読んではあはあなるほどとなる．
B AC (10分ちょい?)
  • はやい．でも問題文はまだ完全には印刷できてない．
  • C書き始めるけど，慌ててて少し細かい遷移条件がうまく思いつかない．再帰でLL(1)のときのように適当にやればいいのは分かるのだけれど．
  • まあとりあえず冷静に脳内でサンプルを動かしてみて動きそうな方法を書く．
C かき上げる(35分くらい?)
  • かなり手こずったし，少しだけバグった(オペレータを'*'だけしか受け付けてなかった)けど，まーすさんの指摘でサンプルが通る．
  • データセットを落としてきて，ちゃんと構文解析完了してるかassertで確認しようみたいな気分になり，assert入れたらassertバグる．
  • 焦って5分ほど時間吸われたけど，assert入れるときに変なキー押して構文解析パート実行するコードが消えてたのが原因らしい．修正．
C AC (40分前後?)
  • 順位は悪くはない．
  • とりあえず，ustimawさんにDを書いてもらう．
  • その間にまーすさんとEについて話したりする．しかし，trie木にすると性質がよくなる...等言っていたけど，そもそもうまくデッドロックが発生するイメージをただちに想像できなかったので，「ごめんなさい」する．
  • とりあえずグラフであるFを考える．2日前にちょうどマトロイドを扱う試験があったのもあって貪欲か～？となる．
  • この国内予選，難しすぎるという話をする．
Fかんがえる
  • 辺の小さい順に「残りの辺でグラフを連結にできる」なら追加する貪欲を考える．でも，辺集合からk本のA辺とn-k-1本のB辺を使って連結にできるというやつの判定方法が全く思いつかない．つらい気持ちになる．
  • その間に，ustimawさんがDにハマっていた．
D バトンタッチ (1時間10分くらい?)
  • ハマっているのはやばそうということで，まーすさんと議論して，方針をustimawさんのものと照らしあわせて，少し違ったので僕にバトンタッチしてもらう．
  • 僕の方針，たしかにあっていたのだけど，僕だけ計算量の見積もりを""""一切""""していなかったので，メンバーの忠告を無視してなぜかmapモリモリ使ったダイクストラで書き上げる．バグをいくつか潰してサンプルが合ってさあ提出するぞ～となったらテストケースの実行が終わらない，死．
  • そもそもダイクストラになぜかコスト含んだ状態もたせてた．修正→終わらない・・・死
  • その後適当な改善をしようとするが，クソコードすぎてもうだめ．
D 僕まではまる Ω＼ζ°)ﾁｰﾝ (2時間くらい)
  • 3完やぞオイ予選落ちするかも...
  • メモ化再帰で書き上げたと思ったらDPの形をしてなくて実行結果がバグる．
  • 頭がついてないと言われても仕方ない感じになった．
  • 仕方なくまーすさんが一から書き直してるときに，あとすこしで完成しそうというところで僕のメモ化再帰のコードを修正させてもらう．
  • とりあえず強引に『余ったお金の総額=min(余ったお金の総額,a)』みたいなaを弄るコードを書いて，答えが変化しなくなったら出す感じのコードで怪しいが出させてもらう．a=15000くらい．
D 1つ目のデータセットAC (2時間半くらい)
  • おもいっくそよっしゃああと手を叩くけど，メンバーに冷静に「まだ1つしか通ってないからな」と言われ，冷静になる．
  • 2個目の実行をしているときに，a=15000なのに関わらず，配列を15001でなく10001で取っていることに気づいて心臓が止まりそうになる．
  • でもまあもう仕方ないし実行に成功してしまったので2つ目のデータセットのやつも出す．
D AC (2時間半くらい)
  • なぜ通ったのか当時全く分からなったけどワイワイってなる．神のご加護を感じた．
  • 冷静に考えると1万以上無駄なお金を手に入れる遷移が無かっただけなのかも．
  • まーすが解法を詰めていたというEを書いてもらう
  • その間にFの考察をustimawさんと二人でする．
E 書き上げ (2時間45分くらい)
  • はやすぎでしょびびる
  • まーす「最悪計算量膨れ上がりそうで怖いんだよなあ....実行間に合うといいんだけど」
  • 一瞬で実行が終わる．
  • 提出
E AC (2時間47分くらい)
  • すげえ5完．まーすの力じゃん．
  • とりあえず間に合わ無さそうだけど，Fの嘘方針っぽい怪しい貪欲コードを書く．
  • 当然間に合わずオシマイ．
コンテスト終了 (3時間)
  • うちは9位で通過．賞がほしいからあと1位下がって欲しい気持ちでいっぱいだった．
  • Ishibashi DとEで詰まっていたみたいで悔しくも3完でアジアならずだった．うーむ残念．
  • 他のチームは2完と3完だった．同級生(と英語サークルの先輩?)に即席で組ませたチームが3完しているのはすごい！と思った．2完のチームのメンバーの人も来年は行くぞアジア地区みたいになっていてほしい．
反省
  • 【チームの力】÷【個人の実力の最大値】＞ 1.0 になっていれば良いんですが，多分0.75くらいにしかなってないのでかなり反省しています．
  • Hを読むのを放棄してしまったのは完全に失敗だったぽく，JOI春合宿の問題文は全部読みましょうの再来になってしまった．
  • アジアがんばります．

標準入力(stdin)を文字列(string)にすり替える方法

こういうのがよかったです．

rewindはプログラム内で複数回こんなかんじのパイプ処理をするときにしないといけないと思います．

stdinが使えなくなっちゃうんでその対策は考えといてください．

#include <bits/stdc++.h>
#include <unistd.h>
#include "testlib.h"

int main(){
	//パイプ生成
	int pipefd[2];
	if (pipe(pipefd) < 0) {
		perror("pipe");
		exit(-1);
	}
	// パイプへの書き込み
	const char *content = "1 2 3 4\n";
	write(pipefd[1], content, strlen(content));
	close(pipefd[1]); // これでEOFをきちんと示す

	// パイプをSTDINのディスクリプタ番号に結びつけ
	dup2(pipefd[0],STDIN_FILENO); 
	//stdinのファイル指示子とかいろいろ初期化
	rewind(stdin); 
	
	// 実際の処理 EOFまで読み込む
	int tmp;
	while( std::cin >> tmp ) std::cout << tmp << std::endl;

	close(pipefd[0]);
}

立命館合宿2日目

集合

evimaさんに明日組もうって言ってたんだけど，なぜか行きでmathさんが現れ(彼は立命館合宿に元々登録していなかったのに!)，あまりのチャンスに浮気してしまった．申し訳なかった．

チーム名はWaldReisfeld(ドイツ語で森田)でした．

コンテスト開始前

ということで

チームメイト: まーすさんとよすぽ

コンテスト開始 きゅうり A

最初，僕がなぜか時間をかけ血を吐きながらAを12分で解く．遅いけどWAしなかったし初動はまずまず．

まーすさん B

その間まーすさんがBを読んでたので書いて通そうとする....がREする．

なんでだろって思ったら，よすぽがfor(int i = 0 ; i < array.size()-2 ; i++) みたいなのはオーバーフローするからNGと一瞬で見抜き，1分後にAC．神かよ．

どうやら常日頃マクロ使ってる人はちゃんと勝手にキャストされるからそういうのに意識が及ばないらしい．

きゅうり C

次にB読んでる間によすぽと議論してぜってーダイクストラやるだけみたいなことを言ってたCを書く．定数倍無駄に意識してゆっくり書く．でっかいケースが通りそうなことを確認し13分後にAC．

35分経過

3完，割とリズムはよい．

よすぽE

よすぽにバトンタッチ，キーボードがつらぽよいと言っていたが，データ構造のEを解いて頂く．

25分後に第一提出，MLEが発生．MLE誤魔化すために絶対map使おうな→今度はうまくいったけどRE(スタックオーバーフロー)．

Trie木への挿入とかを非再帰で書いてRE回避→今度は圧倒的TLE．はっきり言って地獄．

なんでだーーーーと結構悩む．悩んでる間にまーすさんに考察進めてたゲームのIを書いてもらう．

議論の結果，Eは制約を誤読していてその解法そもそも圧倒的TLEするということがわかり，よすぽが絶望，立て直しして頂く．

まーす I

まーすさんが書いたIがWA．まーすさんが問題文を読みなおしたところ読み落としがあることが判明，方針を練りなおしてもらう．

きゅうり D　アンド　よすぽEの続き

よすぽが実装しつつ，パソコンが空いた時間で僕は実装するだけのD問題(カレンダー系)をちまちま書く．

そして，なぜか曜日関数がバグったのでわーってなったら，よすぽが一瞬で，西暦0年のケースで負の割り算を床関数に放り込むからやばいと見抜き，神かよとなる．

「西暦1年から周期計算するとややめんどくなるのでは」となったので少し紙上で整理する．その間によすぽがEの新しい方針を書く．

とりあえず整理したので書く→サンプル合う→出す→Dが通る．最高．

3完→5完

ここで1時間48分4完，一気にリズムが悪くなったな？と思っていたら，3分後によすぽが書いていたEが完成し提出したらAC．一気にチームがホットに．5完．

Iの考察

Iについて，よすぽが適当なことを言ったらまーすさんがそれを誤解して受けとり，そのおかげで正しい方針が見えるというハプニングが起きてたりする．

Iをまーすさんが実験したり実装を考えつつ，「Theやるだけ」のHを書かせてもらう．ザコなので意外と時間がかかる．

結局その1時間何してたかは思い出せないけど，Fとか考えてたのかなみんな．結局わからなかったぽい．

きゅうり H

3時間経過くらいでHを提出→WA．絶望．

よすぽと題意の確認と実装を指指し確認，自明にしてはいけないことをしていることがよすぽの指摘によって分かり提出→ACアツい(WA後，15分くらいで解決)．

まーす I

その16分後になんとmathさんがIをAC．7完(3時間半)．

そこからどうしたか

んー，あと残り4問で，全部誰も解いていない．

何を解けるかなあと考えていたんだけどFは誰も解いてないしやばい，Jは思いつかないのでやばい．

Kはよすぽと僕もいろいろ話していたけど，よくわからなくウーン．

Gは明らかに方針は立つが激重だし通す自信がないという感じ．

ということで，結局僕がGを書き，その間によすぽとまーすさんがKを考察することに．

きゅうり G

僕がGのコードを必死に書く．線分と多角形の内外判定とかだるいなーと思いながら頑張って直線を分割したりして内点見たりして書く．70分かけて書き上げる．残り17分．必死な怪しいコードがサンプル通る．

出す→WA Ω＼ζ°)ﾁｰﾝ

EPS変えて出す→同じケースでWAΩ＼ζ°)ﾁｰﾝ

EPS変えて出す→同じケースでWAΩ＼ζ°)ﾁｰﾝ

とりあえず解法を口に出して他人に説明してたら，多角形の頂点間同士の移動をうっかり書き忘れてることに気づく（アアアッ）

出す→TL:1sのところ1.4sで少しだけTLE，実装の簡易化のために，だいぶ定数倍重いコードを書いたので(移動距離に対称性があるのにいちいちちゃんと計算していたり)，一番楽そうな部分を書き換えてとりあえず出す

通った直後

0.7秒くらいで通る!!!!!!!!!!!!!!!!!!!!!!!!!!!(残り8分くらい)

8完！！！！！！！！！！もう時代が追いついててサイコーってなる．

まーす&よすぽ K

喜びも束の間，どうやらKはもう場合分けが済んで，後は書くだけというフェーズらしいので急いで書いてもらう．

オマケパートにTSPがあったんだけど，TSPのDP自体はグラフが構築されてれば1分で書く自信があったのでそれを待ち構えていた．

でも場合分けが重すぎて8分では写しきれるものではなかったらしく，あえなくコンテストが終わり．

とりあえず悔しいので終わった直後くらいに出したらテストケース10番目くらいでWAする．

その後によすぽがとある自明なコーナーケース(と彼は言っている)に対応させたら通ったと言っていてすごい．

ただ本番では通せなくて悔しかったという感じ．

結果&感想

コンテスト終わった後けっこう経った後に順位表見たら単独8完1位でワーイって気分になる．

正直，9完も目前だったし組んでから思ったけどかなりパワフルなチームだった．組ませて頂いてありがとうございます．

一人だったら絶対5完以下な気がする．

僕とまーすさんが解きつつ，よすぽが神助言とかしてた．

誰にも解かれてないF,Jは相変わらずムズそうだった．Jはなんか解説見て狐につままれた気分で「あっそっかぁ・・・」ってなった．

K解いたしゃっふりゅーさんアツすぎでしょ．絶対国際情オリ代表になってくれ．

懇親会

その後，立命館合宿のスポンサーのリクルートのトイレ5コさんがきていてindeedについて説明してくれる．

懇親会では何人かと話す．高専生(若い人とかも!)いてびっくり．楽しかったです．

トイレ5コさんにアイコンごめんなさいしたりした．

アクション南草津？とかいうゲームセンターにevimaさんとyosupoと行ったりする．よすぽの動画撮れてよかった（小並感）．