competitive: 4月 2021

2021年4月25日日曜日

AHC 002 A - Walking on Tiles

問題
AC

とりあえず愚直ビームサーチを書いてみると盤面全体を移動できないうちに行き詰まってしまうことがわかる。

こういうのをどうするかという時に手札があまりなくて困るが、安直な対処として、全体を10x10マスの25個のブロックに区切ってブロックを頂点とするグラフでハミルトンパスをひとつ与えて（偶奇によってはハミルトンパスがなくて24ブロックしか渡れないが）それに沿うような経路を探索するというのはありそう。ベスト方針とは思えないので少しためらっていろいろ考えたが、他に大した案を思いつかないので実装した。

現在のブロックを $B_1$ 、次のブロックを $B_2$ とするとき、 $B_1$ 内では幅6000のビームサーチをする。移動先は $B_1$ 内のいずれかのマスか、 $B_2$ のマスで $B_1$ に隣接しているもの（高々10個）に限る。後者は最高点の経路だけ保持する。 $B_1$ のビームサーチが終わったら $B_2$ のマスで $B_1$ に隣接しているものを始点に $B_2$ のビームサーチを始める。これで $5.2 \times 10^6$ 点程度だった。もう少し考えると、 $B_1$ と $B_2$ にまたがるタイルを取る/取らないで $B_2$ における探索に影響があるので、それらの違いも考慮して経路を保持する（高々 $10 \times 2^{10}$ 状態だが、平均的にはそれよりだいぶ小さい。) これで $5.3 \times 10^6$ 台に上がった。ビームサーチの幅を増やすと点はある程度上がるようだったので、最後の数十分は高速化をして幅8000のビームサーチが間に合うようにしたが、更新できなかった。

結果を見ると、2個程度のテストケースで25個のブロックを渡りきる前に行き詰まって終了しているようだ。そうなる可能性は認識していたけれど、seed=0から99まででは大丈夫だったので軽視していた。応急処置としては、時間があまりすぎていたらもう一回別のハミルトンパスで探索する等は思いつくが……
- コンテストが終わったあとで調べていたが、そもそもどう動いても隣接ブロックに移れないか、移れる経路が極端に限られるような配置がたまにあるようだ。
最初の考察で、タイル毎に取るほうを決め打つと普通の最長経路問題になるなと思ってしばらく考えていたが、それを利用する方針は思いつかず。
経路を一部破壊してからつなぎなおす方針で上位に入っている人がけっこういるようだ。これも考えたけれど、4時間で詰められると思えなかったので捨ててしまった。

2021年4月24日土曜日

ABC 199 E - Permutation

問題

$\operatorname{dp}[S] :=$ 集合 $S$ に含まれる整数を数列の先頭 $|S|$ 箇所に（制約を満たすように）配置する場合の数、としてDPできる。 $S$ に整数 $t$ を追加して $S \cup \{t\}$ に遷移する時、制約は $X_i=|S|+1$ であるようなものだけ調べればよい。

また、状態を入れ換えて $\operatorname{dp}[S] :=$ 集合 $S$ に含まれる位置に整数 $1, 2, ..., |S|$ を配置する場合の数、としてもDPできる。この場合は $|S|$ に位置 $t$ を追加して $S \cup \{t\}$ に遷移する時、制約は $Y_i = |S|+1$ であるようなものだけ調べればよい。

前者と後者は同じ形の遷移になっていて、一方を書いて入力の $X$ と $Y$ の順番を「間違える」ともう一方になって同じ答えがでる。これらの数えているものは、数列を置換とみなしたときに逆置換で一対一対応している。

第六回アルゴリズム実技検定

提出

リアルタイム受験した。O以外を通して94点だった。今回は前半の複数の問題にはまってしまって、辛うじてエキスパートという結果だった。

G - 一日一歩

素直に考えると最短経路問題を解けばよくて、通りたい道の直近で通れる日はRMQ上の二分探索で突き止められるが、Gでそんなことする必要がある？と悩んで時間を消費した。結局、最初に考えた通りに実装した。

H - カンカンマート

$T$の値によって2列にわけてどちらも昇順ソートして、$T=0$をできるだけ取るような構成にしてから$T=1$をひとつひとつ増やしていけばよい……のだが、それが見えずに三分探索などをして時間をかなり消費した。

L - 都市計画

道路の端点がタワーか環状交差点上になければならないという条件を見落としていて、解ける問題に見えなくて困っていた。

M - 等しい数

似た問題をCodeChefで解いたことがあったにも関わらず、長時間はまった。CodeChefの問題は平方分割で解いたのだが、実装が大変だった記憶があるし、この問題のほうがハッシュテーブルへのアクセスが多くなりそうだし、制約も厳しいし、ということで平衡二分木で解くことにした……のだが、複数箇所でバグらせてしまった。

