競技プログラミングの大会に参加したので、簡単に概要と解説を書いていきます。かなり前の話ですが。

Educational Codeforces Round #49

問題セット：

公式解説：

ところで、今回参加した Educational Codeforces Rounds は競争ではなく練習や教育を目的としたコンテストだそうです。3年前の開催告知記事：

A. Palindromic Twist

問題概要：英小文字からなる文字列 S がある。各文字をアルファベット順で前後の文字のどちらかに置き換えるとき、回文にできるか判定せよ。

例えば c は b か d のどちらかに置き換えられます。S=bad なら abc, abe, cbc, cbe の4通り。cbc が回文なのでこれはYES。

回文にする方法は、b→c←d のように真ん中で合わせるか、 b→c←b のように初めから合っている文字を同じ方向にシフトするかのどちらかです。これを両端から中央まで調べていけばOK。

ただし a と z はそれぞれ b, y にしか変更できないので注意が必要……と思ったんですが関係ないですね。それとインデックス計算のミスがたたって、筆者はWAでした。

提出 (コンテスト終了後)：

B. Numbers on the Chessboard

問題概要：正の整数 N がある。N×N の盤面に、規則的に 1~N^2 の値を書いた。座標 (y, x) の値を求めよ。規則とは、左上から右下にかけて1つ飛ばしで値を埋めていくというもの。図を参照：

頑張って座標を計算すれば解けます、以外にない。

提出：

C. Minimum Value Rectangle

問題概要：棒が N 本ある。長さが x, x, y, y である4つの棒から1個の長方形が作れる。この長方形の周長を P = 2(x + y)、面積を S = xy、価値を V = P^2 / S とおく。最も価値の低い長方形を作れる棒の組み合わせ x, y を求めよ。

まず、ペアにならない棒は無意味なので除去。同じ長さの棒のペアを3つ以上残す意味もないので「同じ長さの棒が 2~3 個なら1つ」「4以上なら2つ」という変換をかまします。(この場合分けはただ実装を複雑化するだけなので、やらないほうがよかった。長さが同じ棒の数を2で割るほうが素直。)

価値の話に戻ると、

V(x, y)
= 4 (x + y)^2 / xy
= 4 ( y/x + x/y ) + 8

だから x と y の差が小さいほど価値が低いだろうと推測しました。実際、長さ x < y < z なら価値最小は V(x, y) か V(y, z) であって、 V(x, z) になりえない、ということは初等的な計算で示せます。

表計算ソフトを開いて実際にやってみようとしたんですが、行番号と列番号を使う式の書きかたがよく分からなくてやめました。

したがって、棒の長さの組み合わせとしてありえるのは、長さが近いペア同士だけです。組み合わせが大幅に減らせたので、あとは全探索でOK。つまり、棒を長さでソートして、隣り合う棒のペアから価値を計算して、価値が最小になるものを見つけます。

ところでこの問題の制限時間はかなりシビアっぽく、結果は TLE でした。

提出 (TLE): https://codeforces.com/contest/1027/submission/41773508

棒の重複を除去するところで二分探索木 (BTreeMap) を使うのが富豪的すぎたかな？　と反省して、配列を使う実装にして再提出しましたが、依然 TLE でした。 

提出 (コンテスト終了後、TLE): https://codeforces.com/contest/1027/submission/42209530

配列や文字列の領域をクエリーごとに確保するのをやめて、1つのバッファを使いまわすようにしたらぎりぎり(1920ms)通りました。気をつけよう。

提出 (コンテスト終了後、AC):

D. Mouse Hunt

問題概要：N 個の部屋があり、1匹のネズミがどこかにいる。ネズミは規則的に部屋間を移動していて、部屋 i にいるなら、次は a_i に行く。ただし i = a_i なら停止する。ネズミがいる部屋にトラップがあると、ネズミは捕獲される。いくつかの部屋にトラップを仕掛けて、ネズミが必ずいつか捕獲されるようにしたい。部屋 i にトラップを仕掛けるコストを c_i とするとき、最小のコストを求めよ。

一例として、部屋数 N=5 で、ネズミの移動経路が部屋 1→2→1, 3→4→5→4 というケースを考えます。ネズミが 1, 2 のどちらかにいる場合に備えて、 1, 2 のどちらかにトラップが必要です。また、3~5 のどこかにいる場合に備えて、 3~5 のどこかにもトラップが必要です。

もし部屋 3 にトラップを置くと、ネズミが初めから部屋 4, 5 にいる場合は捕獲できないので、部屋 4, 5 に追加のトラップが必要です。逆に、部屋 4, 5 にトラップがあるなら部屋 3 から走り出すネズミを捕獲できます。つまり、部屋 3 にトラップを置く意味はありません。

結局、トラップはネズミがぐるぐる回る閉路上に1つあればいいです。すべての閉路を探して、各閉路での最小のトラップコストを求めて、総和をとればOK。

あとは実装するのみ。

有向グラフの閉路検出はググってもよく分からなかったのですが、今回はグラフの形がかなり単純なのでアドホックにやっていきます。

まず、グラフを無向グラフとみなして連結成分分解します。DFS を回すだけ。再帰で書くとスタックオーバーフローするのでスタックを使います。

各連結成分について次の操作をします。成分のいずれかの点にネズミを放ち、通る点の順番を記録していく。ある点 v に2回目に訪れようとしたとき、その点 v を訪れてから現在までの点が閉路です。(これ → b)

いくぶん冗長ですが、ACしたのでよし。

提出：

おわりに

B-D 完です。この結果は私のレートからすると相当ひどく、レートが暴落しました 。ABC の直後で疲れてたというのはある。

残りの3問は別の機会に。