ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

AtCoder Beginner Contest 141 E - Who Says a Pun?

AtCoder プログラミング 競技プログラミング

E - Who Says a Pun?

解説で別解として紹介されている二分探索＋ローリングハッシュで通したので書いておきます。

解法

条件を満たす長さで二分探索

「文字列 S の連続部分文字列として位置が重ならずに2回以上出現する、長さ L の文字列が存在する」ということを単に「長さ L は条件を満たす」と呼ぶことにします。

注目すべき性質として、もし長さ L が条件を満たす場合、必ず長さ L-1 も条件を満たします。単に長さ L で条件を満たしている文字列の末尾を除いた文字列を考えれば良いです。

この性質から二分探索ができるので、「長さ L をある値に固定した時、それは条件を満たすか？」という判定問題が解ければ良いことになります。

ローリングハッシュで一致判定

判定問題を解くために「ローリングハッシュ」というものを使います。これはある与えられた文字列について、その部分文字列の一致判定を大量に行いたい時に便利なアルゴリズムです。

ハッシュとは文字列などをある規則で整数（ハッシュ値）に変換したもので、2つの文字列をそれぞれ変換した整数が一致していれば文字列が一致したと見なします。与えられた文字列について前計算を行っておくことで、部分文字列のハッシュを O(1) で計算できるのがローリングハッシュです。

固定したある長さ L について、開始位置を1つずつずらしながら長さ L の部分文字列のハッシュ値を求めていきます。そして「既に登場したハッシュ値」をsetなどに入れておくことで、同じハッシュ値が2回登場した時に検出することができます。

ただし「位置が重ならない」という条件があるので、求めたハッシュ値を即座にsetに入れてはいけません。今見ている位置と重ならなくなったタイミング、具体的には S.substr(i, L) を見る直前のタイミングで S.substr(i-L, L) のハッシュ値をsetに入れると良いです。ここで S.substr(s, l) は開始位置 s 、長さ l の部分文字列を表します。

f:id:betrue12:20190916012509p:plain

この方法で、位置が重ならずに2回以上登場する長さ L の部分文字列があるかを判定できます。二分探索の判定1回の中でハッシュ値を最大で N 個setに入れるので、setの \log と二分探索の \log が付いて全体計算量は O(N(\log N)^{2}) になります。

ハッシュの衝突について

文字列をハッシュ値に変換するときに、異なる文字列を変換して同じハッシュ値になることがあり得ます。これをハッシュの「衝突」と呼びます。

もちろんその確率が十分小さくなるように工夫しますが、今回のような問題だと「最大 N 個のハッシュ値のうち1ペアでも衝突したらアウト」なので、「誕生日のパラドックス」と呼ばれる性質によりそこそこの確率で衝突します。

それを避ける方法として、パラメータが異なる複数のハッシュ値を用意しておいて、その全てが一致したら文字列が一致したと判定する方法があります。また特定のパラメータに対して衝突を起こすような恣意的な入力や、コードを見てから衝突ケースを流し込めるCodeforcesのhackなどに対策するために、乱数でパラメータを決定する場合もあります。

以下のACコードではパラメータが異なる2つのハッシュ値を計算しています。

ACコード

Submission #7525999 - AtCoder Beginner Contest 141

AtCoder Grand Contest 024 E - Sequence Growing Hard

AtCoder プログラミング 競技プログラミング

E - Sequence Growing Hard

公式解説とだいたい同じ考察を辿ったんですが、最後の計算で違うことをしたので書いておきます。

解法

要素を挿入して、辞書順でより大きくなる条件は

長さ i の数列に1つ要素を挿入して、辞書順でより大きい長さ i+1 の数列を作る方法は、ある要素の手前に、その要素より大きな要素を挿入することです。末尾に追加する場合もありますが、数列の末尾には常に 0 があるという風に思っておけば統一的に扱えます。

例えば使える数字が 1, 2, 3 であり、 \lbrace 2, 2, 1\rbrace という長さ3の数列から条件を満たす長さ4の数列を作るには

  • 1番目の要素である 2 の前に 3 を挿入する（ \lbrace 3, 2, 2, 1\rbrace）
  • 2番目の要素である 2 の前に 3 を挿入する（ \lbrace 2, 3, 2, 1\rbrace）
  • 3番目の要素である 1 の前に 2 または 3 を挿入する（ \lbrace 2, 2, 2, 1\rbrace, \lbrace 2, 2, 3, 1\rbrace）
  • 擬似的な4番目の要素である 0 の前に 1, 2, 3 のいずれかを挿入する（ \lbrace 2, 2, 1, 1\rbrace, \lbrace 2, 2, 1, 2\rbrace, \lbrace 2, 2, 1, 3\rbrace）

