Mujin Programming Challenge 2018

Mujin Programming Challenge 2018

オフィスツアー・解説放送 今回は chokudai さん。すまない私はもう寝る。

Source codes

• My submissions (AtCoder)
• My source codes (GitHub)

Solutions

A - コンテスト名

S.substr(0, 5) で先頭の 5 文字を取り出す。

B - セキュリティ

指示通りに A を増減させる。ただし最初から $A = 0$ の場合を気をつける気をつける(アストルフォ風に)。

C - 右折

向きを変えたマス $(i, j)$ ごとに数え上げる。 $0 \leq i < N$, $0 \leq j < M$, $0 \leq k < 4$ に対し、

$f(i, j, k) = (i, j)$ から見て方角 $k$ にある . の個数、ただし # のマスの場合は $0$ と定める。

と定める。すると、答えは \[ \sum_{i, j, k} f(i, j, k) f(i, j, (k+1) \% 4 ) \] と求まる。そこで $f$ をメモ化再帰で求めればよろしい。

$g(i, j, k) = (i, j)$ から見て方角 $k$ にある . の個数、ただし自分自身も含める。基本的に $f$ と同じ

と定める。 $(i, j)$ が # ならば $g(i, j, k) = 0$ であるし、そうでないならば、 $i’ = i + dx[k]$, $j’ = j + dy[k]$ とした時に $(i’, j’)$ が範囲内でありかつ $g(i’, j’, k) \neq 0$ ならば $g(i, j, k) = g(i’, j’, k) + 1$ とする。 $f(i, j, k) = \max(g(i, j, k) - 1, 0)$ とする。

ポイント

実装は面倒だが、落ち着いて実装する。

D - うほょじご

コンテスト中に思いついた解法

$0 \leq x \leq N$, $0 \leq y \leq M$ の全ての $(x, y)$ に対しメモ化再帰で止まるまでの回数をシミュレーションで求める。ただし無限ループをどうやって処理するかは最初に方針を決めておく必要がある。再帰する前に -2 をメモしておく。再帰先が -2 ならループしているので、ループしていると判定する。

ちなみに $0 \leq x, y \leq 999$ ならば、新しい $(x’, y’)$ についても $0 \leq x’, y’ \leq 999$ が成立するので、メモは $10^6$ マスだけ用意しておけば十分である。

ポイント

これも実装は面倒な方に入る。落ち着いてやる。

解説放送の模範解答

$1 \leq x, y < 1000$ に対し、遷移 $(x, y) \mapsto (x’, y’)$ を求める。そして辺を $(x’, y’)$ から $(x, y)$ に張る。幅優先探索をする。初期状態 $(0, y), (x, 0)$ 全てを入れておき、ここから辿り着けるマスを求める。たどり着けなかったマスが遷移でループしているマスである。

こちらはループ判定をしなくて良いので汎用性が高い。

E - 迷路

「各秒ごとに L, R, U, D するためにかかる時間」を $O(1)$ で求められるならば、ダイクストラ法で普通に求めることができる。途中で遠回りしてわざと到着時間を遅らせる意味はない。なぜなら早く到着してそのマスで待てば同じことが実現可能だからだ。

そこで「各秒ごとに L, R, U, D するためにかかる時間」を前処理で求めれておけばよろしい。これは $K$ の剰余で良い。まず $D$ を 2 つ繋げておく。 $char = \mathrm{(L, R, U, D)}$ とする。

$dist[i][k] = $ 時刻の剰余 $i \in \mathbb{Z}/K\mathbb{Z}$ に対し方角 $k$ に行くための最小の待ち時間

として、実際は $0 \leq i < 2K$ で求める。 $dist[2K] = (\infty, \infty, \infty, \infty)$ とし、 $i = 2K-1, \dots, 0$ に対し、 $0 \leq k \leq 4$ に対し、 $D[i] = char[k]$ ならば $dist[i][k] = 1$ そうでないなら $dist[i][k] = dist[i + 1][k] + 1$ と定める。これで求まる。

計算量は $O(K + NM \log NM)$ である。

ポイント

間違えたところ： $\infty$ をどのくらいで持っておくか。最大で $KNM \leq 10^{11}$ であることを考えると $10^{12}$ くらいであるべきである。小さすぎて WA した。もちろん答えは ll で出力する必要がある。

実装は時間はかかるものの、部分的に見れば定跡通りで straight forward であるので、そこまで難しくはない。

F - チーム分け

方針の解説

chokudai さんの思考がわかりやすかったので書いておく。まず人の順番は関係ないので $M[k] = \sharp \{ 0 \leq i < N \mid a_i = k \}$ と定め、この情報だけで考察する。

この問題の悩ましいところは状態の管理の仕方である。人を順番に見ていこうとしても煩雑になりすぎる。例えば、番号 $0$ の人の所属するグループに番号 $4$ の人が所属した状態をどうやって管理するか。 $2^N$ 通りなんて管理できない。 $N \leq 1000$ であるから、あと 1 つの index で管理するべきである。それは何か、と考察する。

