ARC54 参加記
http://arc054.contest.atcoder.jp
参加してました。
解説↓
http://arc054.contest.atcoder.jp/data/arc/054/editorial.pdf
前回の記事では問題順に書きましたが、今回は時系列順に書いていきます。
～～21:00 コンテスト開始～～
まずはいつも通りA問題を開く。
読む。
字が多い。
A問題はもう少し字を少なくして欲しい。
ついでに変数も多い。少なくして欲しい。
一通り読んで、時計回りと反時計回りの2通りについて時間を求める、という解法が生える。
とりあえず式作って実装。
早速サンプル1が合わない。
高橋君のスピードが歩道のスピードより速いか遅いかによって誤答してるっぽい。
なんかabs()とかつけてごまかす
サンプルが通ったので提出。
--21:07 A問題 WA--
あれれれれ・・・
絶対適当に誤魔化したのが悪かったと思うけどどこが間違ってるか分からんぞ。
しばらくプログラムを眺めて、X>=Yのときは動く方向を決めれば良いことに気付く。
abs()で誤魔化す必要も無くなったので修正して提出。
--21:14 A問題 AC--
やったぜ。
絶好調の出だしでB問題へと進む。
読む。
334。
グラフが単調減少だったら二分探索できる？と思ってグラフ書いたけど下に凸なグラフだった。
解説にあるように三分探索なら解けます。
でも下に凸なら微分すれば最小値が求まるはずなので、突発数学コンテストを始めることにした。
問題を言い換えると、
のyの最小値を求める、となる。
y'=0となるxを求めれば、yの最小値も求まるはずなので、手計算でy'を求めることに。
求まった。ごちゃごちゃした式になってるけどこれをそのままプログラムにブチ込む。
あっさり実装終了。本文4行くらい。
実行。
サンプルが合わない。なぜだ。
しばらく首を傾げる。数式の写経ミスを疑ったが無さそう。
悩む。
～～10分後～～
数式の書かれた紙をよく見てみたら・・・
←！？？！？！？ｗｗｗｗｗｗｗｗｗ！？！？ｗｗｗｗｗ
axの微分だってことを忘れておりました・・・
という一悶着があり、サンプル合わない→数式間違ってた ってのを4回くらい繰り返した後、サンプル通ったので提出。
--21:41 B問題 AC--
ﾖｯｼｬ
ごちゃごちゃな式が書いてある紙を丸めて捨ててC問題を開く。
読む。
この問題文はずるいと思う。
あれ？これ組み合わせ普通に求められるんじゃね？ｗ
ビットDP使えばO(N2N)くらいでいけるやんｗってなる
実装する。結構手こずる。ビット嫌い。
コンテスト終了10分前くらいになんとかサンプルを通す。
提出。
めっちゃ祈る。
--22:21 C問題 RE--
あっランタイムエラーっすか。
なんでよおおおと思って問題文読み直す。
・
・
・
ん？
制約
1≦N≦200
ええええええええええN≦20だと思ってたえええええええ
というわけで盛大な誤読をしていたことに気付く。
O(N2N)が間に合うわけないやん。ていうか配列が確保出来ない。
この解法を修正するのは不可能だと悟り、他の解法を探るも分からず。
～～22:30 コンテスト終了～～ 2完
110位
まあ2完出来たので良しとする。
Cはなんかガウスの消去法とかやるっぽい。難しい。
Cに部分点があればワンチャン取りにいけたかな・・・嘘解法じゃなければ。