とすることで漏れなくダブりなく列挙することができます。この作り方だと、 \lbrace 2, 2, 2, 1\rbrace のように同じ値が連続しているところにさらに同じ値を足すような場合でも正しく扱えるのがポイントです。

以降は 0 も数列の要素として数えることにします。つまり \lbrace 2, 2, 1\rbrace という長さ3の数列は、 \lbrace 2, 2, 1, 0\rbrace という長さ4の数列として扱います。

位置関係を無視して挿入要素だけの列に

先ほど見た条件から、数列のある位置にある値を挿入できるかどうかはその直後の値との前後関係のみによって決まり、数列の中での位置や他の要素とは全く関係がないことが分かります。このことから数列の位置関係は無視してよくて、例えば

  • \lbrace 0\rbrace \to \lbrace 1, 0 \rbrace \to \lbrace 2, 1, 0\rbrace \to \lbrace 2, 1, 2, 0\rbrace \to \lbrace 2, 3, 1, 2, 0\rbrace

という数列の組は、単に各操作で挿入された要素だけを並べて

  • 0 \to 1 \to 2 \to 2 \to 3

として考えても構いません。これらの要素が数列内でどう並んでいようと、このように作られた数列に例えば要素 2 を挿入するときには、入れられる場所は 0 の直前と 1 の直前の2箇所です。

これまで「数列」と呼んできたものと混ざらないように、この挿入された要素を並べたものは「操作列」と呼ぶことにします。

実際にこの操作列によって実現できる数列の組がいくつあるかは、各操作での挿入箇所の候補数（つまり既に追加されている自分より小さい要素の個数）を全て掛け合わせることで求められます。上記の例では 1\times 2\times 2\times 4 = 16 通りあります。

挿入DPっぽい何か

次のステップですが、挿入DPっぽいことをします。つまり先程の操作列を数えていくにあたって、整数を 1 から K まで順番に入れていきます。その過程で、挿入箇所の候補数による係数も処理していきます。

次のようなDPを考えます。

  • dp\lbrack i \rbrack\lbrack j\rbrack = 整数を 1 から i まで入れ終わって、現時点での長さが j であるような操作列の通り数。ただしそれまでに発生した挿入箇所の候補数による係数は既に掛けられているものとする。

dp\lbrack i-1 \rbrack\lbrack j\rbrack から dp\lbrack i \rbrack\lbrack j+k\rbrack へ遷移するときの係数を考えます。つまり i-1 以下の数からなる長さ j の操作列に、整数 i を k 個挿入することを考えます。

操作列に挿入できる箇所は j 個の各操作の後ろなので、まず「操作列における挿入箇所の選び方」が重複組合せ _{j}H_{k} 通りあります。そしてそれぞれに対して「そのように操作列に i を挿入した時に、数列への挿入箇所の候補数によって係数が何倍されるか」が求められ、それらを全て合計したものがDPの遷移の係数になります。

具体例で確認します。 i=3, j=3, k=2 として、 2 以下の整数でできた長さ3の操作列（例えば、 0\to 2\to 1 ）が既にできているとします。この操作列に 3 を2個挿入するとき、その挿入箇所の選び方は _{3}H_{2} = 6 通り考えられます。

例えばその中で、2操作目と3操作目の後にそれぞれ挿入した 0\to 2\to 3\to 1\to 3 という操作列を考えましょう。このとき前のほうの 3 について、数列の中での挿入箇所の候補は2箇所あります。同様に後ろのほうの 3 の挿入箇所の候補は3箇所あります。つまり係数が6倍されたことになります。

このような係数を _{3}H_{2} 通り全て計算して足すと、 1\times 1 + 2\times 2 + 3\times 3 + 1\times 2 + 1\times 3 + 2\times 3 になります。つまり重複組合せとして選んだ挿入箇所の選び方それぞれについて積を計算し、全て足したものです。これがDPの遷移の係数として採用すべき値です。