すると、人数の大きいグループから作っていくことにすると良いことに気がつく。 $i$ 人のグループを作ろうとした時には、 $a_k \leq i$ なる $k$ の番号を持つ人のみ参加できる。つまり $M[i], M[i+1], \dots, M[N]$ の数字だけが問題である。しかしもちろんすでにグループに入った人は除外されている。今からグループに分けられることが可能だがまだ分けられていない人を「候補人」と称する。その人数を「候補人数」と呼ぶ。この候補人数 $j$ だけ持っておけば、どの人が具体的に候補人として残っているかに関わらず、その後の遷移(グルーピング、 $i$ を下げる)につく係数は同じである。すなわち同じ状態とみなすことができる。

解法

DP をする。 $0 \leq i \leq N + 1$, $0 \leq j \leq N$ に対し、

$DP[i][j] = i$ 人のグループを、候補人数 $j$ を余して作る場合の数

と定める。初期状態： $DP[N + 1][0] = 1$ 、その他は $0$ 。答え： $DP[0][0]$ 。

遷移は以下の通り。 $i = N+1, \dots, 1$ に対し、 $j = 0, \dots, N$ に対し、以下の 2 つを行う。

1. $i$ 人のグループを $k$ 個作った結果、候補人数が $j$ 人になった。 $k = 1, 2, \dots$ に対し、 $j + ki \leq N$ ならば \[ \begin{align} DP[i][j] &+= \frac{1}{k!} \begin{pmatrix} j + ki \\ i \end{pmatrix} \begin{pmatrix} j + (k - 1)i \\ i \end{pmatrix} \dots \begin{pmatrix} j + i \\ i \end{pmatrix} DP[i][j + ki], \tag{F.1} \
   \text{i.e.,} ~~~~ DP[i][j] &+= \frac{(j + ki)!}{(i!)^k j! k!} DP[i][j + ik]. \end{align} \]
2. $i$ の人数の降下。 \[ DP[i - 1][j + M[i - 1]] = DP[i][j]. \]

これで答えが出る。注意すべきは 1. である。今回の場合、人は区別するが、出来上がったグループを区別はしない。つまり、例えば $\{1, 4 \}$ という $2$ 人グループを作ってから $\{2, 5 \}$ という $2$ 人グループを作った場合と、 $\{2, 5 \}$ という $2$ 人グループを作ってから $\{1, 4 \}$ という $2$ 人グループを作った場合は、全く同じグループ分けと見なされ、区別されない。そこで (F.1) の冒頭に $1/k!$ がつくというわけである。ゆえに、 $j = N, \dotsm 0$ に対して順繰りに $i$ 人組を素朴に作って降下していくような方法だと、今挙げた場合が区別されてしまうので正しい答えは出ない。

今回の場合は逆元 $((i!)^k j! k!)^{-1} \in \mathbb{Z}/p \mathbb{Z}$ ( $p = 998244353$ は素数) を求める際には、素直にフェルマーの小定理を使うか、または $((i!)^k j! k!)^{-1} = ((i!)^{-1}) ^ k (j!)^{-1} (k!)^{-1}$ とする。

計算量

計算量を議論しよう。ナイーブに見積もって $O(N^3)$ はすぐわかるし、これでも多分間に合うと確信が持てるが、実際は $O(N^2 \log N)$ である。というのも、 1. の過程では $k \leq N/i$ の範囲しか動かないので、全体の遷移回数の総和 $X$ は、 \[ X \leq \sum_{i = 1}^{N + 1} \left( \sum_{j = 0}^N \frac{N}{i} + 1 \right) = (N + 1) \sum_{i = 1}^{N + 1} \frac{N}{i} + (N + 1) \] 回で抑えられる。ここで、 \[ \int_{1}^{N + 1} \frac{N}{x + 1} dx \leq \sum_{i = 1}^{N + 1} \frac{N}{i} \leq \int_{1}^{N + 1} \frac{N}{x} dx \] であり、この両辺は $O(N \log N)$ である。ゆえに $X = O(N^2 \log N)$ である。

ポイント

chokudai さん曰く、この問題は結構難しいらしい。自分も少し悩んだ、サラサラ DP がかけた人は強いと思います、とのことだった。 rng さんだと全ての典型問題( ARC くらいだと)は同じくらいの難易度くらいのつもりで解説するので、そこにはないコメントで、ホッとした。

G - 移動

ポイント

H - タイル張り

ポイント

Others

オフィスツアーの権利を獲得した。やったー。

A - sample: 3, tle: 2.000, time: 02:39, from_submit: 108:02
B - sample: 3, tle: 2.000, time: 12:02, from_submit: 96:00
C - sample: 3, tle: 2.000, time: 23:54, from_submit: 72:06
D - sample: 3, tle: 2.000, time: 24:52, from_submit: 47:14
E - sample: 3, tle: 2.000, time: 47:14, from_submit: 00:00
F - sample: 3, tle: 2.000, time: 00:00
G - sample: 1, tle: 2.000, time: 00:00
H - sample: 3, tle: 2.000, time: 00:00