ABC119

100位以内に入れた。よし。クセのあるセットだったけど、なんとか。開始前に36.9度あったのは、体感としては影響なし。ブログ書き始めた今も36.8ある(平時は36.0~36.5)。

A - Still TBD

"Heisei"とかをコピペするのめんどい。期待して問題文を見ると2019年の日付なので、月だけ比較すればいい。4/30は前のほうなのでやはり月だけでいい。mmが何文字目か手で数えて、幸い変な分岐も発生しないので、1桁ずつ条件を書く。この問題は1分切れなくても仕方ない。

B - Digital Gifts

これは、やるだけ。見た目に反して面倒なところもない。全部doubleで処理するだけ。1.38e8などと出力してもいいのは親切だ。

C - Synthetic Kadomatsu

Nが小さい。かなり嫌らしい問題。実装が面倒な予感しかしない。すぐには解法も思い浮かばず、焦る。「漏らす前に全完すればいい」は叶わず、トイレでO(3^N)の解法を思いつく。組合せ的なことを色々考えたけど、A,B,Cそれぞれに使う竹を決めてしまうのがいい。3^Nを計算してその回数だけループする。3で割りながら剰余を配列に入れて、i番目の竹をどれに使うか(A,B,CはA[3]で受け取るように変更した)0,1,2で表す。竹の長さは0より大きいので、現在の和が0より大きければMPに10を足していく。和が0だったら0本の竹では作れないので飛ばす。ここで作れなくても他で作れる。最後に和とA[j]の差を足せば消費MPが求まる。それの最小値が答え。サンプルが合わない。答えが大きく出てしまうということは?ああ、O(4^N)でした。使わない竹があるかもしれないんだった。ていうかO(N*4^N)だ。解くのにトイレで5分、実装に10分という感じだった。

D - Lazy Faith

神社と寺とその数え方でけっこう時間を取られる。西端なのも気になるが、東でも同じことなので考えなくていい。さてどんな問題だと本格的に考え始めてしばらく経つと、「二分探索をやるだけでは?」と気づく。いつもの二分探索じゃなくてstd::lower_boundで済むやつ。最近使ったので使い方をすぐ思い出せる。それでも慣れなさはある。これでもう解けてるけど、x地点の近くにある2つの神社と寺をどの順に訪れるかを全探索するか、するとしたらどう書くのがいいか、しないとしたらどんな方法かを考えなければならない。ここがかなり嫌。まず、s,tの配列をそれぞれ2個増やし番兵みたいにする。二分探索を2回して配列に4つの座標が入る。色々考えたが、最初に訪れる場所をforで回す。次に訪れるのは、自分と異なるカテゴリーのどちらか。お、きれいに書けた。サンプル合わないのは、答えが小さく出てるので0を訪れている(番兵のs[0]は1より小さければいいと思っていたが十分に遠い必要があった(-1LL << 60のようなマイナスを付ける書き方を嫌ったのも影響してる))。二分探索するだけで簡単すぎないかと思いきや、その後のやるだけ部分の具現化でけっこう悩む問題だった。あとから考えると、なんでこんなに時間かかってんだ。