係数は前計算

この係数を毎度直接求めるのは難しいですが、DPで前計算することができます。以下のように定義します。

  • sub\lbrack i \rbrack\lbrack j\rbrack = 整数 1, ..., i から重複を許して j 個選ぶ選び方それぞれについて、その積を全て合計したもの

遷移も似ていて、 sub\lbrack i-1 \rbrack\lbrack j\rbrack から sub\lbrack i \rbrack\lbrack j+k\rbrack へ遷移するときには i^{k} の係数を掛ければ良いです。

これで本命のDPに使う係数を事前に求めておけば答えを求めることができます。 i^{k} も前計算しておくと、どちらもDPの遷移は O(KN^{2}) になり間に合います。

ACコード

Submission #7456265 - AtCoder Grand Contest 024

MODの値が入力で与えられています（固定MODだと埋め込みできちゃうことが理由だと思います）が、逆元などは使わないので問題ありません。

競プロでWAが出たときのランダム入力データ生成入門

プログラミング 競技プログラミング

概要

競技プログラミングで提出コードがWAになったとき、実際に不正解となるような入力データを入手できると役に立つ場合があります。ただ多くのコンテストサイトでは、コンテスト中には入力データを見ることはできません。

そのような時に、小さめの入力データを乱数で大量生成して、提出コードと愚直解法の結果を突き合わせ、答えが一致しないものを探すという方法があります。もちろんそのようなデータを確実に得られる保証はありませんが、もし見つかればデバッグの大きな助けになります。

今回の記事はその手順を紹介します。また、生成コードの例としてC++とPythonを扱います。

手順1：愚直解法コード作成

まずは問題に対する愚直解法のコードを書きます。小さな入力データで回すので、 O(N^{3}) だろうと O(2^{N}) だろうと気にせず書きましょう。これがバグっていると破綻するので計算量よりも正しさ優先です。

C++等の場合はコンパイル時に提出コードのものと別の実行ファイル名になるようにしましょう。g++であれば -o オプションで実行ファイル名を変えられます。

手順2：乱数データ生成コード作成

乱数で入力データを生成するコードを書きます。

データサイズ・各データの値ともになるべく小さいものが見つかるほどデバッグしやすいです。私はまずは数列であれば4～10要素程度、値は20以下くらいで作っています。見つからなければ後で増やせば良いです。

乱数の作り方は言語によって異なります。以下の制約に従う入力データを標準出力に出力する、C++とPythonの実装例を示します。

生成する入力データ

制約：

  • 4 \le N \le 10
  • 1 \le a_{i} \le 20

入力形式：

N
a1 a2 ... aN

C++コード

#include <bits/stdc++.h>
using namespace std;

int main(){
    random_device seed_gen;
    mt19937_64 rnd(seed_gen());
    
    uniform_int_distribution<int> dist_N(4, 10), dist_A(1, 20);
    int N = dist_N(rnd);
    vector<int> A(N);
    for(int i=0; i<N; i++) A[i] = dist_A(rnd);

    cout << N << endl;
    for(int i=0; i<N; i++) cout << A[i] << " \n"[i==N-1];
    return 0;
}

乱数生成器まわりのコードの書き方が少し面倒なのでコピペで使ってください。ある範囲の整数をランダムに得る時は剰余演算などを使っても良いですが、明示的に範囲を指定できる uniform_int_distribution のほうがミスが少ないと思います。

" \n"[i==N-1] という書き方について少し補足しておくと、これは i==N-1 のときに改行、そうでないときにスペースとなり、結果的に数列のスペース区切り＋改行が出力されます。仕組みとしては、" \n" はスペースと改行を並べた2文字の文字列です（改行がコード上2文字なので分かりづらいですね…）。i==N-1 は true または false になるので、整数として解釈すると 1 または 0 になります。これらがインデックスとして解釈され改行またはスペースが取り出されます。

注意：Windows/MinGW環境の場合

注意点ですが、WindowsのMinGWでC++環境を作っている場合、このコードでは毎回同じ乱数になってしまうという問題があります。本来であれば random_device が実行ごとに異なる乱数シードを与えてくれるのですが、MinGWではこのシードが毎回同じになってしまうためです。

