JOI'17-18 本選参加記
今日も一日かんばるJOI!
問題のネタバレを微妙に含みます。(特に5)
Day1 practice
飛行機にのって、バスに乗っていった。
バスに乗っている人を探したら蚪蝌さんからリプが来て、一生懸命に蟻本を掲げたが、ダメだった。(出発地が違っていたことが判明)
バスのほかの人にはさぞかし奇妙に見えただろう。
バスから降りた後、昼食に海鮮丼を食べた。おいしかったけど、ワサビが多かった。
会場について、早く受付をした。今度こそ蚪蝌さんと遭遇した。
その後もたくさんのプロがあつまって、実質オフ会0120人になった。
双子が到着した。本当によく似ていた。
みんなで動植物タワーバトルをした。(このあともたくさんした)
荷物置き場がロビーよりも人が集まる。
practice
環境の確認をする。全完。 双子が一瞬で全完していて、さらにE869120さんは片手でマスコットを挙げたまま、もう一方の手でタイプする という謎行動をしていた。プロ。 すぐに全完勢が集まって、いろいろ話していた。動物タワーバトル再び(さっきの画像)
シスコの人たちの講演
双子の間に座った。双子つよい。たくさん話した。
夕食会
DEGwerさんとmaroon_kuriさんなどに作問のコツを聞いた。ぼくもARCでwriterをしたいな~(深刻なレート不足) 自己紹介フェーズで双子にあおられた。こっちも負けずにあおり返した。
ホテル(独房)
ロビーでみんプロ予選オンサイトが発生した。 双子は3完して、すぐにお風呂に入ったが、 僕は最後まで粘った。結局E問題は解けなかった。 順位表をみると、みんプロ予選通過っぽい。やったぜ。 順位表で双子に挟まれた。 そのあと、platypusさんにC問題の解説などをして、寝た。
起床フェーズ
上の階の目覚ましの音で起床した。 僕の目覚ましは、「平日のみ」の設定なので、鳴らなかった。上の階の人に「圧倒的感謝」
朝食
朝花粉症の薬を飲むのが早すぎて、少し吐き気がした。緊張のせいかもしれない。 ゆっくり食べることで何とかなったけど、体調管理WA
本選開始
09:07:44 1問目 ストーブAC!!
09:16:24 2問目 博覧会AC!!ソート多くない?
3問目 お団子メーカー ほかのと重なってない方から貪欲に取ろうとする
09:50:56 実装が複雑すぎる。ここで唐突に(ネタバレ防止)を思いつく。切り替える(34分ロス)
10:13:50 それを実装したが、微妙にバグらせてWA デバッグする
10:53:18 いろいろデバッグして、やっとAC!!!97分かかった。
11:39:11 4問目 定期券の購入AC!!!3問目と難易度が逆に思える。44分で解けた。
5問目 ここで蛇の脱走の解法を考えるが、解けない。
12:25:33 とりあえず22点の部分点3までを獲得。12まではやるだけ。おすすめ部分点。22も行ける。3や4の部分よりもおいしい。
部分点4(5+7+10+53=75点の解法)がわからない。
はてなが12個あるもののうちの一部について求めておく解法か?実装難しいうえ、クエリあたり5000回ぐらい計算がいるのでう～ん...
想定解がこれだったら定数倍のくそ問という気持ちになった。(解けないとdisる悪い癖)
本選終了!
まず双子に得点を聞いた。square1001さんが412点、E869120さんが430点で金賞。またもや双子に挟まれる。 E869120さんは4問目を55点のかわりに、5問目を75点で解いていた。ガチプロ曰く、「55+75>100+22なので、4を適当にして、5に集中した」らしい。 (でも僕は4問目はへたに部分点1~3場合分けするより、一気に満点とった方が早いと思った)(実際同じぐらいの時間)
結論:E869120さんはプロ!!
squareさん、Kmcodeさんも実は小課題4の実装途中だったらしい。もしかして5問目小課題4の解法わかってないのぼくだけ??
解説
またまた双子の間に座った。実質三つ子(は?) 1~4 なるほどなあ(ネタバレ防止🎩) 5 DEGwerさん「ここで包除定理を使います」
それは天才!!!!!!!
あっけにとられた。なるほど。大好き。さすがレッドコーダー。プロ。すごい。...
JOI終了
たくさんの競プロerとつくばエキスプレスで帰った。
つかれた。
速く空港につきすぎたら、飛行機を無料で1便早めることができたのでそうした。ありがとう。 帰ったらすごく雪が積もっていた。一便遅かったら帰れなかったかも...
結論
とても楽しかった。去年と違っていろんな人を知っているので本当に楽しかった。 今twitterとAtCoderを始めてない高校1年生までの競プロerは、この機会に始めてください。よろしくお願いします。 本当に楽しかったので、来年もまた出たい。（高２なのでア） そういえば、2/14~学校の定期試験だ...勉強してない..いまもしてない...
次回予告(ポプテピピックのネタです)
やっほー!WA_TLEだよ!!!🐣
銀賞はぼくだけのものなんだから!!!(いいえ)(たくさん存在した)(たぶん3人)
JOIのことばっかり考えてたら、全科目☀0完太陽☀とっちゃった!
べつに、勉強教えてくれたってうれしくないんだから!!!(教えてもらってもしないので)(課題を代わりにやってくださいお願いします)
太陽色WA_TLEドロップアウト
「WA_TLEの単位炎上中!」
来年も、単位ドロップドロップ!!
北大日立新概念コンテスト1stの僕の解法
北大日立コン1st,最終systest736571点,29位でした。以下、かいせつです。 僕の最終方針は、9秒間ビームサーチして、最後の1秒焼きなます方法です。 盤面に点を順番におくのをビームサーチして、最後の方は置く選択肢が少なくなってあまりよくない感じなので、焼きなましで仕上げを行った。 ビームサーチで置いた後、余った点を焼きなましで配置するということです。
11/15 17:07 145320点 貪欲に上から置いていった。ただし、GVの正方形をVぐらいのサイズの正方形の形に収めるようにした。(例えばGV=36,V=5のとき、
1,2,3,4,5,6
7
ではなく
1,2,3
4,5,6
7
にした。(これはビームサーチするときもこのようにおいてます)
11/15 18:08 149919点 焼きなまし法である点と点の交換を行ったが、焼きなまし温度をバグらせていて、温度が上昇してしまっていた。
11/16 17:06 141447点 貪欲をビームサーチにした。
11/16 18:11 154956点 焼きなまし法の温度管理のバグに気が付いた。(実はこのころはビームサーチの回数が固定なため、実質焼きなまし法onlyの点数) やらかし 実質焼きなまし法のスコアなのに、ビーム+焼きなましの成果だと誤認。焼きなましはパラメーター調整しかないと思っていたので、ビームサーチの改良に進んでしまった。
11/17 16:23 158173点 ビームサーチの時間を管理して、しっかり8秒まわすようにした。やっぱりビームサーチ最強!!(いいえ) このころのプログラムをビジュアライズすると、ビームサーチから焼きなましするときに、点は全部変わることにはなってなかったので、作戦通りにいっていた。
11/19 20:11 158978点 ビームサーチの手をソートするのがボトルネックだったため、高速化した。ついでに時間を9.8秒にした。頂点を置く順番を
01,02,03,04,29,30,31
05,06,07,08,32,33,34
09,10,11,12,35,36,37
13,14,15,16,38,39,40
17,18,19,20,41,42
21,22,23,24
25,26,27,28
のように,4個ずつおいた。
さらに、直前に置いた5個が全く同じ盤面は、重複として除去した。
11/20 テストケース生成器を適当に眺めていたら、辺のrandがおかしいことに気が付いて、質問を投げた。 辺の偏りは、焼きなましなら問題はないが、ビームサーチなら重要なことだ。序盤の方にたくさん辺を持つ点が選ばれて、後半はゴミみたいな点が集まるのは、あまりよくないことだからだ。
11/20 17:25 154934 点 たくさん辺を持つ頂点ばかりが最初に選ばれないように、そういう点をたくさん含む盤面の評価値をさげた。 ある頂点について、そこから伸びている辺の重みの合計をもとめておいて、それの合計*ペナルティ定数だけ評価値をさげた。 しかし、肝心のペナルティ係数の決め方がうまくいかなかった。(動的に変更しようとしていた)(現在の使っている頂点の辺の重みの合計と、平均の辺の重みの合計を比較して、あれこれしていたが、頂点を端の方から決めるために、それではダメだった)
1週間ぐらい、マラソンに飽きていた。
最終日 ??????点(pretestの点数が残ってない)
結局ペナルティ係数を動的にするのはあきらめて、ExcelでVとE/Vのいろいろな値に対して実験して決めた。
systest 736571点,29位で終了した。
考察メモ落書きです。
PCK 参加記
参加記です。問題のネタバレを含みます。
day0
飛行機->新幹線->電車 それぞれにかかる時間が大体同じだった。
区間を移動する方法がセグ木っぽくないですか？ないですね。
会津は寒くなかった。
相方が財布を電車に忘れた。(後で戻ってきた。大変だった)
スプラのアプデ予告の情報ではしゃいだ。
ラーメンを食べた。
day1
|会|津|大|学|にバスで行った。
Noyashiの紹介文がとても面白かった。
始まる前に大学で任意のプロとたくさんはなした。
コンテスト開始
問0
ログインIDのOと0を間違えて5分とかした。
問1
相方が解いたが、かっこの対応が間違っていた。
コンパイラがいつもと違うので、cinが定義されてませんと意味不明なことを言い出して、20分ぐらいとかした。
違うファイルに上書き保存とかいうミスも。
何とかACしたが、上位陣はすでに3ACぐらいしている。
もう問1,2,3,4,6を解いたチームもいて、まだ1完なので、引率の先生はかなり心配していたかも？
しかし、この間に僕は考察を進めていて、実はたいした問題になってない。
はい。考察完了です。
考察に20分ぐらいかかりました。
配点/実装時間が高い順に解きました。
問9 配点/実装時間 が最大なので、解きます。
submit! -> CE
最後の}をコピーし忘れ😢😢😢
CEのペナルティがでかいので、これは痛い！
再submit!AC!
解く順番が奇抜なので、ツイッターに載りました。(非想定)
問4 解きました。
問6 解きました。実装は簡単です。
問7 疲れからか、不幸にも問題に0が含まれないのを忘れて、9999->10002みたいなのを考慮してしまう。
そのまま組むも、コードが複雑化
ワアーーーーーーーッッッ！(WA)
ちょっと変える。
結局複雑なままAC。
問2 相方が実装した。
int n; double t,w,h; cin>>n>>t>>w>>h; double ans=h/w; for(int i=1;i<n;i++){ cin>>w>>h; if(w/h>ans){ans=w/h;} } cout<<setpresicion(20)<<ans*t<<endl;
i=1;i<n;i++で一瞬バグってるように見える(実際には最初に1回分回っていて、あっている)
バグっているように見えたので、i=0,i<n,i++に書き直した。ロス。
問3 相方もわかっていたっぽかったが、時間がないので僕が実装した。(もう考察ないし) やるだけ。
問5 やるだけ。O(14401440n)の方で解いた。
問10 問題読めた。二重連結やるだけ
えーと...ライブラリは...
蟻本...に載ってない！！！！
ライブラリ...ない！！！！！！！！！
うえーん😢😢😢
lowlink思い出せず、無事死亡
問8 僕が解ける可能性はこれだけ
順位表凍結 C++Castle(1WA)が1問でも解いたら負け
問9,10が(C++Castleにとっては)簡単(に思えた)だけに、僕のこれまでのやらかしが頭をよぎる(特に問9のWA)
線分の交差判定が難しい！
手が震えて、実装に集中できない!
コンテスト終了。結局問8は解けなかった。
終わってすぐカモノハシさんに何完か聞いた。7完だったらしい。どうか？2位行けたか?
風船を持ち帰った。🎈🎈🎈
交流会
yutakaプロと話した。†Absolute Winner†の†オーラ†が出ていた。
8完2WAより良いチームはyutakaプロ以外いなかった模様。
ほかにもいろいろな人と話した。カモノハシさんとかNoyashiさんとか。
ごはんがおいしかった。
その後
カモノハシさんの部屋に行った。風船をたくさんつけたらマスコットが浮いた。実質うく(いいえ)
そのあと会津大学の人がホテルにきて、みんなで大富豪をした。
2日目
朝が早い！先生からの電話で目覚めた
またカモノハシさんと話していたら、ヅ大バスの時間がヤバだった。
モバイル部門を見た。
テーマが「友と学ぶ」だったので、同じようなものがたくさんあった。それはそう。
本選問題解説を見た。
beetさんやうくさんと話した。
表彰式
予想通り2位だった。
カモノハシプロが4位だったけど、コードがきれいの賞をもらっていた。答えとなる変数名はbigだったらしい。
賞品を無限にもらった。
終わった後の抽選会でさらにクッキーをもらった。やったぜ！
ホテルのwi-fiがクソオブクソなので、ARC不参加。
後泊
朝起きて、帰った。
荷物&賞品が無限に重かった。
感想。楽しかった。
SuperCon2017
優勝した！楽しかった！
問題説明
音楽の生データが与えられる。
0と1に圧縮する。
なんか平均をとる。
元のデータも平均をとる。
誤差が小さいと勝ち！
詳しくはSuperConのホームページに載ってます。
1日目
・問題を見た。大体の方針（ベクトル化焼きなまし法）を立てた。
・実装をした。貪欲にやる部分は相方にまかせた。
・最大値を決定するために3分探索を組んだ。
・それを焼きなますコードを書いた。
・gnuplotで方針あってそうなのを確認した。（gnuplotとは、みんなに配布される、グラフをプロットするアプリで、excelの折れ線グラフを早く書くみたいなものだと思ってください。）
・時間は20時までと決まっていたが、周りは20時になる前に帰っていた。
・僕たちが20時に帰って、夕食をとるためにホテル近くの空港に向かったところ、大体のレストランが閉まっていた。しまった。結局そばと丼を食べた
2日目
・1日目にやったことのベクトル化をしようとした。
・そしたら内側の小さな11回のループの方がベクトル化されてしまって早くならなかった。
・仕方がないので†人力ループ展開†をした。
・これは初日だったかもしれませんが、supercon主催の先生が僕の本気のと同じぐらい良い値を「何もしないで」出せると全体に対する掲示板に書いていて、非常にビビった。（結局先生は1桁間違えていたのだが。
・でも、gnuplotでプロットしても、10倍もいい値を出せるとはとても思えないので、大いに困惑した。
・このあたりからいろんなパラメータの調整が始まった。
3日目
・焼きなましのバグを発見、修正した。誤差が2/3ぐらいによくなった。
・パラメータの調整をエクセル使ってひたすらやった。
・いろんな謎ヒューリスティックスを入れたらよくなった。
4日目
・焼きなまし法の乱数を思ったよりも大きくしたらすごく（10%ぐらい)値が良くなった。
・競技が終了した。
・他チームといろいろ話した。(これは0bitの情報です)
最終日
・なんか優勝した。びっくりした。
おわり
