お久しぶりです．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ごめん．