対処法ですが、今回の用途では厳密な乱雑さは必要なく、実行ごとに異なるシードになってくれればそれでいいので、現在時刻をミリ秒単位で取ってきて与えるという方法があります。先程のコードのmain先頭2行を以下に置き換えればよいです。

int64_t seed = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count();
mt19937_64 rnd(seed);

Pythonコード

import random
N = random.randint(4, 10)
A = [random.randint(1, 20) for i in range(N)]
print(N)
print(*A)

文字列の生成について

例えば英小文字をランダムに生成したい場合は、C++であれば0～25の乱数を作り 'a' に足すだけでOKです。Pythonの場合は以下のように書くとランダムな英小文字を1つ選べます。

import random
import string
c = random.choice(string.ascii_lowercase)

手順3：ひたすら回すスクリプト作成

愚直解法コードと乱数データ生成コードができたら、以下の処理を行うスクリプトを書きます。

  1. 入力データを生成する
  2. 提出コードと愚直コードをそれぞれ実行する
  3. 出力を比較し、異なっていれば終了する。同じであれば1に戻る。

このときの入力データですが、私は毎回ファイルに出力しています。どんな入力データが出ているか視覚的に分かるのと、スクリプトが止まった時に確実に入力データが保存されているので。その分毎回のファイル書き込みのぶん時間ロスがあるかもしれません。

RubyやPythonなどを使うほうが色々楽だと思いますが、実行環境がなくてもいいように一応シェルスクリプトとPowerShellの例を示しておきます（実行方法は調べてね）。各実行コマンドは使っている言語やファイル名に応じて変更してください。

※私自身は普段はRubyでやっているので、これらのスクリプトはこの記事用に急ごしらえしました。特にシェルスクリプトはWSLのbashでしか動作確認していないので、動かないところがあれば教えてください。

シェルスクリプト（Mac, Linuxなど）

while true; do
    ./make_random.out > input.txt
    ans1=$(./a.out < input.txt)
    ans2=$(./guchoku.out < input.txt)
    if [ $ans1 != $ans2 ]; then
        echo "Wrong Answer"
        echo $ans1
        echo $ans2
        exit
    fi
done

PowerShell（Windows）

while(1){
    ./make_random.exe > input.txt
    $ans1 = (Get-Content input.txt | ./a.exe)
    $ans2 = (Get-Content input.txt | ./guchoku.exe)
    if($ans1 -ne $ans2){
        Write-Host "Wrong Answer"
        Write-Host $ans1
        Write-Host $ans2
        exit
    }
}

これをしばらく回してみて、不正解データが見つかったらラッキーです。手計算したりコードの途中経過を細かく追ってみましょう。見つからなかったら、入力データの生成方法を変えてみるか潔く別の方法を取りましょう。

特殊な入力制約

制約に特殊な条件がある場合の作り方です。

数列の各要素が相異なる

既に出現したデータをsetなどで持っておいて、かぶったデータは捨てます。

順列も同じ考え方で作ることができます。コンプガチャみたいになるので要素数が多いと余計に時間が掛かりますが、小さいデータなら問題ないでしょう。

グラフが木である

Union-Findを使いましょう。頂点2つをランダムに選んだ後、その2点がまだ連結でないなら辺として採用します。クラスカル法のイメージです。

直線やウニなどの偏ったグラフは生成されにくくなります。

無向グラフが連結である

Union-Findを使って全頂点が連結になるまで辺を追加します。

頂点 s から頂点 t に到達可能である

無向グラフならUnion-Find。有向グラフなら辺を足すたびにDFSなどで確認しましょう。

グラフに自己ループや多重辺がない

頂点2つをランダムに選んだ後、その2点が異なっていることと同じ辺が既に出現していないことを確認してから辺を足します。ランダムに作っちゃうと意外と忘れがちな制約なので注意。

問題の性質による注意点

答えが偏る問題

Yes/Noやゲームの勝ち負けを判定する問題で、入力データをランダムに作ると高確率で答えがどちらか片方になってしまう…ということがあります。例えば「ある操作の繰り返しで数列 A を数列 B に一致させられるか判定せよ」という問題で、その一致条件が厳しい場合には、 A, B を独立に作るとほとんどNoになってしまいます。

こういう場合は、必ず答えがYes（起こりにくい方）になる入力を作れないか考えてみましょう。つまり先に A をランダムに作ってから、何回かランダムな操作を施して B を作れば、必ず答えはYesになるはずです。

