tsutaj @tsutaj@pawoo.net

天下一文字列集合 https://beta.atcoder.jp/contests/tenka1-2014-quala/tasks/tenka1_2014_qualA_c

文字列 s と t を同じ文字列で表現できるとき、s と t の間に無向辺を張る、ということを考えよう。このようにして作った無向グラフのあるクリークに属する頂点すべては 1 つの文字列で表現できるため、与えられたグラフをできるだけ少ない個数のクリークに分解する問題になる。

これは dp[S] := 頂点集合 S をクリークに分解する時の個数の最小値 とし、S と共通部分を持たず、かつクリークである集合 T をぶつけて、dp[S|T] = min(dp[S|T], dp[S] + 1) のように更新すれば良い。計算量 O((2^N)^2)

Space-Time Sugoroku Road について
閉路判定 + 最短路 (閉路および閉路につながるマスは使えない) と、解法はすぐにわかるが閉路判定がめんどい。
自分の実装では UnionFind で解決した。今回与えられるグラフは、各ノードの出次数は高々 1 であり、自己ループがないため、ある連結成分が閉路を含む条件は (ノード数) = (辺の数) を満たすとき、となる。unite するときに辺の数も数えてあげるとこの判定は簡単にできる。
他の人の実装も読もう！

今回の C と D どっちが実家かと言われると C だしなあ

再帰が必要な bit DP が苦手な気がするなあ

ドワコン 2018 予選 D について
・頂点集合 S の状態にするのに必要な値の候補として、まず明らかに各要素のディスク使用量の総和だけ必要になりそうなことはわかる
・S の前の状態 S' とは何かを考えると、「S から適当な頂点 v を取り除き、 v の子全てを追加したもの」であることがわかるので、(さっきの総和) + (v の子のディスク使用量の総和) も考慮する必要がある。さらに、S' における最適値を計算するにはその更に前も考慮する必要があり・・・と考えると、bit DP が生える

パス上に N 個あった頂点が〜 は嘘では？まあ確かに高さは log N に落ちるけどさあ

昨日みた蟻本初級編の問題、結構目から鱗だったな・・・。
d(u) を始点 s から u までの最短距離と定義するとき、コスト w の有向辺 (u,v) があるとすると、d(u) + w >= d(v) となる。(イコールはこの辺が最短経路に使われるときに成立)
隣り合うもの同士の距離が 「w 以上」とか「w 以下」 とかでも同様に不等式を作ることができ、制約式と辺を相互に変換できる

もともと木ではなかったものを木とみなしてやる場合もあって、例えば二重辺連結成分分解をかけて木にして、そいつに対して HL 分解をかけるパターンもある。結局何と等価であるかを適切に判断するのが必要っぽい

HL 分解について色々考察していたけど、やっぱりパス上に N 個あった頂点が log N 個になってくれるのが一番嬉しいんだなあ (大抵縮約後の頂点の評価にはセグ木とかの区間を扱うデータ構造が入るので実際には log^2 N くらいだけど)
LCA を求めて dist(s, t) = dist(s, lca) + dist(t, lca) - 2 × dist(root, lca) を利用して登って何かするパターンもあれば (パス上のコストの和など)、lca を使わずに s, t が属する chain が同じになるまで適切な場所に登って何かするパターンもある (パス上の最大値クエリなど)

余事象で考えたり、クエリを逆からやったり、文字列を反転したりなどなど、何かをひっくり返すとうまくいく場合って意外とけっこうあるのかもしれないな

実装上の罠はわりとあって、最初必ず止まるからと言って 2 番目の駅から更新しようとするとバグる (うまくやればこんなことは起こらないのかもしれないけど、止まらない場合を考える時に、「最初からずっと連続している」場合が抜けて死ぬ)

準急を久しぶりに解いた。この問題は「K 連続してはならない」という制約を「自分の直近 K-1 箇所のどこかで途切れている部分がある」と読み替えられるかどうかに全てがかかっていると言っても過言ではない。それさえ理解すれば、「駅 i で止まったかどうか、そしてその時の場合の数はいくらか」さえがわかればよいことに気づき、止まっていない場合を累積和で持っておくことによって線形で解ける

あとはしれっと余事象で解く必要があるけど、「〜〜〜の中に一度でも出現する」系は余事象でやったほうが絶対わかりやすい。そういう意味での類題は http://arc058.contest.atcoder.jp/tasks/arc058_c

問題を解いた時に、key insight が何であったかを反復しないともったいないね。地頭がよくないなりの精進法を考えないといけない

もちろんこの方針が可能であることの見極めもしなければいけなくて、今回の場合は H, W がともに小さいので bit 管理でもなんとかなることに気づかなければならない

JOI 旗で大切だったことは
・「自分の真上が "J"、そのすぐ右が "O" というパターンであるか」だけを確認すれば、今注目しているマスに何の文字を置けるのかがわかるということ
・前の結果を使いまわせるように bit で管理して計算量を落とすこと。今回の場合は直近 (W-1) 個の結果しか利用しないため、それを保持する。たぶん一番大事なのはこれ。
・何の列でどのような操作をする必要があるのかをしっかりまとめてから実装すること (最初の列や最後の列は諸々例外処理をしなければならない、この辺を有耶無耶にして実装に取り掛かると INF 時間かかる)

考察のプロセスを記録するには Twitter は向いてない (ネタバレになるので)

夏合宿2015day2D 真っ暗な部屋 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2709)
はじめは $ dp[S][k] = k $ 回の指示で集合 $ S $ の状態にできるか (bool 値) を解く DP を考えたが、指示の上限はいくつか、計算量は大丈夫か、などなど迷ってしまった (実際サンプルくらいの回数であれば正しく動くが大きいケースだと無理)
集合に対しての最短路を解けば良いと考えるとあとは早かった。集合に対して最短路をやったのはたぶん初めてなのでこの調子で柔軟に対処したい

Twitter が落ちている時に MSTDN を見に来ると避難している人がたくさんいるのがわかる (自分もそうだよ)

ちゃんと解説書きたいならブログの方に書くし、こっちはブログに書くまでもないけど残しておきたいやつを書く場所になりそう。あと思考プロセスを残しておくのも良さそうかな