ARMERIA

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

Codeforces Round #587 (Div. 3) E2. Numerical Sequence (hard version)

Problem - E2 - Codeforces

問題概要

正整数  x に対して、 1, 2, .., x を十進表記で書いたものをこの順に連結した文字列を  s(x) とする。そして、 s(1), s(2), ... をこの順に連結した無限の長さの文字列を考える。与えられる  q 個の整数  k_{i} に対して、この文字列の  k_{i} 番目の文字を答えよ。

制約

  •  1 \le q \le 500
  •  1 \le k_{i} \le 10^{18}

解法

各クエリに対する  k_{i} を単に  k と記します。また、問題概要に記したように文字列  s(x) を定めます。

まず、 k 番目の文字がどの  s(x) に属するか調べる必要があります。これは  s(1), s(2), ..., s(x) の長さの合計を  S(x) とすると、 S(x) \ge k を満たす最小の  x として求められるので二分探索できます。判定問題を解くために、ある固定した値  x に対する  S(x) の効率的な求め方を考えましょう。

 x の桁数を  D として、 1 \le d \le D なる桁数  d を考えます。 1, ..., x に含まれる  d 桁の値を抜き出します。この最小値、最大値、値の個数をそれぞれ  m_{d}, M_{d}, n_{d} と書くことにすると、これらは以下のように計算できます。

  •  m_{d} = 10^{d-1}
  •  M_{d} = \min(10^{d}-1, x)
  •  n_{d} = M_{d} - m_{d} + 1

やりたいことは文字列  s(m_{d}), ..., s(M_{d}) の長さ合計を求めることです。これを  1 \le d \le D について合計したものが  S(x) になります。

ある  d についての計算を、さらに分けて考えます。 1 \le e \le d なる桁数  e について、文字列  s(m_{d}), ..., s(M_{d}) の中に  e 桁の整数が合計でいくつ入っているかを求めます。

  •  e \lt d のとき、 s(m_{d}), ..., s(M_{d}) それぞれに  e 桁の整数全てが1つずつ含まれています。 e 桁の整数は全部で  9\times 10^{e-1} 個あるので、合計で  9\times 10^{e-1} \times n_{d} 個の整数があります。
  •  e = d のとき、 e 桁の整数は  s(m_{d}) に1個、 s(m_{d}+1) に2個、...、 s(M_{d}) n_{d} 個含まれています。つまり等差数列の公式から、合計で  \frac{1}{2}n_{d}(n_{d}+1) 個の整数があります。

これに  e を掛けたものを全ての  1 \le e \le d について合計すると  s(m_{d}), ..., s(M_{d}) の長さ合計が求められます。それをさらに  1 \le d \le D について合計したものが  S(x) になります。

これを用いて二分探索することで、 k 番目の文字がどの  s(x) に属するか求められました。ここで求められた値を引き続き  x と記します。ここで  k^{\prime} = k - S(x-1) とすると、求めたいのは  s(x) k^{\prime} 番目の文字です。

ここで知りたいのは  s(x) として並べられた整数  1, 2, ..., x のうちどれに  k^{\prime} 番目の文字が含まれているかで、これはまたしても二分探索することで求められます。つまり  k^{\prime} 番目の文字を含むのは、  |s(y)| \ge k^{\prime} を満たす最小の  y です。

 |s(y)| の計算方法は先ほどの  S(x) に比べると簡単で、 1, ..., y の中に  d 桁の数がいくつ含まれるかを同じように計算し、それに  d を掛けたものを全て合計すれば良いです。

これで  y も特定できれば、その十進表記における  k^{\prime} - |s(y-1)| 番目の数字が求める文字です。

(プレテスト)ACコード

※記事作成時点ではシステスが終わっていませんが…

Submission #61031718 - Codeforces

計算量ですが、 q が小さいので10の冪乗などの前計算などをしておかなくても余裕があります。二分探索・桁数  d, e の全探索・10の冪乗で  O(\log k) が4つくらい付いていると思います。