区間を平衡二分木で管理するやつを改造して使うことにして、手持ちのものはmapではない（区間に対応する値がない）ので、区間$[l, r)$に入っている値は別に用意した配列の位置$l$に保持することにしたのだが、それが間違いだったかもしれない。区間の分割・消去・挿入などの操作間で、区間に入っている値を正しく保つための処理が複雑になってしまって、手におえなくなるところだった。

N - 活動

順番を固定できればラッキーと思って調べると、$a_i/b_i$の降順でソートしてよいことがわかるのでソートしてDPする。（しかし、最後の活動の取り方を素朴なDPで正しく扱えているのか自信がなかった。）

O - 最短距離クエリ

先に開いて少し考えたがわからなかった。似た設定の問題としてUTPC 2011 - 巡回セールスマン問題があったのを思い出したが、そもそもこれも解けていなかった。

2021年4月11日日曜日

ABC 198 F - Cube

問題
AC

サイコロが手元にあったので、回しながら考えた。まずはバーンサイドの補題を思い出す:

群 $G$ が集合 $X$ に作用するとする。この時、作用に関する同値類の総数は次の数に等しい:

\frac{1}{| G |} \sum_{g \in G} | F_{g} |

ただし、 $F_{g}$ は $g$ のfix、つまり $F_{g} = {x \in X | g (x) = x}$ 。

したがって、正六面体に対する回転操作で回転前と回転後が重なるものを列挙して、各回転に関するfixの大きさを求めればよい。正六面体に対する回転を分類すると以下の通り:

$id$ : 恒等変換、つまり何もしない。1通り。
$α$ : ある面の中心 $A$ と向かいにある面の中心 $B$ を結ぶ直線を軸に $90 °$ 回転する。どちら向きに回転するか述べていないが、ベクトルとみなして反時計回りに回転するとすると、 $A B$ と $B A$ で別の回転になって $3 \times 2 = 6$ 通りある。
$α^{2}$ : ある面の中心 $A$ と向かいにある面の中心 $B$ を結ぶ直線を軸に $180 °$ 回転する。3通り。
$β$ : ある辺の中心 $A$ と向かいにある辺の中心 $B$ を結ぶ直線を軸に $180 °$ 回転する。辺対が6ペアあるので6通り。
$γ$ : ある頂点 $A$ と向かいにある頂点 $B$ を結ぶ直線を軸に $120 °$ 回転する。頂点対が $4$ ペアあって、やはり回転する方向が2通りあるので $4 \times 2 = 8$ 通り。

合わせて24通りあるので、fixの大きさを求めて全部足して24で割ればよいことになる。上の回転によってどの面とどの面が重なるかを調べると、以下の数え上げをすればよいことがわかる:

$id$ : $x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} = S$ の正整数解の総数を求めることに等しい。
$α$ : $x_{1} + x_{2} + 4 x_{3} = S$ の正整数解の総数を求めることに等しい。
$α^{2}$ : $x_{1} + x_{2} + 2 x_{3} + 2 x_{4} = S$ の正整数解の総数を求めることに等しい。
$β$ : $2 x_{1} + 2 x_{2} + 2 x_{3} = S$ の正整数解の総数を求めることに等しい。
$γ$ : $3 x_{1} + 3 x_{2} = S$ の正整数解の総数を求めることに等しい。

$id, β, γ$ は単純な重複組み合わせに帰着するが、 $α, α^{2}$ がやや面倒に見える。

たとえば $α$ に関しては $1 / (1 - z)^{2} (1 - z^{4})$ の $z^{S - 6}$ の係数を求めることに等しく、 $1 / (1 - z)^{2} = \sum (\binom{i + 1}{i}) z^{i}$ （負の二項定理）を利用して $1 + z^{4} + z^{8} + . . .$ と掛けたときにどうなるか考えればよい。（自分は計算をバグらせてWolframAlphaに頼った） → $x_{3}$ を決め打つと $x_{1} + x_{2} = S - 4 x_{3}$ の正整数解が $S - 4 x_{3} - 1$ 個だから、 $\sum_{x = 1} (S - 4 x - 1)$ を非負の範囲で計算すればいいのか。難しく考えてしまった。

見て何をすればよいかはわかったが、WolframAlphaがなければコンテスト中にはACできていなかった。結局は計算力なんだよな。

$mod 6$ で多項式になりそうなのでラグランジュ補間、というのを見てなるほどと思った。とはいえ小さいケースをちゃんと求めるのにもある程度の考察は必要か。

https://q.c.titech.ac.jp/docs/progs/polynomial_division.html
そもそも母関数が書けた時点で貼るだけになるらしい。というか、これを知らなくても漸化式に直して行列累乗はできるのでそれは考えるべきだった。