square869120Contest #5
Updated:
(2018/04/16 0:33) 他の人のソースコードが見られないので、もしかしたら rejudge があるのかと心配しています。記事書いていいか微妙なんだけど、もう寝なきゃいけないので upload することにする。
Source codes
Solutions
A - Sushi 2
$t = 0, 1, \dots$ 秒後にお目当ての寿司が取れるかどうかシミュレーションをする。
ポイント
こういう問題とてもいいと思う。誰もが AC できる上に、設定もそこまで自明ではない。誰しも腕組みするだけで終わるのが一番つまらないと思う。小課題で $N = 1$ を設定しているのもいい。
B - Emblem
基本的には、二分探索でも良いし、最小値をばっちし求めることもできる。ただし $M = 0$ の時は $\min r_i$ を出力することに注意されたい。
C - Two Parentheses
まず $A$ を構成する。前から ( を貪欲に選び、後ろから ) を貪欲に選ぶのが後から考えると最善である。この時にできた文字列がまず正しい括弧列であることを確かめる。次に余った文字で $B$ を構成して、 ( と ) を入れ替えたのちに正しい括弧列であるかどうか判定する。
時間内に証明が書けなかったので書いておく。
解法の正当化
補題 1：$S$ が正しい括弧列であるとする。 $S$ は部分文字列
)(を含むと仮定する。 $S$ のある 1 箇所の)(を()に変更したものを $S’$ とする。このとき $S’$ は正しい括弧列である。
さすがに証明略。正しい括弧列は前からカウンターを動かすことで判定できるのを使えば明快だろう。
補題 2： $K, L$ を非負の偶数とし、 $L \leq K$ とする。
(と)からなる $K$ 文字の文字列 $A$ から $L$ 文字の部分列であって正しい括弧列であるもの $B$ を取り出せる必要十分条件は、前から(を $L/2$ 文字貪欲に選び、後ろから)を $L/2$ 文字貪欲に選んでできる文字列 $B’$ が正しい括弧列であることである。
証明：十分性は自明。必要性を証明する。 $A$ から $L$ 文字の部分列であって正しい括弧列が存在すると仮定する。これを $B$ とする。文字列として $B = B’$ であれば示すことは何もない。そこで $B \neq B’$ と仮定する。すると $i < j$ が存在し、 $B$ を構成する際に次のいずれかが成立している。
- $a[i] = a[j] =$
(, かつ $a[i]$ は選ばれず $a[j]$ は選ばれている。 - $a[i] = a[j] =$
), かつ $a[i]$ は選ばれ $a[j]$ は選ばれていない。
いずれも類比的なので前者について議論を行う。このとき、 $a[j]$ の採用をやめて $a[i]$ を採用してそれを新たな文字列 $B’’$ とする。 $B$ と $B’’$ では ( の位置が前にずれていることになるが、 $B$ において )( を () にするのと、操作の便宜上 (( を (( にするのを有限回繰り返すことにより $B’’$ が得られるので、補題 1 より $B’’$ は正しい括弧列である。 $B \gets B’’$ として、このような動作を上記 2 つの $i < j$ が存在しなくなるまで行う。すると最終的にできる文字列は $B’$ である。以上より $B’$ は正しい括弧列である。証明が完了した。
命題 3： $N = \lvert S \rvert$ とする。問題文において $S$ が構成できる必要十分条件は、前から
(を $N/4$ 文字貪欲に選び、後ろから)を $N/4$ 文字貪欲に選んでできる文字列 $A$ と、余った文字列で構成した $B$ を(と)を入れ替えてできる文字列 $B’$ がともに正しい括弧列であることである。
証明： $S$ が構成できる必要十分条件は、 $S$ から $N/2$ 文字選んで正しい括弧列 $A$ を構成でき、さらに残りで $B$ を作って ( と ) を入れ替えてできる文字列 $B’$ が正しい括弧列であることである。よって十分性は明らか。必要性を証明する。 $S$ が構成できるのであれば、 $S$ はそれぞれ $N/2$ 文字の ( と ) で構成されている。この事実のもとで、 $S$ から、前から ) を $N/4$ 文字貪欲に選び、後ろから ( を $N/4$ 文字貪欲に選ぶと命題に述べた $B$ が構成できる。つまり $A$ と $B$ を今述べた方法で独立に貪欲に選ぶことができる。 $B$ については後で ( と ) を入れ替えるから、これは $B’$ にとっては補題 2 の選び方と同じである。 $A$ については補題 2 の選び方そのものである。よって $S$ が構成できるのであれば、 $A, B’$ が正しい括弧列であることが補題 2 より従う。証明が完了した。
ポイント
500 点だからそこまで難しくないと高を括るのが大事。
D - Battle with E869120!
$0$-indexed とする。しばらく $H, W \geq 2$ とする。勝利条件は $(H-1, W-1)$ を獲得することである。ゆえに、自分が $(H-2, W-1)$ または $(W-1, H-2)$ を獲得すると、次のターンに相手に $(H-1, W-1)$ を獲得されて負ける。ゆえに、最初から駒が置かれている $(0, 0)$ と、取ったら負ける $(H-2, W-1)$ と $(W-1, H-2)$ と $(H-1, W-1)$ を除いた残りのマスを 2 人でジリジリと奪い合う展開になる。手番を渡して、相手が折れるのを待つ。
今挙げた「残りのマス」の初期の数を $C$ とする。 $C = HW - 4$ である。 $C$ が偶数の時は後手、奇数の時は先手必勝である。戦略としては、相手が $(H-2, W-1)$ または $(W-1, H-2)$ を獲得した場合はすかさず $(H-1, W-1)$ を獲得する。それ以外は、獲得できるマスのうち $(H-2, W-1)$ または $(W-1, H-2)$ ではないマスが必ずあるはずなのでそれを獲得して手番を渡す。これを繰り返す。
例外は $H = 1$ または $W = 1$ の場合。必要なら swap(H, W) することで $H = 1$ としても一般性を失わない。この場合、 $W \geq 3$ ならば $C = HW - 3$ である。 $W = 2$ の場合は、いきなり $(H-1, W-1)$ が取れる状態なので、この場合だけ後手ではなく先手必勝である。
ポイント
これが一番最初に解けた。インタラクティブの問題結構好きなので先に手をつけた。
E - Broken Skateboard
ポイント
F - Lunch Menu
ポイント
G - Snake Escaping 2
ポイント
H - Percepts of Atcoder
ポイント
I - Collecting Gems is Fun
とりあえず自明な戦略を適当に出した。 FA 多分とったと思うけどどうか？ 最初に手をつければ面白い戦略を思いついて戻ってこれるんじゃないかと思ったけど、ほかの問題の部分点の自明な解法を書くだけでも時間かかるから戻ってこられなかった。
Others
いややっぱりこういうコンテストは慣れないですね。情報オリンピックみたいな形式です。時間は短かったものの、もう少し考えてみたくなるような良問が多かったと思います。前回より問題文が読みやすかったと思います。