またオーバーフローに注意する必要があります。二分探索の初期値としてあまり大きな値を取りすぎると  S(x) の値がオーバーフローしますが、実際に計算すると  S(10^{9}) がだいたい  4.39 \times 10^{18} になって  k の制約を超えるので、 x の上側の初期値を  10^{9} としておくと良いでしょう。

AtCoder Grand Contest 038 B - Sorting a Segment

B - Sorting a Segment

公式解説と少し違う方法で解いたので記録。

解法

ある長さ  K区間を昇順に並び替えた時に、値が変更される最左のインデックスを  l 、最右のインデックスを  r とします。この時操作の結果は、閉区間  \lbrack l, r \rbrack 内の要素を昇順に並び替えたものとなります。つまりこの区間  \lbrack l, r \rbrack は「操作によって実質的に並び替えられたのはどの区間」というものを表します。

f:id:betrue12:20190922003715p:plain

求めたい答えは、 N-K+1 通りの全ての操作パターンについてこのようなインデックスの組  \lbrace l, r \rbrace を求めた時の、それらの相異なる要素数となります。ただし1つも要素が変更されない場合もあるので、その場合は適当に  \lbrace l, r \rbrace = \lbrace -1, -1 \rbrace などとしておきます。(開区間と紛らわしいので値の組は  \lbrace \cdot, \cdot \rbrace と表記します)

では各操作パターンについて、長さ  K区間  \lbrack i, i+K-1\rbrack を操作したときの  l, r はどのように求めれば良いでしょうか。左右同様の方法で求められるので  l について考えます。

左端から見て、要素が変更されていない区間  \lbrack i, l-1\rbrack に注目します。この区間に属する全ての値  j\in \lbrack i, l-1\rbrack が満たすべき条件は、 P_{j} より小さい要素が区間  \lbrack j, i+K-1\rbrack に存在しないことです。

f:id:betrue12:20190922003725p:plain

このような条件を満たす区間のうち最も長いものを求めることができれば、その区間 \lbrack i, l-1\rbrack として  l の値を求めることができます。そしてこれは二分探索で求めることができます。

具体的には、あらかじめ各インデックス  j について「 P_{j} より小さい要素が右側で次に現れるのはどこか」を求めておきます(存在しない場合は適当に大きな数とします)。この値を  x_{j} としましょう。

そうすると区間  \lbrack i, l-1\rbrack の値が変更されない必要十分条件は、区間内の全ての  j について  x_{j}区間  \lbrack j, i+K-1\rbrack の外にあること、つまり

 \displaystyle\min_{j\in \lbrack i, l-1\rbrack} x_{j} \gt i+K-1

が成立することなので、 x_{j} の値をSparse Tableやセグメント木などに入れておくことで効率的にこの判定が出来て、二分探索をすることができます。

また  x_{j} の値も、 P_{i} そのものをSparse Tableに入れて二分探索したり、 P_{i} を右から見ていきながらセグメント木に入れていくことで求めることができます。

 r についても、左/右や小さい/大きいを逆にして考えると同様に計算できます。これで各操作に対する  l, r の値が求められるので、 値の組  \lbrace l, r \rbrace をset等に入れて相異なる要素数を数えることで答えを求めることが出来ます。

ACコード

Submission #7637418 - AtCoder Grand Contest 038

AtCoder Beginner Contest 141 E - Who Says a Pun?

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

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 のほうがミスが少ないと思います。

注意:Windows/MinGW環境の場合

注意点ですが、WindowsMinGWC++環境を作っている場合、このコードでは毎回同じ乱数になってしまうという問題があります。本来であれば 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に戻る。

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

RubyPythonなどを使うほうが色々楽だと思いますが、実行環境がなくてもいいように一応シェルスクリプト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

PowerShellWindows

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 オンライン参加記

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

お題箱より。

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} となるようなものは存在するか?

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