ABC273

ABCEの4完。これ100分は無理でしょ。

A - A Recursive Function

迷ったけど、問題文の通りに再帰を書くのではなく、階乗を書いた。デメリットは、問題文が本当に階乗か確かめる時間が必要なこと。

B - Broken Rounding

10^iの位以下を四捨五入するには、10*10^iで割ったあまりをRとしてまずRを引いて次にRが5*10^i以上なら10*10^iを足す。XをintでKをllで受け取って逆だったり、10^iで割って10倍違ってたりで、サンプルが全然通らなかった。

C - (K+1)-th Largest Number

解法はすぐ見えたけどそこから混乱したりした。この問題文かなり読むのが難しい。まずソートしてしまっていいので降順ソートする。大きい順に見ていけば、それまでに自分を含まず何種類あったか更新していってあればいい。問題は同じ数が連続したときだが、最初の要素では何もせず、それ以降で前の要素と違っていればインクリメントでいい(なぜそれでいいのかと言われると困る)。最初に何もしないの珍しい。

D - LRUD Instructions

嫌な見た目だが、とりあえずやる。横に動くときを例にすると、その行に壁がないなら簡単、壁があるなら両端(0とW+1)も含めstd::setに壁の位置を入れて自分がどの壁と壁の間にいるかstd::set::lower_boundで求め壁に当たるまで移動する。10分くらいで大体方針が立ったので、ここでEへ。縦横両方あって、壁もある場合とない場合があるって面倒すぎる。

(追記)ACした。けっこう短く書けたと思うが、短く書くにはしっかり考える必要がありそんなに実装時間は変わらないイメージ。20分くらいはかかる。まあ飛ばして正解。あと、上でsetと書いたけどそのあとすぐvectorでソートして二分探索すればいいと気づいたんだった。

(追記2)実行時間が短い提出があってどうやってんだと思ったらunordered_mapを使わずにpairで全体をソートしていた。言われてみれば(高速化するなら)普通のやり方だ。これ思いつかないのほんと錆びついてるな(直接競プロには必要ないが)。コードも意外と短くなる。

E - Notebook

永続。Library Checkerの「Persistent Queue」をやっていたので見に行くが、自分のコードの意味がわからない。ものを考える力が皆無(わからないのはよくて、何かに頼る方向性しか持ってないこの頭は)。

あなたの庭に永続データ構造を飾りませんか? - noshi91のメモ
ググってこれを見つける。思ったより簡単にできるものでありそう。これを貼って解けるならいいが、よくわからない。文章は簡単そうなので頑張って書く。木構造っぽい(近いものは自分でもちょっと思ったが、リスト構造とか明確に木とかが何も見えてない)。クエリ毎に、親と追加した要素を持つ。スタックの底に-1を入れておくか迷ったけど入れなかった(余裕がないね)。今どこにいるかの変数を持つ(iにいたらAの末尾はa[i]に入っている、親はp[i])。削除は親に戻るだけ(これで済むんかあ)。サンプルに2回も助けられた。未知のフィールドでまともにコードを書く力がない。

switch caseで書いたらめっちゃ煩雑になった。1行ずつで済まないならifのがいいな。

F - Hammer 2

左右に動くだけとはいえ選択肢が多い。ハンマーと壁だけ考えればいいとはいえ。考えて行動すれば選択肢は限られる気もするが。必要なものを足していけば壊す壁は決まると思うし、壊す壁の区間が決まれば取るハンマーの区間も決まる。貪欲に行って後悔したら戻るみたいのできないのかな。解けそうな気持ちをコードに落とせない。たぶん気持ちが間違っている。難しそう。

(追記)解説見たらたしかにそんな感じでDPできそうだ。なんか3乗になるイメージあったけど遷移が2通りしかないんだな。壁を含める必要はない気がしたのでそう実装した。ハンマーとスタートとゴールを座標でソート(座標の他にハンマー番号も持つ)。到達済みの区間を閉区間で考える。区間の幅(最初スタート地点だけのとき0で最大N+1)が小さい順に貰うDP。左端へ遷移するのは、今の区間の左側を1つ削ったものの左端と右端から。端から端へ移動するのはハンマーの入手に影響しないので遷移のときに移動してもらえばいい。問題は壁で移動できないパターンだが、幅1の各区間についてその区間内の壁を全て壊すのに必要なハンマーが存在する区間を前計算(愚直にやってO(N^2))しておきその区間に遷移元の区間が含まれていれば遷移できる。これは時間かかる。D問題の比ではない。

G - Row Column Sums 2

読んだけどわからない。Gまで読んで順位表を見てEに集中し、Eを通したあとはFを考えていた。