ABC185

ノンペナ全完だけどうれしくない。A<<C=D=F<B<E みたいな難易度だった。

A - ABC Preparation

最小値。min({ a, b, c, d }) と書ける。

B - Smartphone Addiction

一番時間をかけたのがB問題っていう。簡単なのはすぐにわかって、実装が面倒というやつ。こういうの瞬殺する力は確かに実際のプログラミングで役立つけど、ratedコンテストでやる問題ではない。ここでパフォーマンス100くらい溶かした。クソゲーにもほどがある。

C - Duodecim Ferra

なかなかの殺意。好きだけどBで消耗してるときにこれはきつい。

分割後の棒の長さが1以上なので、1ずつ取り除いてL-12個のボールに11個の仕切りを入れる。とりあえずいつものライブラリ貼ってサンプルは通るが、確認するとやはりL=200でオーバーフローする。どうやったらいいのって一瞬(一瞬にしてはだいぶ長い)思ったが、普通に 199/1*198/2*197/3*... とやっていけばいいんだね。最後に11で割るので、その前にオーバーフローしてないか確認して提出。けっこうギリギリだった。答えが2^63未満って書いてあるけど、だからって普通に計算できる保証はないんだよなあ(今回の場合だと途中経過で答えの11倍になっている)。

(解説を聞いて)パスカルの三角形でやれば、答えが2^63未満なら計算過程でもそれ以下の数しか出ないね。オーバーフローする範囲を計算しないためには、メモ化再帰も使える。

D - Stamp

これサンプルが、連続白マス数の最小を与える区間がみんな内陸なんだよね。「N個のマスのうち連続するkマス」と明記されてはいるものの、マスからはみ出してスタンプ押してもいいんじゃないかという不安がそれでもつきまとった。さて、言ってることはわかるけど、趣旨がよくわからない。両端に青マスを追加し、青マス間の距離が0より大きい中での最小を求めそれで塗る。回数を求めるときに切り上げは必要になるか。

E - Sequence Matching

ここで順位表を見る。BCでペナ出してる人が思ったより少ない。Fが簡単そうなので先に片付けた。

DPかなと思って、DPはDPでも編集距離に近いのではと気づく。「yukicoder 編集距離」で検索して出ず、「yukicoder レーベンシュタイン」で検索して目的の問題を見つける(そこには自分の提出がある)。コピペして入力の形式とか合わせたらサンプルが通ってしまった。この問題だと挿入はないが、最終的な位置で相手を削除したと考えることができる。置換はyだし、削除はxだ。順位表を見てもペナが少ないし、編集距離と違うところも見つからないので提出。短時間でACはとったが、ちゃんとやるには典型を理解している必要があり難しい問題だと思った。

(解説を見て)明快なDPだあ。そう考えるのか。こんな理解度で11分ACしていいわけないだろ。

F - Range Xor Query

大量に解かれているとはいえ簡単すぎて誤読を疑う。セグ木やるだけ。遅延ですらない。しかもxorだからBITで足りそう。せっかくなのでBITで実装した。加算以外で使うことはほぼないので、実装が楽しい。BITなので差分をとるが、引き算をxorに変え忘れてサンプル通らず。最初は意識してたのになあ。