AtCoder Regular Contest 089

AtCoder Regular Contest 089

Source codes

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

やったー 26 位だった！

Solutions

C - Traveling

$t_0 = 0$, $(x_0, y_0) = (0, 0)$ とする。どのような経路をとるにせよ時刻 $t_i$ には $(x_i, y_i)$ にいることに注意すると、この問題は全ての $i = 0, \dots, N-1$ に対しぴったり $T = t_{i+1} - t_i$ 秒で $(x_i, y_i)$ から $(x_{i+1}, y_{i+1})$ へ行けるかという問題に帰着する。以降これを解く。

まず $(x_i, y_i)$ から $(x_{i+1}, y_{i+1})$ へ最短経路を使って行けないとお話にならないので、 $d = \lvert x_{i+1} - x_i \rvert + \lvert y_{i+1} - y_{i} \rvert$ としたとき $d \leq T$ であることが必要である。また、 $d - T = 0$ in $\mathbb{Z}/2\mathbb{Z}$ が必要である。$d$ と $T$ の偶奇が一致していない場合は、目的時刻に目的地と奇数距離だけずれたところにいることになるからだ。逆に、今の 2 つの条件さえ充たされていれば、最短距離で移動→隣のますと行ったり来たりで暇つぶし、で目的時刻に目的地にいることができる。

ポイント

仰々しく書いたが悩む場所はなかった。

D - Checker

この問題は $K$ が固定されていることに注意する。するとまず、どのように市松模様を塗ったとしても、同じ色を塗らざるを得ない「運命共同体」となる座標がある。これは同値関係で結ばれていて、次のように定義される。

$\mathbb{Z}^2$ における同値関係 $(x, y) \sim (x’, y’)$ を、以下を充す最小の同値関係として定める：

• $\mathbb{Z}/K\mathbb{Z}$ において $x - x’ = 0$ かつ $y - y’ = 0$。
• $(x - x’)/K + (y - y’)/K = 0$ in $\mathbb{Z}/2\mathbb{Z}$。

商集合 $F = \mathbb{Z}^2 / \sim$ は $\{ (x, y) \in \mathbb{Z}^2 \mid 0 \leq x < 2K \land 0 \leq y < K \}$ で代表される。本問題においては $\mathbb{Z}^2$ におけるあらゆる代数構造は全く関係ないのでイコールと思っても問題ない。ここで、 あとで累積和をスムーズに取るために 、 2 倍の広さを持つ

\[ F’ = \{ (x, y) \in \mathbb{Z}^2 \mid 0 \leq x < 2K \land 0 \leq y < 2K \} \]

で取ることにする。上の段は下の段をコピーするのではなく、市松模様に塗るように$x$ 座標を $+K$ in $\mathbb{Z}/2K\mathbb{Z}$ だけずらすことに注意されたい。

int cnt[2000][2000][2] を $\text{cnt}[i][j][k] = (i, j)$ における点の数、$k=0$ の時白、$k=1$ の時黒を充すように入れておく。すると $0 \leq i < K$, $0 \leq j < K$ に対し $\sum_{p = i+1}^x \sum_{q = j+1}^y \text{cnt}[p][q][k]$ を求めれば、この部分を黒く塗ったとき or 白く塗った時に要求が充たされる数が求まる。黒く塗るなら、$W - w + b$ だし($W$ は白点の総数、 $w, b$ は和)、白く塗るなら $N$ からこれを引いた数である。このクエリの処理は $\text{sum}[i][j][k] = \sum_{x = 0}^i \sum_{y = 0}^j \text{cnt}[x][y][k]$ として累積和を求めれば $O(1)$ で済む。全体の計算量は $O(N + K^2)$ である。

ポイント

累積和を取る時に $F’$ で思考することを割とスムーズに思いつけたから時間内に実装ができたと思う。「上の段は下の段をコピーするのではなく」はミスしたが、 cerr で出したからわかった。

E - GraphXY