ただ、このような問題は愚直解が書きにくい傾向があります。この生成方法であれば答えがYesと分かっているので「Yesケースだけを生成してNoと誤判定されるまで回す」ことで片側のミスは探せます。しかし逆にNoケースをYesと誤判定するミスは探せません。なかなか難しいですね。

特殊な出力の問題

構築問題の場合は出力を単純比較してもダメです。この場合は構築結果が問題の要求に合っているかを直接ジャッジするコードを書きましょう。

また小数出力で許容誤差が設定されている場合も単純比較はできません。出力結果を数値として受け取って誤差評価をすれば判定できますが、私自身は使ったことがありません。

さいごに

ランダム入力データの生成と愚直解法との突き合わせについて、色々書いてみました。

この方法は万能ではありませんが、慣れればコンテスト中でも短時間で準備できるようになります。私個人の感覚としては、コードや考察を見直している裏で回しておいて、もし見つかったら儲けものというくらいです。

そしてこの方法が取れるかどうかは問題の性質にかなり依存します。愚直解を書くのがそもそも難しかったり、本文中に書いたように特殊な入出力がある場合にはこの方法は向いていません。

この準備作業に手間取ってしまうと本末転倒なので、実戦投入する前にちょっと練習しておいたほうが良いかもしれません。あと、もちろんランダム生成だけに頼らず、偏ったケースを自分で色々作って試してみるという作業も大事です。

まずは非コンテスト時でWAの原因が分からず困ったときなどに、よかったら試してみてください。

TTPC2019 オンライン参加記

プログラミング 競技プログラミング AtCoder

f:id:betrue12:20190905012051p:plain

てんぷらさんとチームpurameriaで出場しました。オンライン参加でしたが、せっかくのチーム戦だったので記事を書こうと思います。

はじまり

ご指名いただきました。やったー！

本番まで

特に何もしていなかったのですが、コンテストでてんぷらさんが異常パフォーマンスを出す一方で私は停滞していたので内心（こんなんでチームメイトが務まるのか…）と焦っていました。

有志コンで要求されそうなちょっと強いライブラリをこっそり整えたりしていました。結局使いませんでした。

前日

チームアカウントを作ったらてんぷらさんが魔改造しました。

プラメリアとプラナリアって似てるよね。トポロジー一緒だし。

コンテスト当日

SlackのDMで相談しながらやりました。1台実装ルールがちょっと難しいかな？と思っていたけど、ちゃんと宣言して書けば意外と困りませんでした。

  • A: めり（2:00）
  • B: ぷら（4:42）
  • C: ぷら（12:39）
  • D: めり（22:33）
  • E: ぷら（25:51）

までは流れで。私がFを考えててんぷらさんがGを実装し始める…も中々解けない。

f:id:betrue12:20190905001128p:plain

Fはこの後しばらく放置されることになります。てんぷらさんがサクっとGを通していました。

  • G: ぷら（58:37）

ここで私がIを誤読（戦犯）

f:id:betrue12:20190905001436p:plain

さらに誤考察がシンクロしてしまったのでIも放置することに。Mもほぼ解けているんですがしばらく放置されます。

f:id:betrue12:20190905001615p:plain

そんなこんなでしばらくACが停滞するんですが、私がFを考えている間にてんぷらさんが上のほうをバシバシ考察していました。

f:id:betrue12:20190905001936p:plain

  • L: ぷら（122:20）

ここでついにFをAC。結局わりと地道なDPを書きました（これは公式解法が天才）

f:id:betrue12:20190905002313p:plain

  • F: めり（129:59）

てんぷらさんがOのデバッグ、私は数え上げのJを考える…も糸口が掴めない。てんぷらさんに投げようと思う（正解）

f:id:betrue12:20190905002644p:plain

  • O: ぷら（169:20）

後回しにしてた実装キュー消化とてんぷらさんの考察により、ここで怒涛のACラッシュ。

f:id:betrue12:20190905003006p:plain

f:id:betrue12:20190905003156p:plain

  • J: ぷら（199:18）
  • M: めり（202:49）
  • H: ぷら（234:33）

Mはオイラーツアー＋区間加算セグメント木でゴリゴリと。Hは終了後に提出を見に行ったら動的セグ木の二分探索で解いていました。

