TTPC2019参加記
前日
りあんさんとおぎんぎんさんとシナモロールと4人で麻雀を打ちました
— こるとん (@kyort0n) 2019年8月30日
もう一回張ったけどダメだった pic.twitter.com/yuB1FZoAmK
— こるとん (@kyort0n) 2019年8月30日
犯罪をしました
当日
会場に着き、運営からのチーム説明や会場使用上の注意等を聞いていると、チームメイトのシナモロールからDMが飛んできました
ご丁寧にチームアカウントが作成されていました。
シナモロールがやりました #ttpc2019 pic.twitter.com/N5gnuQmKZX
— こるとん (@kyort0n) 2019年8月31日
「アイコンに丁度良い画像無い?」と言われました。ねえよ。
うんち屋さんってなんだよ (当然の疑問)
— えでゅふぉを埋める (@homuhomucomp) 2019年8月31日
コンテスト開始
実は前日の麻雀の際に軽く相談をして、「シナモロールが前半の問題を通し、その間にkort0nが後ろで簡単なものを探しておく」作戦を取るという話になっていました
しかし小学生2人組はこのチーム名を解説スライドに載せたくなってしまった為、
こ「FA取りたくね?」
シ「分かる BかCあたりでFA狙おう FA狙いで最初の1問だけ実装して」
こ「ok」
となりました。
開幕Bを開きます
これは開始地点を2重に回して、それぞれの部分文字列がokyo,echであるか調べればok!FAは貰った!
サンプル実行!
Segmentation fault (core dumped)
終
制作・著作
━━━━━
ⓃⒽⓀ
結局元の作戦に戻って、G以降を読むことにしました
G:これは出来そう ただ細かいところ詰めないといけないからすぐにやるべきではない
H:絶対データ構造ゲーだ...
I:ノーチャンではないかもしれないが、他の問題やってからでいい
J:うーん出来そう(しかしこのとき何となく考えていた解法は完全に嘘)
K:はいヤバ枠(←は?)
L:もう開かん
M:苦手分野 多分ヤバ問題ではないと思うのでシナモロールに投げたい
N:要はユーリ君が整数を選べるということが大事っぽい 出来るのでは?(←は?)
ここまで読んだところで、Dまで通したシナモロールにEの構築を投げられる 30分くらい?掛けて通す
後ろの方の問題が全体的に難しめだし、前半6問は簡単枠とは言えEFあたりは骨のある問題だろうし、とりあえず2人でFを通そうという話になる
Fを読む これじゃんとなる
実はコドフォで3日前にグループバチャをした問題に、かなり似ている問題がありました これは無向グラフで、V, E<=3000の問題
この問題の想定解は「合流地点と離れる地点を探索O(V^2)」だったのに、今日のFはほぼ同じ問題設定でV<=1e5になっている これはどういうことだ...
2人で分からん分からんと言い合う 有向グラフであることを使う?でも有向グラフであることが良い性質を持っているとは思えないぞ?
Fで詰まって数十分後、おもむろに制約を再確認したシナモロールが気付く
DAGやんけ!!!!!!!!!!!!!!!!!!!!!!!
頭を抱える DAGなら流石に出来そう
考える
出来ません
数十分掛けてようやくまともなdp解法が生える
実装して投げる WA
泥沼感が出てきたので、6完で終わることは無いだろうし後ろに手を付けようという話になる
順位表を見るとOが沢山通っているのでOをやろうと言われる Oって何だっけ?そういえばOだけ読んでないな
Oを読む これじゃんとなる
幅がギリギリだったので無理やり分岐路を詰め込んで、マジックナンバーをコードに埋め込みつつ無理やり通す
そういえばOの実装はこうやりました
— こるとん (@kyort0n) 2019年9月1日
形が汚いので何となく分かると思いますが、実装が酷いですね...#ttpc2019 pic.twitter.com/o0yCfb31WN
次は、自分がGを考え、シナモロールがFを考えるという話になる
GがO(N^2)から落ちねーと唸っていると、シナモロールに「違う文字に変更するペアの数で全探索をすると、各答えが綺麗に累積和の形になる」と言われて、確かにと答える 実装すると通る
流石にそろそろFから目を背ける訳には行かなくなってくる
考えていると、自分がさっき投げたdpが、"基本的に"最適であることが完全に証明出来てしまう あれ?
流石にコードの内容的にもバグらせているとは思えないし、おかしいなーと言っている
こ「これ何で落ちてるって話になったんだっけ?」
シ「こういうの(w<x<y<z)」
コードを読み返す 2つのルートが1度も合流しない場合を考えていませんでした................................................................................
直すと流石にACする
ここからが困る
「H、セグ木でマージテクすれば間に合いそう」
「それMLEしない?」
「動的セグ木でやればMLEしないし動く」
「確かに 出来るじゃん」
「動的セグ木使える?」
「使えない」
「使えない」
「そっかぁ」
でHが終わる
相変わらずK不可能にしか見えない病を患っているのでKはやろうとしない
Lは開かない
Nは詰めれば出来ると思っていたが、順位表を見て流石にやめる
ということで、残りがIJMになる
相談した結果、残り時間的にもあと1問通せば御の字だろうし、お互いに通せそうな問題を頑張って考えようという話になる。
自分はJを頑張ることにする シナモロールはMを頑張る
頑張るが解けません 解けません
終了20分ほど前になると、解法が分かっても実装が重いであろうMは諦め、Jが分かれば実装は軽い問題であることに期待して、2人でJを考える
考えるが解けません 解けません
終わり際になってシナモロールに「こういう遷移計算でいいんじゃないか」と言われる
こ「うーん、多分正しくないし、仮に正しかったとしてもN<=10^9だから間に合わないんだよね」
シ「え、N<=10^6でしょ」
こ「え?」
終
制作・著作
━━━━━
ⓃⒽⓀ
本当に神バランスの良セットだったと思います。東京工業大学の皆様、FUTURE様、有難うございました。