Codeforces Round #516 参加記録＆解説（A～C）

Dashboard - Codeforces Round #516 (Div. 1, by Moscow Team Olympiad) - Codeforces

結果は3完！とはいえ、3完速解き勢が多くてレート上昇はそこそこ。Div1は修羅の世界。

f:id:betrue12:20181016232110p:plain

A～Cを振り返ります。Div2だとC～Eに相当します。

A. Oh Those Palindromes

Problem - A - Codeforces

問題概要

長さ $n$ の文字列 $s$ が与えられる。 $s$ の文字を並び替えたもののうち、回文になるような連続部分文字列が最も多くなるものを1つ出力せよ。

制約

$1 \le n \le 100000$
$s$ は英小文字からなる

解法

この問題にはとてもシンプルな答えがあります。ソートなどを使い、同じ文字を全て隣り合うようにまとめてしまえばそれが答えになります。例えば $s$ が abaacb だった場合、 aaabbc は答えです。

これを示すため、まずは回文になる連続部分文字列の数の上界を考えます。「並び替えをどんなに頑張っても絶対にこの値より大きくはならない」という値です。

文字列が回文になっているとき、その文字列の最初の文字と最後の文字は必ず等しいものである必要があります。そのため回文の数は、「文字列の中から、同じ位置または異なる位置にある同じ種類の文字を2つ選ぶ方法の総数」以下になります。これは具体的には、文字種それぞれについてその個数を $k$ として $\frac{k(k+1)}{2}$ を計算し、全ての合計を取ったものです。

aaabbc のように同じ文字をまとめた文字列から、同じ位置または異なる位置にある同じ文字を2つ選びその間にある連続部分文字列を考えます。その文字列は1種類の文字しか含んでいないため、必ず回文になります。そのためこのような並べ方は先ほどの上界を実現することが分かり、これが答えとなります。

閃けば一瞬。上位陣は爆速で通していますね…

ACコード

（C++）Submission #44295304 - Codeforces

B. Labyrinth

Problem - B - Codeforces

問題概要

$n$ 行 $m$ 列のマスで定義されるマップがあり、いくつかのマスには障害物があり進入できない。

マス $(r, c)$ からスタートし、マップ内を上下左右に0回以上好きな順番で移動してどこかのマスを訪れる。このとき上下には好きな回数移動可能だが、左には $x$ 回以下、右には $y$ 回以下しか移動できない。

障害物がないマスそれぞれについて、「上記の条件で $(r, c)$ から到達可能か？」を考えた時、到達可能なマスはいくつあるか答えよ。

制約

$1 \le n, m \le 2000$
$1 \le r \le n, 1 \le c \le m$
$0 \le x, y \le 10^{9}$

解法

制限が特殊ですが、「移動回数」をなるべく小さく保ったままマスを探索したい、ということでBFSをしたくなります。

左右の移動回数をなるべく少なくしたいというのは分かります。ただし、左右どちらを優先すべきか？というのは一概に決められません。このため、もしあるマスへの行き方の候補として「左移動は少ないけど右移動は多い」ルートと「右移動は少ないけど左移動が多い」ルートがある場合、どちらを採用すれば良いか決めかねてしまいます。

ただしこの問題の場合、「左右の合計移動回数」だけを管理し、それがなるべく少ないルートを採用すれば、それが各マスへの最適な移動経路となります。このことを確認します。

スタート地点の横軸座標は $c$ であり、そこから左右合わせて $s$ 回移動して $c^{\prime}$ に移動するとします。このとき左右それぞれの移動回数を $a, b$ とすると、

$b+a = s$
$b-a = c^{\prime} - c$

であり、この連立方程式によって $a, b$ の値が一意に定まります。具体的には

$a = \frac{s - c^{\prime} + c}{2}$
$b = \frac{s + c^{\prime} - c}{2}$

であり、合計移動回数 $s$ が小さいほど $a$ も $b$ も小さくなるため、 $s$ を小さくするルートが常に最適というわけです。

ということで、左右の合計移動回数 $s$ をなるべく小さくしつつ、 $x, y$ による制約の範囲内でマップを探索していきます。上下の移動はノーコストと考えることができるので、単純な「幅優先探索」ではなく、 $s$ が小さい順に近隣の探索を行っていく「最良優先探索」をやるとよいです。

最良優先探索の一般的な方法は、ダイクストラ法でお馴染みの優先度付きキューを用いるものです。ただこの問題の場合は、コストを0または1とみなせることから「0-1 BFS」で解くと速いです。0-1 BFSの解説としてはhosさんのスライドや、英語でよければこちらの記事などがあります。

ACコード

（C++）Submission #44303644 - Codeforces

C. Dwarves, Hats and Extrasensory Abilities

Problem - C - Codeforces

問題概要

（インタラクティブ問題）以下の処理を行い、最後に条件に合う値を出力せよ。

システムから整数 $N$ が与えられる。
以下の処理を回行う。
1. 解答者のプログラムは2次元平面上の整数座標 $(x, y)$ を指定する。これは毎回異なる点である必要がある。
2. システムはその点に対して、黒または白を回答する。
異なる整数座標を2つ指定する。この2点を通る直線が、以下の条件を満たす必要がある。
1. 前項で指定した座標点のうち、黒い点と白い点がこの直線によって分離される。
2. 前項で指定した座標点は、この直線上には存在しない。

制約

システムから与えられる値は $1 \le N \le 30$
解答者が出力する整数座標は、いずれも $0 \le x, y \le 10^{9}$

解法

1つの点を指定して、その点が2つの分類のうちどちらに属するかを判定し、境界を探る。これはまさに二分探索と同じ処理であり、二分探索のように解くことができます。

使える範囲は $10^{9} \times 10^{9}$ と広いですが、ほとんど1直線上で十分です。ある直線、例えば $y=1$ を考えます。

まず、 $(0, 1)$ のクエリを発行し、色を指定してもらう。
直線 $y=1$ 上で、 $x$ を二分探索するような要領で $N-1$ 回のクエリを発行する。すなわち初期値を $x_{lb} = 0, x_{ub} = 10^{9}$ として、 $x_{mid} = \lfloor\frac{x_{lb}+x_{ub}}{2}\rfloor$ として $(x_{mid}, 1)$ のクエリを発行する。そこで指定された色が $(0, 1)$ の色と同じかどうかによって、 $x_{lb}$ または $x_{ub}$ を $x_{mid}$ に置き換える。
クエリを必要回数発行し終わったら、これらの境界となる直線を引く。

のようにできそうです。ここで考えるのは「この方法で毎回異なる点を指定できて、かつ分離できるような直線が引けるのか？」です。

範囲が二分割される機会が最大29回であり、 $\lfloor\frac{10^{9}}{2^{29}}\rfloor = 1$ であることから、クエリ発行完了後の $x_{ub} - x_{lb}$ は最も小さい値で1です。クエリが完了する前にこれが1になってしまうと異なる点を指定できなくなりますが、その心配はないです。