ここで残りは「I - I hate P」「K - サーキュレーション」「N - 瓜二つ」の3問。Iについて私が O(Q (\log R)^{2}) を思いついたけど、てんぷらさんが O(Q \log R) を思いついたのでそのまま実装してもらうことに。

f:id:betrue12:20190905003753p:plain

しかし制約が厳しい…

f:id:betrue12:20190905004135p:plain

てんぷらさんの移動中に私も小手先の改善をやってみたけど、因子 0, ..., Q-1 ごとに登場個数を数える方針だったので結局最後に O(Q \log R) かけて累乗しなきゃいけないんですよね。きびしい。

終了10分前くらいに中国剰余定理というワードが出て、ダメ元で実装RTAしたけど時間切れ。後から考えると、素冪に分解したところで P の逆元があるとは限らないから無理でした…

f:id:betrue12:20190905004707p:plain

結果

ということで結果は12完の2位でした！

知らない間にてんぷらさんが上のほうをバンバン考察していてビビりました。私の最大の貢献は簡単枠とされている（そして実際かなり通されていた）のに2人とも詰まっていたFを何とか通したことですね。それでいいのか橙コーダー。

私目線での反省はKをちゃんと考察して私が通すか、Hの実装を引き取っててんぷらさんにIを詰めてもらうか、ができればよかったかなと思います。でも1400点はたぶん取れてないでしょう…

私はチーム戦の経験はほとんどない（2回目）のですが、とても楽しかったです。通したり通してもらったりしたときにはいつも以上に嬉しいですね。

5時間15問、耐久レースかと思ったけどあっという間でした。問題も楽しかったです。運営の皆さん、てんぷらさん、ありがとうございました！

Codeforces Round #577 (Div. 2) B. Zero Array

Codeforces プログラミング 競技プログラミング

お題箱より。

Problem - 1201B - Codeforces

問題概要

n 個の正整数 a_{1}, ..., a_{n} が与えられる。これに

  • 異なる2つの要素を選び、それぞれの要素を1減らす。

という操作を繰り返すことで全ての要素を0にできるかどうか判定せよ。

制約

  • 2 \le n \le 10^{5}
  • 1 \le a_{i} \le 10^{9}

解法

この判定は競技プログラミングではしばしば登場し、もう少し難しい問題の考察の1過程として登場することもあります。必要十分条件は知識として覚えておく価値があります。

要素和 S = \sum_{i=1}^{n}a_{i} とします。この問題の条件を満たす必要十分条件は

  1. S が偶数である。
  2. \max_{i} a_{i} \le \frac{S}{2} である。

これらを2つとも満たすことです。

必要性は理解しやすいと思います。もし合計が奇数だと2ずつ減らしていって0になることは絶対ありませんし、もし最大要素が合計の半分を超えていたら、その要素と他の要素を組めるだけ組んでも最大要素が余ってしまいます。

あとは十分性です。これを証明します。

十分性の証明1

良い証明がないかググってみたのですが見つからず…私が思いついたのは数学的帰納法です。合計値 S が正の偶数であることは前提として、要素の最大値が \frac{S}{2} 以下である全ての数列が問題の条件を満たすことを証明します。

まず S = 2 から始めます。合計値が2で最大値が1以下である正整数の数列としてあり得るのは 1, 1 だけです。これは明らかに問題の条件を満たします。

次に「合計値が正の偶数 s で最大値が \frac{s}{2} 以下である全ての数列は問題の条件を満たす」という仮定のもとで、合計値が s+2 で最大値が \frac{s+2}{2} 以下である全ての数列が問題の条件を満たすことを示します。

ここで、最大値を取っている（すなわち同率1位の）要素の個数で場合分けをします。

  • 最大値を取っている要素が2個以下の場合、それらをペアに含めることで要素の最大値は必ず1減ります。この操作によって数列の合計値は s 、最大値は \frac{s+2}{2} - 1 = \frac{s}{2} 以下になります。
  • 最大値を取っている要素が3個以上の場合、そもそもこの最大値は \lfloor\frac{s+2}{3}\rfloor 以下であるはずです。全ての正の偶数 s に対してこの値は \frac{s}{2} 以下であることが不等式を評価することで示せるので、操作後の最大値も \frac{s}{2} 以下です。

