japljコンテスト参加記

お久しぶり過ぎて・・・・・
お久しぶりです。今回はjapljコンテスト参加記。
Aを開く、読む、うーん、なんか関数を再帰的に定義しているらしい。
F1を書いてみる、ほうほう
F2を書いてみる、ほほう、山々ができてくるわけね
山の個数は2の累乗個、の前後、解けたーーー
投げる、「30パーセント正解」
なん・・・・・・だと・・・・・・
コーナーケースがあるんだろうなーとか思ったが
問題が単純なため、気付くのに時間がかかると思い、Bを読む
なるほど、K番目になりうる物を出力か・・・・
個人には力の優劣がついていて、遷移する・・・
力の関係をグラフにするとDAGね
おー、トーナメントの結果はその一部を埋めてるわけね
で、K番目までになりうるのは、優勝者から距離Kまでにいる人
DAGだしDFSすりゃいいじゃん
入力がパースし辛い・・・・投げる、おお、通った
Aに戻る、コーナーケース無いかなー、おお、なんかループ回す最大値ちげーし
投げる、30パー正解・・・・うーん・・・・お、これPが0の時だめじゃね
投げる、通った。
Cを読む、なるほどね、線形でやれと、なんとなく、隣り合ったものはつなげたい気分になる
辞書順最小が線形でもとまるのだから、たぶんそうだよねーー、これGreedyにやりゃいいんじゃね
スタックで適当にGreedyっぽいコード書く、投げる、通った
ここらへんで1時間半くらい
さて、hosさんたちも相当苦戦しているらしい
これ俺なんかが解けるのか
D,E,Fを全部読む、知るかこんなもん
とりあえず100パーねらいのコードを目指して、残り45分切ったら部分点狙いに切り替えよう
Dを考える、0以上かどうか判定するのにどうしても時間がかかる、しかもなんだこのタイルの
繰り返しって・・・・・謎ゲーすぎる
E、そもそもある時間を見た時、大きさN以上のものを判定するのにも工夫がいる
これはあきらめる
F、見た中で一番まともそう、計算量的な観点で見ても明らかにDP・・・・なんだけど
どやってやるの？とりあえず一つサイクルを作ると、その内部には枝を張れないから
そのサイクルにつながってる先のツリーの部分グラフすなわち部分問題に分解できるのは
わかるけど・・・・・・まぁ、ただでさえDP苦手な俺が解けるのか・・・・
ここで45分来る、あちゃー、まぁ、部分点狙いで
Dの全探索コード書く、投げる、0パーセント、なん・・・・・だと・・・・・・
考える、考える、焦る、一回別に書いた奴投げる、0パー・・・やっべー
あ、wとh逆にしてる・・・・orz
まぁいいや、投げる、15パーを期待したら予想に反して30パーが返ってくる
次の15パーも結構イージーだったのね
ここで試合終了

JOIみたいな部分点方式は初めてでとても面白かった
また、こういう形式でコンテストをやってほしいと思った
正直最後、バグがなければ、EFの部分点コード書いて投げたのに・・・
実装力無さ過ぎ・・・・反省、こういうのがあるのがJOI形式の面白さなんだろうな

追加で書くと、Dに関して試合後ちょっと考えてた、これ大きさdの格子で区切れば、あとは
長方形のクエリのサブ問題に落ちるじゃないの・・・
長方形クエリなら2DBITが使える
だが・・・・クエリ数多すぎてこれでもだめか
クエリを平方分割するというアイデアが浮かんだけれど
それでもたらない、うーんバイナリーサーチできるの？
アイデアはあっててそれをうまく使えてないだけかなぁ
だけど、それくらいしか思いつかないよなぁと思っている
綺麗かつ新鮮な解答を期待ってことで・・・・