まず任意の経路の道のりは $iX + jY + a_{ij}$ の形である。ここで $a_{ij}$ は複数の可能性がある定数だが、最短経路しか考慮しないので、複数あることには意味はない。 1 つだけ考慮すれば良い。つまり $(i, j)$ ごとに一意に定まる定数である。そこで集合 $S_{XY} = \{ iX + jY + a_{ij} \in \mathbb{N} \mid 0 \leq i \leq 100 \land 0 \leq j \leq 100 \}$ と定める。そこで問題は、いかにして $a_{ij}$ を定めるかである。条件は

• 任意の $(X, Y)$ に対し、 $d_{XY} = \min S_{XY}$ である。

ここで 最小値の定義 から、これは以下の 1., 2. を充すことと同値。

1. 任意の $(X, Y)$ に対し、任意の $(i, j)$ に対し $d_{XY} \leq iX + jY + a_{ij}$ である。
2. 任意の $(X, Y)$ に対し、 $(i, j)$ が存在し $d_{XY} = iX + jY + a_{ij}$ である。

これを充すように $a_{ij}$ を定めればよろしい。実装のために、 1. の条件を

\[ (\forall (i, j))(\forall (X, Y))(d_{XY} \leq iX + jY + a_{ij}) \]

と書き換える。直感的に考えても明らかなように、できるだけ $a_{ij}$ は小さい方が 2. を充たすには有利である。だから 1. を充す最小の $a_{ij}$ を定めるべく、 $(i, j)$ ごとに $a_{ij} = \max\left(0, \max_{(X, Y)} d_{XY} - iX - jY \right)$ と定める。次に 2. の処理であるが、 bool OK[20][20] を持って置いて $(i, j)$ ごとにそれぞれの $(X, Y)$ に対し、 $d_{XY} = iX + jY + a_{ij}$ かどうかをチェックする。最後に $(X, Y)$ に対し全ての OK[X][Y] が true であるならば Possible 、そうでないなら Impossible である。

あとは、要求を充すようなグラフを具体的に $1$ つ作るだけである。これは以下のようにして作ればよろしい。

• $N = 202$, $S = 1$, $T = 202$ とする。
• $1 \mapsto 2, \dots, 100 \mapsto 101$ を X でつなぐ。
• $102 \mapsto 103, \dots, 202 \mapsto 203$ を Y でつなぐ。
• $i+1 \mapsto 202-j$ を $a_{ij}$ でつなぐ。

ポイント

$S_{XY}$ を最初に想定でき、それに従って、次に、グラフを思いつけた。最小値の定義に従って考察するのは自然とできていた。実装はそこまで重くなかったから、時間内に解けた。

F - ColoringBalls

あとで解説放送を聞く。

補足：仕切板での場合の数の言い換えについて

大学入試(もしかしたら中学入試や高校入試でも)では基本事項であるが、頭の整理のためにここでしっかり解説しておく。

まずは次の基本問題から。

問題 1 袋が $3$ つある。球は $5$ つある。袋は区別する。球は区別しない。それぞれの袋には $0$ 個以上の球を入れるものとする。球の入れ方は何通りあるか。

これは次のように言い換えができる。一列に $3+5-1 = 7$ つの「座」があるとする。イメージがわかないなら座布団にしておく。この座のうち、 $2$ つを仕切板 $S_1, S_2$ に変更する。変更しなかった座は球に変更する。仕切板 $S_i$ より右側にあって次の仕切板がくるまでの球を、袋 $i$ に入れる。ここで $S_0$ は一番手前にあると理解する。仕切板・球の状態が、上記の問題の球の入れ方に $1:1$ に対応している。

例も示しておく。操作ののちに

\[ S_1BBBS_2BB \]

となったとする($B$ は球)。この場合は、袋 $0$ に $0$ 個、袋 $1$ に $3$ 個、袋 $2$ に $2$ 個入れる場合に対応する。

だから、問題 1 の答えは $\begin{pmatrix} 7 \\ 2 \end{pmatrix}$ である。具体的な数字を使ったが、一般化は明らかだろう。

問題 2 袋が $3$ つある。球は $5$ つある。袋は区別する。球は区別しない。それぞれの袋には $1$ 個以上の球を入れるものとする。球の入れ方は何通りあるか。