つまりどちらの場合でも、適切に操作をすると合計値が s で最大値が \frac{s}{2} 以下であるような数列にすることができて、帰納法の仮定よりこれは問題の条件を満たします。

十分性の証明2

この記事を公開したら天才証明を教えてもらいました。すごい。

以上で必要性だけでなく十分性を示すことができたので、この必要十分条件を使って判定することで正解できます。

ACコード

Submission #58393368 - Codeforces

余談

この条件は今回のような数列操作だけでなくグラフの問題でもしばしば見る印象です。具体的には

  • n 頂点の無向グラフで、自己ループは許さないが多重辺はあってもよいという条件で、各頂点の次数が a_{1}, ..., a_{n} となるようなものは存在するか？

という問題と同一視することができます。多重辺を許さないという条件もつくと結構難しい（参考）のですが、許すのであれば今回示したシンプルな必要十分条件で判定ができます。このように別の形式で出た時も思い出して同一視できるようになれば、きっと役に立つでしょう。

第一回日本最強プログラマー学生選手権-予選- C - Cell Inversion

AtCoder プログラミング 競技プログラミング

C - Cell Inversion

解法

各マスの操作のされ方は、

  • 自分より左のマスとペアになって、1つの反転操作区間の終点になる
  • 自分より右のマスとペアになって、1つの反転操作区間の始点になる

のどちらかです。そして各マスがそのどちらになるかは、実は端から順番に決めていくことができます。

まず左端の1マス目を見てみます。これは必ず区間の始点になるので、左端のマスは必ず1回だけ反転します。なのでもし左端のマスの初期色が白だったら、どうやっても黒になってしまうので即アウト（0通り）です。

次に2マス目の扱い方は、「1番目のマスとペアにして終点となる」「右にあるマスとペアにして始点となる」の2択です。そして前者なら1回、後者なら2回、2番目のマスが反転します。なので2番目のマスの初期色が黒だったら前者、白だったら後者を選ぶ必要があり、終点/始点のどちらにするかが一意に決まります。

f:id:betrue12:20190825013226p:plain

この考え方は一般化できます。つまり自分より左のマスの扱いが全て決まっていれば「左から何本、閉じていない操作区間が伸びてきているか」が分かり、その偶奇と自分の初期色から、自分が終点/始点のどちらになるべきなのかが一意に決まります。

より具体的に考えましょう。 i-1 マス目までの終点/始点を決めた時点で、 i マス目に伸びてきている閉じていない操作区間が k_{i} 個あるとします。このとき、もし i マス目の初期色が白だったら、 i マス目の反転回数が偶数にならないといけないので

  • k_{i} が偶数である場合、 i マス目はこれまでの始点の「どれか」とペアにして終点となる。ここで場合の数が k_{i} 倍され、次に伸びる区間は k_{i+1} = k_{i} - 1 個。
  • k_{i} が奇数である場合、 i マス目は新しい区間の始点となる。次に伸びる区間は k_{i+1} = k_{i} + 1 個。

となります。 i マス目の初期色が黒だったら真逆です。

ここでもし k_{i} = 0 なのに i マス目の初期色が白だったら、その時点で答えが0通りになります。また最後まで見終わった時点で閉じていない操作区間が残っている場合も0通りになります。（1敗）

この「 i マス目を終点にするときに、始点のどれかを選んでペアにする」ときの選び方の数を全て掛け算したものが、ペアの作り方の数になります。今回の問題では N 個のペアを並べる順番も考慮する必要があるので、 N! を掛けると答えになります。

ACコード

Submission #7112052 - Japanese Student Championship 2019 Qualification

「みんなのプロコン」本選 A - YahooYahooYahoo

AtCoder プログラミング 競技プログラミング

お題箱より。

A - YahooYahooYahoo

解法

「編集距離DP」を知ろう

まずは「編集距離DP」なるものを説明します。2つの文字列 S, T の編集距離とは、文字列 S に以下の操作を好きな順序で行って文字列 T に一致させるための、操作回数の最小値です。

  • 置換： S の任意の1文字を選んで、それを任意の1文字に置き換える。
  • 削除： S の任意の1文字を選んで、それを取り除く。
  • 挿入： S の任意の位置に、任意の1文字を挿入する。

この3操作は今回の問題と同じですね。これは以下のようなDPで解くことができます。

  • dp\lbrack i \rbrack\lbrack j \rbrack = 文字列 S の前から i 文字目までを文字列 T の前から j 文字目までに一致させるための操作回数の最小値

