ABC184

簡単回だった。Cでドキドキするのと、Dで少し考えるくらい。なんで簡単回と言いながら81分かかってるんですか?まあ実力通りだと思う。

A - Determinant

言われた通りに書くだけなので簡単。行列式ということで概念が難しく少し確認を入れたがそれでも32秒。

B - Quizzes

シミュレーションするだけで簡単と思ったが点数がマイナスにならないことを忘れてサンプル通らず。

C - Super Ryuma

直感的に嫌な感じがしてDへ行く。こんなところで消耗して後の問題が楽しめなかったら意味がない。Dの問題文を読んでからトイレへ。ウンコを出しながらCD両方ほぼ解けた。やはりこの実装はしたくないので、DEを先にやった。

「超竜馬だけど竜の動きはできてないじゃん」と一瞬思うが竜馬は馬のことだ(竜王が竜)。動ける先が多いので単純にBFSや全探索は無理で困る。しかし飛車の動きなら2回でどこでも行ける。角も筋違いでなければ同様。つまり答えは最大でも3だ(サンプルに3があるの親切)。答えが0や1のケースは条件式をそのまま書くだけなので簡単。残るは2回で行けるかの判定だけだ。まず、角の動き2回で行けるものを処理(偶奇)。そうでないとき角の動きを使うのは高々(今気づいたけど近くへの移動2回というパターンが考えから抜けてた気がする(本当に必要かはわからんが))1回、さらにこの駒の移動は可換、ということで1回目は近くへ移動するものとしてよい。面倒なので周囲10*10くらいを全探索する。(r1, c1)から(a, b)へ、(a, b)から(r2, c2)へ、それぞれ1回以下で移動できれば2回(以下)で移動できることになる。けっこうすっきり解けている。

(解説を見て)r=r2-r1, c=c2-c1 しないのアホやん。きれいに解けたと思ったら基本的なところが抜けてる。

D - increment of coins

枚数が多いほど増えやすいので、なかなかすっぱりとは解けなさそう。じゃあ全部で100^3パターンくらいしかないから順次計算していく?それもなんかよくわからない。逆だ。操作回数の期待値そのものを、枚数が多いほうから順次計算していくんだ。自分の増える先の計算が全て終わっているので、あとは確率で重みを付けて足して1を足せばいい。全部0枚のときは処理しないように注意。

E - Third Avenue

PASTでやれ、という感じの問題。ダイクストラやるだけ、と思ったけどBFSでいいじゃん、と思ったけどコスト0の辺を使うから01BFSになるからダイクストラでいいや。提出して、TLEの心配はしてなかったがMLEはちょっと気にしてた。結果は909ms、235MB。思ったよりかなりかかっててびっくりした(まあ、100万じゃなくて400万だからね)。コンテスト中はどうしてもこの辺をじっくり見積もる時間がない。AtCoderの場合、これで通らないということはほぼないのでコンテスト中に考えるというムーブが結果に対して悪い影響しかなく、「軽めのlogが付くくらいなら大丈夫だろう」で提出することになる。

実装としては、頂点数をH*W+26として、隣り合う2マスを見て障害物がどちらにもなければ双方向に辺を追加、英小文字からはコスト1で26個あるステーション(と脳内で呼んでいた)の自分の文字のところへワープしてコスト0で戻ってくる(好きなところへ戻れる)。辺の数はO(H*W)になるのでOK。

(解説を見て)01BFS使わない方法もあるのかー。まあ実戦的には面倒&正しさの確認が難しそう。

F - Programming Contest

Nが小さくて怖いので、先にC問題を片付けた。ナップサックとかも考えたけど、半分全列挙に気づいてしまうと40が半分全列挙にしか見えなくなる。実際できそうなのでそれで実装。N=1を場合分けしてから書き始めるが、実装するうちに1を0と1に分けても2^0と2^1になるから場合分けしなくても問題ないと気づいて削除した。{ 0, n/2, n } という配列を作って2回ループで処理。同じ処理は極力1回しか書かないようにする。ソートして、片方を大きい順に見ていき、もう片方を小さい順に可能なだけ大きくしていき最大値を更新していけばよい。しゃくとりみたいにやるのだが、ここでしゃくとり法の実装に引きずられて一生サンプルが合わなかった。足していくのではなく、列挙した値そのものを使うのだ。そんなこともわからない。半分全列挙に慣れていなさすぎる。そこを直せば当然サンプルは通るので、見慣れない字面を慎重に確認してから提出。なんとかノンペナ全完。