Luzhiled's memo

メモということです

AtCoder Regular Contest 111

xooxxx (543rd)

コンテスト

おおまかな動き

A を読む　全く方針がたたない　何人かが一瞬で通していてびっくりしてしまう

15 分くらい考えてもわからないので一旦 B を読む

あきらかに二部マッチング　Dinic を貼る　なぜか実装に手間取る　まあどうにか AC(20:17)

C を読む　Minimum Cost Sort ですね！！！！！！！(大声)

どうせサイクルに分解はやるはず、そのあとでサイクル内で操作を完結させるかサイクル外でもっとも適切な人を扱うかの 2 択だと思うのでそれらを考える

ちょっと考えるとサイクル内で最も軽い荷物を動かす操作だけを考えると、初期状態で操作ができなくなっている場合を除き操作を完了させることが可能

前者は後者より真にコストが小さいし、初期状態で操作ができない場合は後者でも解決できないのでサイクル外の人を考える必要がないことがわかる

実装にめちゃくちゃ手間取る (2回目) (いつもの) (実家のような安心感)　実装に 30 分くらいかかったけどなんとか AC(59:48)

この時点ですでに A を通す利点が薄いので D を読む

$c$ のうち $c_v$ が最小となる頂点 $v$ を考えると、最終的なグラフにおいて $v$ は $c_v$ 頂点の出次数 0 の強連結成分に属することがわかる

この考察を踏んだ段階で $c_{a_i} = c_{b_i}$ なら $a_i, b_i$ は同じ強連結成分に属するし、 $c_{a_i} \neq c_{b_i}$ ならその大小をみて辺の方向を決められることがわかる

あとは一つの強連結成分内の辺の方向をうまいこと決めるだけなんだけどここをちゃんと考察せずに実装が破綻しそのままコンテスト終了　たすけて

反省点

相変わらず実装が下手　実装方針を引くのはそこそこ上手くなってきて余計な苦行は避けられているけど、他の実装がうまい人にそれでも負けがち

実装に対する考察とか、こまかい正当性とかを怪しいまま進めるのはよくないので定期的に反省したい

いい加減 AOJ-ICPC とか埋めて苦しむのをやっていきたい

解法 (A ~ E)

A - Simple Math 2 (300)

300 ではないと思います

求める答えを $k$ とすると、

$\lfloor \frac {{10}^N}{M} \rfloor \equiv k (mod M)$

$M$ の整数倍であれば $mod M$ の上で合同なので

$\lfloor \frac {{10}^N}{M} \rfloor + tM \equiv k (mod M)$

$tM$ は整数なので floor の中に入れてもよくて、

$\lfloor \frac {{10}^N}{M} + tM \rfloor \equiv k (mod M)$

$\lfloor \frac {{10}^N + tM^2}{M} \rfloor \equiv k (mod M)$

なので、 ${10}^N$ から $M^2$ の整数倍を足し引きしても値は変わらない
⇒ ${10}^N$ は $mod M^2$ で計算してオケオケオッケー

考察以外は繰り返し二乗法やるくらいだけど 300 ではないと思います

B - Reversible Cards (400)

前述　略

公式解説の方針もすごいと思うけど知識とライブラリで殴るほうが安全で早いと思う

これが通るのでやっぱさっきのは 300 でいいです

C - Too Heavy (600)

前述　略

公式解説と少し方針は違うけどやってることはほぼ同じ　もしかすると公式解説の方針のほうが少し実装が軽いかもしれない

D - Orientation (600)

序盤は書いてあるので省略

強連結成分内での辺の向き付けは dfs 木を作って後退辺を根方向に向き付けるだけで OK

制約から橋がないことが言えるのが多分本質で、それに気がつけば dfs 木も後退辺も自然と思いつけた気がする

惜しいような気もするし全然ダメだったような気もする　多分ダメだったんだろうな　やっぱりすぐ実装に走らずに細かいところをちゃんと詰めるように癖付けないとよくない

E - Simple Math 3 (800)

コンテスト後に問題を読んだ

考察として、区間 $[A+Bi, A+Ci ]$ の長さが $D-1$ 以上なら自明にその区間は解に含まれない

なので $i$ のとりうる最大値を考えると、高々 $\frac{D-1}{C - B}$ になる　解説を読んで気がついたけどこれはもう少し詰められる、ただ少し大きい程度なら解に影響しないことがわかっていたので OK

使わなかった考察だけど、その次に想像より区間 $[tD, (t+1)D ]$ の数は少ないんじゃないかと思って計算してみる　 $A = D-1, B = D-2, C = D-1$ を考えるとこれは $O(D)$ 個あるのでダメ

ただ、自明な考察ではあるが区間 $[tD+1, (t+1)D-1 ]$ に $[A+Bi, A+Ci ]$ が収まるならそれが解になる

もう少し言い換えて、 $\lfloor \frac{A+Bi-1}{D} \rfloor = \lfloor \frac{A+Ci}{D} \rfloor$ なる $i$ の個数が解

⇒ $i$ の上界を先の $\frac{D-1}{C - B}$ とすると、その差は高々1

⇒ $\lfloor \frac{A+Bi-1}{D} \rfloor - \lfloor \frac{A+Ci}{D} \rfloor = -1$ なる $i$ の個数が $\frac{D-1}{C - B}$ 個のうち条件を満たさない $i$ の個数

前者の総和をとると、一致するかどうかを総和で表すことができてかなり筋がよさそう、しかも floor_sum の形にすごく似ている

ので、 $N = \frac{D-1}{C - B}$ として $\sum_{i=1}^{N}{\lfloor \frac{A+Bi-1}{D} \rfloor - \lfloor \frac{A+Ci}{D} \rfloor}$ がうまいこと floor_sum の形にならないか考える

10分くらいうなったんだけど、2 つの底関数を足すことはなかなか難しくないか？となってかなり行き詰まる

しょうがないのでトイレ行って思考をリセットしたんだけど、冷静に考えて $\sum {a_i + b_i} = \sum {a_i} + \sum {b_i}$ 、〜完〜

あとは 1-indexed を 0-indexed にするなどの細かい調整をして終わり

実はこの段階でもまだこんなんで解けるとは思わなくて一旦投げてみるくらいの気持ちだったんだけどほんとに通っちゃって変な声でた