このDPにおいて、文字列 S の文字をそのまま採用することと、上記の3操作を行うことは以下のような遷移で表現できます。

  • そのまま： S\lbrack i+1\rbrack が T\lbrack j+1\rbrack に一致する時に限り、 dp\lbrack i+1 \rbrack\lbrack j+1 \rbrack \leftarrow dp\lbrack i \rbrack\lbrack j \rbrack
  • 置換： dp\lbrack i+1 \rbrack\lbrack j+1 \rbrack \leftarrow dp\lbrack i \rbrack\lbrack j \rbrack + 1
  • 削除： dp\lbrack i+1 \rbrack\lbrack j \rbrack \leftarrow dp\lbrack i \rbrack\lbrack j \rbrack + 1
  • 挿入： dp\lbrack i \rbrack\lbrack j+1 \rbrack \leftarrow dp\lbrack i \rbrack\lbrack j \rbrack + 1

遷移は全て「より小さければ更新」です。この計算量は O(|S|\times |T|) です。

「yahoo」のループを考えよう

さて今回の問題です。目標とする文字列は yahoo の繰り返しで、問題文の上では T の長さがどこまでも大きくなる可能性があります。さらに、 |S| \le 10^{5} という制約から2乗オーダーのDPは間に合いそうにありません。

しかし逆に言うと、 yahoo は何周繰り返していようと条件判定には関係ないので、周回数の情報は忘れてしまうことができます。つまり状態定義はこうです。

  • dp\lbrack i \rbrack\lbrack j \rbrack = 文字列 S の前から i 文字目までを、「yahoo を0周以上繰り返した後、末尾に yahoo の途中まで j 文字が中途半端に付いているような文字列」にするための操作回数の最小値

このDPの遷移は先ほどの編集距離DPとほぼ同じです。相違点は j は 0, 1, 2, 3, 4 の値しか取らず、 4 の次は 0 に戻ります。これは末尾の yaho の後に o を付けることに対応します。

ここで少し注意すべきは「挿入」の遷移で、 dp\lbrack i \rbrack\lbrack j+1 \rbrack \leftarrow dp\lbrack i \rbrack\lbrack j \rbrack + 1 と遷移するため同じ i での遷移となります。この遷移はどこかで止めないと無限に回りますが、1周以上の文字列を連続で挿入することは無駄なので、それぞれの dp\lbrack i \rbrack\lbrack j \rbrack からの挿入の遷移として1～4文字の挿入だけを考えれば十分です。

このときの具体的実装として、例えば以下のような遷移が素直です。

  • 遷移元の dp\lbrack i \rbrack\lbrack j \rbrack それぞれについて挿入文字数 k=1, ..., 4 を全部試し、 dp\lbrack i \rbrack\lbrack (j+k)\% 5 \rbrack \leftarrow dp\lbrack i \rbrack\lbrack j \rbrack + k と遷移する

この他に、公式解説のように「遷移を2周回す」という手があります。これは

  • dp\lbrack i \rbrack\lbrack 1 \rbrack \leftarrow dp\lbrack i \rbrack\lbrack 0 \rbrack + 1
  • dp\lbrack i \rbrack\lbrack 2 \rbrack \leftarrow dp\lbrack i \rbrack\lbrack 1 \rbrack + 1
  • ...
  • dp\lbrack i \rbrack\lbrack 0 \rbrack \leftarrow dp\lbrack i \rbrack\lbrack 4 \rbrack + 1

という遷移を順番に回していくもので、

  • 0\to 1\to 2\to 3\to 4\to 0\to 1\to 2\to 3

と2周回すことで先ほどの j = 0, 1, ..., 4 から k=1, ..., 4 文字を挿入する操作が全パターン含まれるようになります。

どちらにせよ、yahoo の文字数5を定数とするならばこのDPは O(|S|) で動作し、 dp\lbrack |S| \rbrack\lbrack 0 \rbrack として答えを求めることが出来ます。

ACコード

遷移先などの候補として「ループして自分より前のインデックスに遷移することはあるが、1周は超えない」という状況になったときには、文字列や数列を2倍して遷移を考えてみるとスマートに処理できることが多いです。例えばこの問題などもそうですね。