どうも気分が浮かないので久しぶりに散歩をした。最近あまり自宅と大学から離れたところを歩いていなかったので、久々に通るとやや様子の変わっている場所がところどころあった。
おそらく10kmくらいは歩いたのでだいぶ足が疲れた。
今日解いた競プロの問題。
ABC279-G: まずKマスの塗り方を考えてみると、これは2色でさえあれば良いので$_CC_2\times 2^K$通りになる。ここから1マス増やすことを考えると、最後のK-1マスが同じ色であればC通りの選択肢がある。そうでない場合は最初に選んだ色のどちらで塗るかという2通りしかない。ということで、最初のKマスの塗り方は「後ろからK-1マスが同じ色である場合」「後ろからK-1マスに2色含まれる場合」に分ける必要があることが分かる。
さらにもう1マス増やすことを考えると、再び後ろからK-1マスが同じ色である場合とそうでない場合を考える必要が出てくるが、これを求めるには最初に「後ろからK-2マスが同じ色である場合の数」を考えなければいけないことが分かる。同様に考えると、任意の$i\leq K-1$について「後ろから$i$マスが同じ色である場合の数」を管理しなければならないことが分かる。
ということで、dp[i][j]=(先頭からiマスの色を決めたとき、後ろからjマスが同じ色であり後ろからj+1マス目は異なる色であるような場合の数)とする。$j>K-1$の場合の数は$j=K-1$にまとめてしまってよい。これは$O(NK)$で計算できる。
これの遷移を考えると、dp[i][j]が寄与する先はdp[i+1][j+1]とdp[i+1][1]のみであることが分かる。つまりdp[i+1]の大部分の要素はdp[i]を1個ずらしただけなので、ここに付け込んで高速化できる。
新しいDPテーブルdp’をdp'[i][j-i+n]=dp[i][j]で定義する。こうするとずれを打ち消しあうことができる。nを加えているのは単に添え字を負にしないためで本質ではない。
あとは適宜やっていくことで、配列を1次元にして値を使いまわす形に直すことができる。
全要素をdp[i+1][1]に加算する部分は、全要素の和を持って差分だけ更新していくことで計算量を落とせる。ここの式変形に不手際があり、K=2の時だけ動かず1WAした。
かなり久しぶりに橙diffをACできた。まあ、ABCのGなので単に時間の問題で解けなかった人の多い問題だとは思うが。それでもそれなりの難易度の問題だったので嬉しい。
チェンソーマン4巻を読んだ感想を書いてなかったので書いておく。ネタバレ注意。
ヘビの人、あんなのを使役した代償が一応あって安心した。いや釣り合ってないだろ。体全体と爪4枚やぞ。なんなんだ。あれヘビって呼んでるけど本当にヘビなのか？わざわざ「ヘビのような姿の強力な悪魔」って紹介されてるし。
サムライソード(この呼称どっから出てきたよ)はなんかすごい速さで斬りこむ特殊能力があるっぽいが、初手で使ったり常に使いまくったりしないあたり制限付きなのだろうか。なんか構えをとる描写があったり、「ぐっ…！」とか呻くところもあるし。死んでも死なないのは完全に謎。魔人＝悪魔による乗っ取りだったら常時頭が変な形になってそうだがそうではなさそうだし、デンジと似たやつなのだろうか。
マキマさん、まあ死んでないんだろうなとは思ったが、こんな直球で単に「効いてない」とは思わなかった。人間じゃないか、あるいは人間じゃない成分を多分に持ってるような人間なんだろう。
能力の行使シーンマジでえげつなさすぎて笑った。名前知られたら終わりじゃん。実質胎界主第二部じゃん(全てを胎界主にするな)。しかし、上の人間の名前を知らないのに(あるいは知ってて泳がした？)下っ端の名前を知ってたのはどういう訳なんだろう。あと悪魔の姿が見えないあたり、マキマさん自身が悪魔か何かとしか思えん。恐らくただの人間が素で特殊能力を行使するような世界観ではないだろう。後のシーンでもなんかグッと睨んだだけで流血させてるの、何？
コベニちゃんがやばすぎる。こんなフィジカルやばい人間だと思わないじゃん…辞めようとしてるけどどう考えても一番デビルハンターに向いてる逸材でしょ…
刀を使うと寿命削れるってやつ、ここまでひどいとは思わなかった。30年くらい削れんのかなと雑に思っていたが、1発で余命2年は容赦なさすぎないか。しかも相手殺せてないし、散々すぎる。
最強のデビルハンターの人だいぶ好き。冷静な態度だが冷静に狂っている。「おもちゃにも情が湧く」がフラグにしか思えんのだが、大丈夫だろうか。
特異課のメンバー(人外)の紹介の流れが自然で上手いなと思った。人類側に付いている人外は全員パワーと同じように魔人なのかと思っていたが、悪魔もいるとは驚いた。「天使の悪魔」がもうしっちゃかめっちゃかな名前で好き。あと顔が良い。
Categories: 未分類