あらかじめ袋 $1, 2, 3$ に入れておくための球を寄せておく。残りの $2$ つの球について、問題 1 を解く。つまりこの問題は

袋が $3$ つある。球は $2$ つある。袋は区別する。球は区別しない。それぞれの袋には $0$ 個以上の球を入れるものとする。球の入れ方は何通りあるか。

と同じになる。問題 2 の答えは $\begin{pmatrix} 4 \\ 2 \end{pmatrix}$ である。

2 個以上入れる必要のある袋があっても、あらかじめその分除いておけばよろしい。

問題 3 $n, m, k \in \mathbb{N}$とする。$0 \leq n-k \leq m$ であるとする。袋が $n$ 個ある。球は $m$ 個ある。袋は区別する。球は区別しない。 $0$ 番目から $k-1$ 番目までの袋には $0$ 個以上の球を入れ、残りは $1$ 個以上の球を入れる。球の入れ方は何通りあるか。

同じように言い換えると以下の通りになる。

袋が $n$ 個ある。球は $m - (n-k)$ 個ある。袋は区別する。球は区別しない。それぞれの袋には $0$ 個以上の球を入れるものとする。球の入れ方は何通りあるか。

座の数は $m-(n-k) + n - 1$ 個、選ぶ仕切板の数は $n - 1$ であるから、答えは $\begin{pmatrix} m+k-1 \\ n-1 \end{pmatrix}$ である。

ポイント

考察も非自明だし、実装が非常に重い問題だから、 ARC 的には観賞用の問題だが、学ぶべき点は多いと思った。

Others

C - sample: 3, tle: 2.000, time: 03:59, from_submit: 88:07
D - sample: 3, tle: 2.000, time: 49:26, from_submit: 38:40
E - sample: 2, tle: 2.000, time: 38:41, from_submit: 00:00
F - sample: 4, tle: 4.000, time: 00:00

E よりも D の方が実装に苦労しているのがわかる。

どうせこんな記事見ている人はどこにもいないから書いておく。

昨年からお医者さんと共にしてきた治療がうまくいっているようだ。 1 月から、気分の良い日はかなり調子がいい生活ができている。この日は朝早く起きて、『カードキャプターさくら クリアカード編』を見た。そこで「桜ちゃんかわいいなー」と余韻の浸りながら、日中論文の原稿を書いていた。そのまま ARC に突入して、 D どころか E も解けてしまったのである。信じられない。

私は人生の半分以上を深夜アニメを趣味としてで過ごしているが、 CC さくらは見たことがなかった ¹ 。よほど幼少からアニメ好きとして生きていない限り、私の世代はリアルタイムの世代ではない。ここ 20 年くらいにおける 2 次元の「かわいい」の進歩は目覚ましい。あの時代のデザインで現代でも通用するかわいさが描けているのは、誠に尊いと思う。桜ちゃん演じる丹下桜さんのボイスは脳みそがとろけるように素晴らしい。私は Fate シリーズのネロとジャックも好きなので、どうしても重ねて見てしまうのもあるのだろう。その魅力に抗うのは難しい。桜ちゃんは女性として好きというわけでなく(ロリ好きではないからな…)、純粋に、あのアニメを見ていて、かわいい、とにかくかわいいと思う。これから 6 ヶ月は晴れやかに過ごせると思う。

CC さくらは冗談としても、 1 月に入ってから研究も気分良くできて、プログラミングコンテストで時々満足いく成績が取れているのは、昨年よりもずっとクリアに思考できるようになってきたからという実感がある。継続的に治療を続けてきたおかげなのかと思う。お医者さんと共に治療していくのは、時間のかかることである。困難を感じることもあるが、諦めずに今後も続けていきたいと思う。

来週以降も同じような成績が取れる可能性は非常に低い。しかし、今回のようにうまくいく回が 3 ヶ月に 1 回くらいあるといいなと思っている。黄色で安定成績を残していきたい。

1. 実は 10 年くらい前から旧版を見るように勧められていた。私の友達で 10 歳くらい上のある人は知世ちゃんが好きらしい。旧版の再放送を見ていた後輩の O 君からも勧めれていた。 ↩