ABC130:水色競プロerのムーブ備忘録 300点問題へのリベンジ

競プロ引退はやめたsyunsukeです。

今回はABC130のムーブ記録です。

配点　A:100 B:200 C:300 D:400 E:500 F:600

制限時間　100分

コンテスト開始時のsyunsukeのレート　1236

今回の方針　300点問題絶対ゆるさん！！(昨日300点問題でやられてます)

　　　　　　まずはCの300点問題からたたき潰す！！

コンテスト開始

C：A、Bは置いといてまずはこいつから潰す！

　？？？

　こいつヤバくね？

　一旦撤退

A：if文が書ければよさそうですね。

　　イージーミスには気を付けて。

　　念のためテストケースを通して。

　　1:48 AC

B：累積和をしておいて・・

　　あれ？Nが小さい。

　　順番にLを足していき、Xを超えたら終了

　　Xを超えるまでの回数を数える。

　　あれ？結局それって累積和じゃん・・

　　無駄なことをしながらも

　　5:29 AC

C：帰ってきました。

　　今回の目的はこいつを叩き潰すこと！

　　でも、こいつは場合分けが難しい(と思ってました)

　　Hとｘの比とWとｙの比を比べて・・

　　大きな長方形の対角線上にいるときは2分割できるし(どこでもできることに気づかず)

　　いろいろなケースを想定して丁寧にコーディング

　　テストケースで確認して

　　1WA！

　　まあ場合分けの難しい問題なので(そう思ってました)1WAくらいは仕方がない。

　　コーナーケースはｘ＝０とｙ＝０ｘ＝Wとｙ＝Hが危ないよね。

　　そこも潰して

　　2WA！

　　昨日の悪夢が蘇る。

　　こいつをつぶすことにこだわって、つぶされてはいけません。

　　一旦パス

D：累積和をとっておいて、A[i]＋Kを超える点を二分探索して足していく。

　　これは難しくないですね。

　　38:06 AC

　　時間がかかったように見えますが、20分以上Cに時間をとられたので、Dは10分ちょっとです。

　　Dだけ見ればよい感じ

E：最長部分列？？なんかそんな感じの名前のdpの有名問題に似てるけどどうする？

　　有名dpのコードを書いて、適当にいじってるうちに正解が出ればラッキー

　　・・

　　・

　　出るわけありません。

　　Cに戻りましょう

C：なんで皆さん解けるんですか？

　　私には見えないコーナーケースがなんで皆さん見えてるんですか？

　　コーナーケース(と思われたもの)を修正してはWAを重ねて５WA

　　あれ？四角って中点とx,yを通せば絶対2分割できるじゃん

　　で、中点とx,yを結ぶ直線が引ける条件は？？？

　　どう考えてもAll OKでしょう。

　　2本以上線が引ける場合は・・中点のみってことは

　　書いてたコードを全部消して、

　　多分1分かからずにコードを書いて、テストケースを確認して

　　63:03 AC 5WA やってくれましたね。

　　そりゃ皆さん瞬殺する問題でしょう。

E：もう一度有名dpをいじりながらTime　UP

A,B,C,D４完　63:03 5WA  1435位でパフォ1114　レートは-12で1224

300点問題　またしてもやってくれましたね。

考察で約50分、ペナルティで25分こいつに持っていかれました。

というわけでリベンジ失敗

返り討ちにあいました。

今回のムーブで良かった点は、Cが危ないと分かった時点で、きっちりDに移行できたこと。昨日の反省は生きているようです。

次回方針は、300点問題は後回し