2018-10-24

ARC091 F - Strange Nim

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

F - Strange Nim

面白い問題だったので記録。公式解説とはちょっと違う解法。

考察・解法

実験と観察

山同士は相互に干渉しないので、それぞれの山のGrundy数を求めることが目的になる。

注目している1つの山について、残っている石の数を $X$ 、その山が持つパラメータ $A_{i}, K_{i}$ を単に $A, K$ 、Grundy数を $G(X)$ と記す。「もう操作できない状態」のGrundy数が0であるとして、

$X \lt K$ のとき、 $G(X) = 0$ 。
$X \ge K$ のとき、 $G(X)$ は $G(X - \lfloor\frac{X}{K}\rfloor)$ から $G(X - 1)$ までに登場しない最小の非負整数。

である。

これがどのような値になるか実験してみる。そうすると、

$\lfloor\frac{X}{K}\rfloor$ が変化しない範囲では、 $G(X)$ は $0$ から $\lfloor\frac{X}{K}\rfloor$ までの値がある順序で繰り返される。例えば $X = 30, ..., 39$ の範囲では、 $G(X)$ は $3, 1, 0, 2$ の繰り返しになっている。
$X$ が $K$ の倍数のとき $G(X) = \frac{X}{K}$ となり、それまでの順序のある位置に $\frac{X}{K}$ が「挿入」される形で、それ以降はまた値が繰り返される。

というような性質がある。この性質を使えば、いくつかの方法でGrundy数が求められそうである。

求め方1：再帰で求める

1つ目の方法は、繰り返しの性質を用いた再帰である。 $X$ が $K$ の倍数でないとき、以下のように考えることができる。

f:id:betrue12:20181024211331p:plain

この考え方から、 $X$ が $K$ の倍数でないとき $G(X) = G(X - \frac{X}{K} - 1)$ であることが分かる。 $X = A$ から始めて、これを $X \lt K$ になるか $X$ が $K$ の倍数になるまで再帰的に繰り返すことで、 $G(X)$ を求めることができる。

この操作1回で、 $X$ はおよそ $\frac{K-1}{K}$ 倍になる。 $K$ が小さいとこれで十分間に合うが、 $K$ が大きいときにはいくら指数的に減っていくとはいえスピードが遅すぎて間に合わない。

計算量はおそらく $O(\log(\frac{A}{K}) / \log(\frac{K}{K-1}))$ であり、 $O$ の中身を単純計算すると $A = 10^{9}, K = 10^{5}$ のときにおよそ $9.2 \times 10^{5}$ となる。後で $N = 200$ が掛かることを考えると、 $K \le 10^{5}$ くらいが限度だろうと思われる。

※公式解法では、後述の「求め方2」は使わず、この求め方1をベースにさらに高速化の工夫をしている。

求め方2：順序への「挿入」をシミュレートする

求め方1の欠点を補うため、 $K$ が大きい時に使えるGrundy数の求め方を考える。

先述のように、 $G(X)$ の遷移はある順序で繰り返され、 $X$ が $K$ の倍数になるごとに、その順序のある位置に新しい値が挿入される。これを全てシミュレートしてやることでも $G(X)$ を求めることができる。

やりたいのは、数列のどこかのインデックス（ $k$ 番目）へ値を挿入すること。そして、最後にどこかのインデックスの値を取ること。これは平衡二分木を使えば、要素数を $a$ として $O(\log a)$ で実現できる。

この操作は全部でおよそ $\frac{A}{K}$ 回行われるので、計算量は $O(\frac{A}{K} \log( \frac{A}{K}))$ である。これは求め方1とは逆に $K$ が大きいほど計算量が少なくなり、 $K \ge 10^{5}$ くらいであれば十分高速である。

解法まとめ

山ごとにGrundy数を求める。このとき、の値によって2通りの求め方を使い分ける。
1. $K$ が小さい場合、再帰で求める。
2. $K$ が大きい場合、順列への値の挿入を平衡二分木でシミュレートして求める。
全ての山のGrundy数のXORを取り、勝敗を判定する。

ACコード

Submission #3462224 - AtCoder Regular Contest 091

求め方を切り替える閾値の設定が難しく、 $10^{4}$ で分けた場合は TLEした。求め方1は処理がとても単純なので定数倍が軽く、求め方2では平衡二分木の処理が重いので、単純に $O$ の中身を計算して比較したときの閾値より高めにするのがよい。想定解法ではないので、どう調整しても通らないときは仕方がない。

さいごに

一番最後はデータ構造で「殴って」しまったけれど、Grundy数の一見不規則に見えて実は美しい規則性、計算量の落とし方の工夫、ともに面白い問題だった。

2018-10-20

九州大学プログラミングコンテスト2018　参加記録＆解説（A～F）

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

九州大学プログラミングコンテスト2018 - AtCoder

6完で31位でした。正答数は良い感じですが、色々バグらせました…

f:id:betrue12:20181020180500p:plain

A - QUPC

解法

$ans = 4N + 2010$ を計算すればよいです。

ACコード

Submission #3436129 - 九州大学プログラミングコンテスト2018

B - Tapu & Tapi

（Ruby）B - Tapu & Tapi

解法

値が大きい方の硬貨から見ていきます。

100円玉が偶数の場合、それを普通に分ければよいです。もし奇数の場合は、余った100円玉の相手になるように、小さい硬貨から100円を借りてこなければいけません。

10円玉についても同様にします。最終的に1円玉が足りて、かつ偶数であればよいです。

ACコード

（Ruby）Submission #3436312 - 九州大学プログラミングコンテスト2018

C - Ito Campus

解法の流れとしては、まずイノシシまで $X$ 歩以内に到達可能な点を求めます。その後、うしくんさんがそれらの点を避けてゴールにたどり着く最小距離を求めます。これらはともにBFSで求めることができます。

まずイノシシについて考えます。「イノシシまで $X$ 歩」とはつまり「イノシシから $X$ 歩」であるため、イノシシをBFSの始点とします。イノシシは複数頭いるため、BFSを複数の始点から開始する必要があります。といっても、最初にキューに入れる点を複数にすればそれでOKです。

同時並行で探索が進み、あちこちが更新されていくので少し違和感があるかもしれません。イメージとしては、1つの始点から探索を広げるのではなく、「距離が0の点（始点）を設定する」→「その隣を見て、距離が1の点を確定させる」→「その隣を見て、距離が2の点を確定させる」…という全体の流れを意識するといいと思います。

イノシシの処理ができたら、イノシシまで $X$ 歩以内の点を通行不可扱いにして、うしくんさんのBFSをやります。

ACコード

（C++）Submission #3437495 - 九州大学プログラミングコンテスト2018

このコードでは、イノシシまでの最短距離を全て計算してしまい、うしくんさんの移動の際にその距離を参照しています。実際に必要なのは「 $X$ 歩以内かどうか」の情報だけなので、これを true/false のフラグで管理する、 $X$ 歩以内の場所を # で埋める、などの実装も可能です。

D - Novelist

解法

「時刻 $t$ に王都にいる（依頼を開始できる）状態であるとき、それまでに完了した依頼の最大数」を $dp\lbrack t \rbrack$ とします。初期状態は $dp\lbrack 0 \rbrack = 0$ です。

時刻 $t$ に王都にいて、それ以降に王都で受けられる依頼を受けることを考えます。そのときの動きとして、次のようなものが考えられます。

f:id:betrue12:20181020190939p:plain

依頼をこなしたあと、戻りの依頼が存在しない場合、合計で $dp\lbrack t \rbrack + 1$ 個の依頼をこなして依頼終了となる。
依頼を2つこなして王都に戻ってこられる場合、帰りの依頼の終了時刻を $t^{\prime}$ として、 $dp\lbrack t^{\prime} + 1 \rbrack \leftarrow \max(dp\lbrack t^{\prime} + 1 \rbrack, dp\lbrack t \rbrack + 2)$ とすることができる。

また、もちろん「時刻 $t$ に依頼を受けない」という選択もできます。その場合は次の時刻に持ち越されるため、 $dp\lbrack t + 1 \rbrack \leftarrow \max(dp\lbrack t + 1 \rbrack, dp\lbrack t \rbrack)$ となります。

このような「配るDP」をすることで解を求めることができますが…時刻は $10^{9}$ オーダーで普通に扱うことはできないので、座標圧縮をします。王都を基準にしたDPを考えているため、王都から受けられる依頼の開始時刻、つまり $A_{i}$ を座標点として採用します。

DPの遷移においては

王都から依頼を受けて都市 $X$ に到着後、都市 $X$ で受けられる依頼のうち最も早いものはどれか
その依頼を受けて王都に戻ってきたあと、次に王都で依頼を受けられる最も早い時刻はいつか

が必要になりますが、これらはともに二分探索を使って求めることができます。

最終的な解は $dp\lbrack \infty \rbrack$ とは限らず、王都以外の都市で依頼を終えることもあるため、遷移の中で逐次更新をしていくとよいです。

ACコード

（C++）Submission #3438131 - 九州大学プログラミングコンテスト2018

終了後、区間スケジューリングとして見ると楽だという話を見てなるほどと思いました。あまりやっていることは変わりませんが、明示的な座標圧縮も必要ないですし、そちらのほうが楽かもしれません…

E - Treeone

解法

各 $A_{i}$ について、「 $A_{i}$ を含む区間で、合計が0になるものはいくつあるか」を求めます。その数が最も大きい要素の値を変更するのが最適です。変更する際に他の区間に影響を与えてしまわないか心配ですが、5000兆とかの極端な数に変更しておけば他の区間の合計を0にしてしまうことはありません。

ということで、「 $A_{i}$ を含む区間で、合計が0になるものはいくつあるか」の求め方ですが…区間がいくつかあり、各要素について「その要素を含んでいる区間がいくつあるか」というものを求めたいので、いもす法が使えそうです。ただ、合計が0になる区間は最大で $O(N^{2})$ 個あり、これをバラバラに扱っていると間に合いません。

いもす法は、（インデックスのとり方にもよりますが）区間ごとに始点の位置に+1して、終点の次の位置に-1して、最後に累積和を取る方法です。そのため、各位置について「ここが始点となる区間はいくつあるか？」「ここが終点となる区間はいくつあるか？」を求めることができれば、+1/-1の計算をまとめてすることができます。

「ここが終点となる、合計が0である区間はいくつあるか？」を求めるには、左から累積和を求めていけばよいです。お馴染みの「Zero-Sum Ranges」です。

f:id:betrue12:20181020195935p:plain

「ここが始点となる、合計が0である区間はいくつあるか？」を求めるには、同じことを右からやればよいです。

これらを求め、いもす法で「その要素を含んでいる区間がいくつあるか」を復元し、その最大値を合計が0の総区間数から引いてやれば答えが求められます。

ACコード

（C++）Submission #3438450 - 九州大学プログラミングコンテスト2018

F - Team Making

解法

$N$ がとても小さいので、bitDPなどの解法が使えそうです。「 $N$ 人のうち集合 $S$ に属する人を使ってできるグループの分け方」を $dp\lbrack S\rbrack$ とするDPをします。

$dp\lbrack S\rbrack$ を求める際に、 $S$ に含まれている人からグループを1つ作る方法を考えます。そのグループを $T$ とすると、 $dp\lbrack S - T\rbrack$ を使って遷移を計算することができます。

ただしグループの取り方全てを考えてしまうと、同じ分け方を何度も数えてしまうので、そうならないようにルールを決めます。具体的には、「 $S$ に含まれる人のうち番号の若い人は必ず使う」というルールです。常にこのルールを守っていけば、同じ分け方を何度も数えることはありません。

$S$ に含まれる人のうち一番若い番号を $i$ とすると、作られるグループは

$i$ 1人だけのグループ（ $O(1)$ 個）
$i$ とあと1人のグループで、レート条件を満たすもの（ $O(N)$ 個）
$i$ とあと2人のグループで、レート条件を満たすもの（ $O(N^{2})$ 個）

で、集合1つにつき $O(N^{2})$ で遷移を計算できます。

全体計算量が $O(N^{2} \times 2^{N})$ となり、単純計算で $18^{2} \times 2^{18} = 84934656$ です。億を超えていないので、1つ1つの計算が軽ければ間に合います。

ACコード

Submission #3438778 - 九州大学プログラミングコンテスト2018

ソートしておくと少しだけ枝刈りができたり、各レートから予め $K$ を引いておくと平均が $K$ 以下かどうかの判定が楽だったり、ちょっとしたテクニックはあります。

2018-10-19

Educational Codeforces Round 52 G. Fibonacci Suffix

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

Problem - G - Codeforces

面白い問題を自力で通せたので記録。

問題概要

文字列の列 $F(i)$ を、漸化式

$F(0) =$ "0" $, F(1) =$ "1" $, F(i) = F(i-2) + F(i-1)$

で定義する。この $+$ は文字列の結合を示す。

整数 $n, m, k$ が与えられる。 $F(n)$ の接尾辞を辞書順に並べた時、 $k$ 番目に該当する文字列の先頭 $m$ 文字を求めよ。（ただし、その文字列の長さが $m$ 未満の場合は文字列全体を出力せよ。）

制約

$1 \le n, m \le 200$
$1 \le k \le 10^{18}$
$k$ は $F(n)$ の長さを超えない

考察・解法

方針を考える

タイトルにもあるように漸化式がフィボナッチ数列のようになっていて、 $F(i)$ の長さは通常の意味でのフィボナッチ数となる。 $n=200$ のときを計算してみると $|F(n)| \simeq 4.54\times 10^{41}$ となり非常に大きい数となる。

注目すべきは $m \le 200$ であり、要求されているのは高々200文字なので、接尾辞のうち201文字目以降は区別する必要がない。そのため「先頭200文字が○○○になるような接尾辞はいくつあるか？」という分布のようなものを計算できれば、それを辞書順で前から加算し、累積 $k$ 個以上になった時点での文字列が答えである。

接尾辞を効率的に数える

01 で構成される200文字の文字列は最悪 $2^{200}$ 通りあるが、 $F(i)$ には同じ文字列が繰り返し含まれているため、パターン数はぐっと少なくなる。

具体的には、 $i$ を適当に決めて $A = F(i-1), B = F(i)$ とすると、 $F(i)$ 以降の文字列は全て $A, B$ を並べたものになる。そのため以下のような方針で、接尾辞の先頭200文字の分布を求めることができる。

$A = F(i-1), B = F(i)$ がおよそ200文字になるように $i$ を適当に決める。
それ以降の $F(i)$ で、文字列の連結も含めて $A, B$ の組み合わせとして登場し得るパターンを列挙する。
それぞれのパターンで登場する200文字以内の部分文字列と、その登場回数を計算し、全て合計する。

$A, B$ として固定するものとしては、 $|F(11)| = 144, |F(12)| = 233$ なのでこれを使う。

$F(n)$ 内に存在する「200文字以内の部分文字列」の登場パターンとして考慮すべきは、以下のものである。

文字列の最後に存在する $B$ の接尾辞1～199文字
$B$ の200文字の部分文字列
$BA$ の200文字の部分文字列のうち、前の $B$ を199文字以下含むもの
$BB$ の200文字の部分文字列のうち、前の $B$ を1～199文字含むもの
$ABA$ の200文字の部分文字列のうち、最初の $A$ を1文字以上含むもの

漏れとダブリがないよう、そのパターンが $F(n)$ にいくつ登場するかの回数も含めて計算していく。各パターンの登場回数はフィボナッチ数に似た漸化式で表せるので前計算しておく。

これで、接尾辞の先頭200文字としてあり得るものについて、それが $F(n)$ にいくつ登場するかが数えられる。実際にやってみると登場する文字列はちょうど400種類になった（！？）。十分扱えそうな個数である。

「 $k$ 番目」を求める

分布が求められたので、実際に $k$ 番目を求めていく。…といっても、高々200文字の文字列が400個なので、辞書順でソートして前から見ていけば十分間に合う。

最初はTrie木を使うと速いかなと思ってそっちを使ったが、mapに順序関係を保ってもらった状態で個数をカウントし、前から見ていったほうが実行時間も短かった。

ACコード

map Submission #44541587 - Codeforces
Trie木 Submission #44495360 - Codeforces

実装上の注意点としては、

$A = F(11), B = F(12)$ として $A, B$ の組み合わせだけで考えた場合、 $n \le 11$ のときはこのやり方では答えが出ない。ただその場合は接尾辞の総数が少ないので、普通に全列挙＆ソートして直接 $k$ 番目を取ってしまえばよい。
数え上げた結果がものすごく大きな数になり得るので注意。 $10^{18}$ を超える個数は数えても無意味なので、個数を足し算するごとに「結果が $10^{18}$ を超えていたら $10^{18}$ にする」などの処理をしておけばOK。

さいごに

えでゅふぉの最終問は、こういうキッチリ考察して地道に解いていく問題が多いように思う。

公式解説も似たようなことをしてそうなんだけど、書いてあることが難しい…

2018-10-17

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

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

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になってしまうと異なる点を指定できなくなりますが、その心配はないです。

距離が1の場合、整数座標を2つ指定して分類直線を引くのが少しだけ難しそうに見えますが、以下のようにすればよいです。 $y=0$ 上でやらなかったのは、ここで両側の点を使いたかったからです。

f:id:betrue12:20181017221832p:plain

ACコード

（C++）Submission #44443898 - Codeforces

本番は少し違うコードで通しました。距離が1になる場合の対応方法は、いろいろやり方があると思います。

さいごに

確かにこの3問は解きやすく、速解きが求められるのも納得です。D問題以降、AC人数がガタ落ちする感じでした。

2018-10-15

CODE FESTIVAL 2018 qual B　参加記録＆解説（A～D）

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

CODE FESTIVAL 2018 qual B - AtCoder

前のこどふぉに出ていたので5分遅刻で参加。結果は108位でした…

f:id:betrue12:20181015020705p:plain

A～Dを振り返ります。今回は公式解説がかなり丁寧なので、それを少し補足するような感じで短めに書きます。

A - Probability of Participation

解法

1以上100以下の整数のうち、 $N$ で割り切れるものは $\lfloor\frac{100}{N}\rfloor$ 個です。これを100から引いたものが答えです。

ACコード

（Ruby）Submission #3406469 - CODE FESTIVAL 2018 qual B

B - Tensai

解法

顔が一番面白い人に毎回トレーニングをしてもらうのが最適です。実装方法はいくつかありますが

字の上手さと顔の面白さのペアを顔の面白さ基準でソートし、一番顔が面白い人の字の上手さを $X$ 増加させ、スコアを計算する
与えられた入力のまま普通にスコアを計算したあと、 $(顔の面白さの最大値) \times X$ を加算する

などをすればよいです。

ACコード

（Ruby）Submission #3406640 - CODE FESTIVAL 2018 qual B

C - Special Cake for CODE FESTIVAL

解法

答えは公式解説に書いてあるとおりです。ので、ちょっと思考の流れを書きます。

制約を確認すると、マスの数は最大100万になり、 X を置いてもよいマスの数はその5分の1＋ちょっとです。そのため、ある程度答えが規則的になるだろうという予想から、「ある行について、5マスごとに1個 X を置いてみる」ということを考えます。

5マスごとに X を置くと、間には X のないマスが4つあります。これら全てをカバーしなければいけません。

f:id:betrue12:20181015201339j:plain

一番左と一番右は、その行の中で X に接しているため、既にカバーできています。残り2つは上と下に助けてもらいたいので、それぞれ上と下に置きます。このような形を作れれば、X の間の4マスが全てカバーできます。

この形を繰り返していくと、公式解説のような模様ができます。

ACコード

（Ruby）Submission #3407445 - CODE FESTIVAL 2018 qual B

D - Sushi Restaurant

解法

この記事はD問題まで書きますが、もちろんこれが4問の中ではダントツに重いです。ただこの問題も公式解説が丁寧です。そちらで丁寧に説明されていることはこの記事では端折っていきます。

「 $i$ 番目に空腹度が小さい人」に着目する

参加者の空腹度が確率で決まったあと、与えられた寿司がどのように割り振られるか考えます。このとき、1番空腹度が小さい人は1番寿司が少ない皿を、2番目に空腹度が小さい人は2番目に寿司が少ない皿を…というふうに寿司が割り振られます。

このため、「 $i$ 番目に寿司が少ない皿（つまり、 $i$ 番目に空腹度が小さい人が取る皿）は、寿司をいくつにするのが最適か？」ということを、各皿ごとに独立に考えることができます。ということで、「 $i$ 番目に空腹度が小さい人」の空腹度がどのような分布になっているかを知りたくなります。

もしこの確率分布が求められている場合、最適な寿司の数はいくつになるでしょうか。ここで、「絶対値で定義された誤差の合計を最小にするのは、分布の中央値である」という知識が使えます。これは少し前のABC/ARCでも登場した知識です。以前の問題のように確率の概念がない場合は小さい方から数えて $\frac{N}{2}$ 個目の要素を採用していましたが、今回のようにそれぞれの要素に確率が付いている場合も似たように考えることができて、「確率の累積値が $\frac{1}{2}$ であるところの要素」が中央値となります。

f:id:betrue12:20181015210335p:plain

この値は空腹度の候補 $x_{j}$ のうちどれかになっているので、もちろん整数です。そのまま寿司の個数として採用することができます。

確率分布を求める

今までの話で、「 $i$ 番目に空腹度が小さい人」の空腹度の分布が求められれば答えが求められる、ということが分かりました。次はこの確率分布を求めます。

$i$ 番目に空腹度が小さい人の空腹度が、 $j$ 番目に小さい候補である $x_{j}$ となる確率を考えてみます。なんとなく「この人より空腹度が小さい人が $i-1$ 人、空腹度が大きい人が $N-i$ 人いて…」みたいなことを考えたくなりますが、こうすると空腹度 $x_{j}$ の人が複数人いたときに困ります。

もう一つ「空腹度 $x_{j}$ の人が全部で $k$ 人いるときの…」という条件を付け足し、 $k$ を全探索すれば確率が求められないことはないです。ただこうすると、 $i, j, k$ のループで $O(N^{2}M)$ の計算が必要で間に合いません。

このようなときに使える手段が、「 $i$ 番目に空腹度が小さい人の空腹度が $x_{j}$ 以上となる確率」を考えることです。これが求められれば、順次差分を取ることで目的の確率分布が求められます。

そしてこの値は、「ぴったり」を求めるよりも求めやすいです。具体的には、 $x_{j}$ より小さい空腹度を持つ人の人数が $0, ..., i-1$ 人のどれかである確率を求めることになります。これも結局全探索のオーダーが1つ増えそうに見えますが…

$i$ 番目に空腹度が小さい人の空腹度が $x_{j}$ 以上となる： $x_{j}$ より小さい空腹度を持つ人の人数が $0, ..., i-1$ 人のどれかである
$i+1$ 番目に空腹度が小さい人の空腹度が $x_{j}$ 以上となる： $x_{j}$ より小さい空腹度を持つ人の人数が $0, ..., i$ 人のどれかである

こうして並べてみると、「 $i$ 番目」のときの結果に要素を1つ足すだけで「 $i+1$ 番目」の結果になり、差分更新で求めることができるのです。

あとは要素1つが現実的な時間で求められればよいです。「 $x_{j}$ より小さい空腹度を持つ人の人数が $i$ 人である」という確率は、 $x_{j}$ より小さい空腹度になる確率を $p$ として

$_{N}C_{i} {p}^{i} (1-p)^{N-i}$

と求められます。コンビネーションは前計算、 $p$ も各 $x_{j}$ が出る確率 $\frac{p_{j}}{q}$ の累積和なので前計算。累乗の部分は繰り返し二乗法で $O(\log N)$ に落ちるので、十分現実的な時間で求められます。

解法まとめ

ということで、まとめです。

$\frac{p_{j}}{q}$ の累積和およびコンビネーションを前計算しておく。
前計算の値と差分更新のテクニックを利用して、「 $i$ 番目に空腹度が小さい人の空腹度が $x_{j}$ 以上となる確率」を求める。ここから差分を取ることで、「以上」を外したものを求める。
この確率分布の中央値を求めて、各皿ごとに最適な寿司の数を決め、答えを計算する。

ACコード

Submission #3410686 - CODE FESTIVAL 2018 qual B

誤差がかなり積もってしまうので、double よりも精度の高い long double を用いました。精度が良い分、計算時間とメモリの占有量は大きくなるのですが、この問題の場合はどちらも余裕があるので大丈夫でした。

公式解説では対数に変換して計算する方法が紹介されています。対数にすると累乗が掛け算になるので、それで $O(\log N)$ が計算量に付いていないのだと思います…たぶん。

さいごに

D, Eは全体的にAC者がものすごく少なかったですね。私も通せませんでしたが、Dはしっかり復習できたと思います。Eも理解しなければ…

2018-10-14

AGC028 参加記録＆解説（A～C）

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

AtCoder Grand Contest 028 - AtCoder

今回も前回と同じく、速解き1完でレート微減。うーん…

f:id:betrue12:20181014005902p:plain

しっかり復習しましょう。A～Cを振り返ります。

A - Two Abbreviations

解法

※以降の説明では、文字列のインデックスを0始まりで記載します。

まず $X$ の長さ $L$ は $N, M$ の両方で割り切れるという条件があるため、 $L$ は $N, M$ の公倍数です。公倍数は最小公倍数の倍数であるため、 $L$ は $lcm(N, M)$ の正整数倍です。

とりあえず、 $L = lcm(N, M)$ として考えます。 $X$ の中で、文字列 $S, T$ がどこに含まれているかを図示します。

f:id:betrue12:20181014011332p:plain

図のように、 $S$ が1文字進むごとに $X$ は $\frac{L}{N}$ 文字、 $T$ が1文字進むごとに $X$ は $\frac{L}{M}$ 文字進みます。

$X$ の各文字のうち、 $S, T$ のどちらか一方に対応している位置はその文字を採用すればよいですし、どちらとも対応していない位置の文字は好きに決めればよいです。問題は両方に対応している位置で、これらは同じ文字である必要があります。

このように $S, T$ の両方の文字が存在する位置は、 $\frac{L}{N}$ と $\frac{L}{M}$ の公倍数（と0）になります。先ほども書いたように公倍数は最小公倍数の倍数であるため、 $lcm(\frac{L}{N}, \frac{L}{M})$ の0以上の整数倍の位置すべてについて、そこに対応する $S, T$ の文字が一致しているかどうかを調べればよいです。

これで、 $L = lcm(N, M)$ のときの判定ができました。では他の公倍数の場合はどうか？と考えてみますが、他の公倍数は $lcm(N, M)$ の正整数倍です。 $L = k \times lcm(N, M)$ とすると、 $X, S, T$ の対応図は上の図をそっくりそのまま $k$ 倍に「引き伸ばした」ような感じになります。つまりどの公倍数で考えても、比較しなければいけない $S$ と $T$ の文字は同じであり、 $S, T$ に矛盾なく $X$ を構成できるかどうかも同じになります。

そのため上記のように $L = lcm(N, M)$ で調べて、OKであればその値が最小値ですし、NGであればどの公倍数でも $X$ は構成不可能なので-1を出力します。

ACコード

C++のほうが、上の説明に沿って書いています。

B - Removing Blocks

解法

各ブロックについて、「 $N!$ 個の全てのパターンについて合計したときに、ブロック $i$ の重さは合計何回分カウントされるか？」を求めたいです。これを係数として $A_{i}$ に掛けて総和を取ると答えになります。

これをさらに分解し、「ブロック $j$ を取り除くときに、ブロック $i$ の重さは合計何回分カウントされるか？」を考えます。各パターンごとに各ブロックはそれぞれ1回ずつしか取り除かれないため、これは「 $N!$ 個の全てのパターンのうち、ブロック $j$ を取り除くときにブロック $i$ の重さがカウントされるパターンはいくつあるか？」と書き換えられます。

ブロック $j$ を取り除くときにブロック $i$ の重さがカウントされる条件は、取り除く時点で $j$ から $i$ までのブロックが全て存在すること。言い換えると、 $j$ から $i$ までの $|j-i|+1$ 個のブロックのうち、ブロック $j$ が最初に取り除かれることです。このようなパターンの数は $\frac{N!}{|j-i| + 1}$ になります。これは、ブロックを取り除く順番をランダムな事象として考えたときに、 $|j-i|+1$ 個のブロックのうちブロック $j$ が最初に取り除かれる確率が $\frac{1}{|j-i|+1}$ である、と考えたほうが理解しやすいかもしれません。

ここまでの内容を整理すると、

「ブロック $j$ を取り除くときに、ブロック $i$ の重さは合計何回分カウントされるか」は、 $\frac{N!}{|j-i| + 1}$ 。
「 $N!$ 個の全てのパターンを合計したときに、ブロック $i$ の重さは合計何回分カウントされるか？」は、↑を全ての $j$ について合計した $\sum_{j=1}^{N}\frac{N!}{|j-i| + 1}$ 。
答えは、それを係数として $A_{i}$ に掛けて合計したもの。

です。

では、 $\sum_{j=1}^{N}\frac{N!}{|j-i| + 1}$ を求めましょう。 $N!$ は全ての項に共通なので、 $\sum_{j=1}^{N}\frac{1}{|j-i| + 1}$ を求めて一番最後に $N!$ を掛けることにします。これは $i$ の両側それぞれで見ると、 $\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots$ という形になっています。この累積和を事前計算しておけば、各 $i$ についてこの値が高速に求められます。

ただしこれは整数での割り算なので、素数modでの逆元計算を行い、その逆元を足し算していきます。逆元の計算についてはこちらの記事によくまとまっています。信頼と実績のけんちょんさん。

「1000000007 で割ったあまり」の求め方を総特集！〜逆元から離散対数まで〜

これで材料が揃いました。解法をまとめます。

素数modでの逆元計算を用いて、 $\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots$ の累積和を計算しておく。
各 $i$ について、累積和を使って $\sum_{j=1}^{N}\frac{1}{|j-i| + 1}$ を計算する。
上記結果を係数として $A_{i}$ に掛け、加算する。
最後に後回しにしておいた $N!$ を掛ける。

ACコード

C - Min Cost Cycle

解法

ある頂点の $A_{i}$ と別の頂点の $B_{j}$ がペアになり、 $N$ 本の辺を構成します。このとき、重みの小さいものをなるべくばらけさせたいです。特に、 $A_{i}, B_{j}$ を合計 $2N$ 個をごちゃ混ぜにソートして、小さいほうから $N$ 個を $N$ 本の辺にばらけさせることができれば、これが最適です。

ただし問題では「全ての頂点を1度ずつ通るサイクルを構成すること」が要求されています。 $A_{i}, B_{j}$ から重みとして使いたい値を $N$ 個選んだとき、それを $N$ 本の辺にばらけさせて、要求されているサイクルが構成できるでしょうか。

f:id:betrue12:20181014113938p:plain

サイクルを構成できる条件は、上図のようなものになります。一番左のOKパターンは実際に作ってみればいいので分かりやすく、一番右のNGパターンも図のように閉路を作ろうとすると必ず繋ぎ相手がいなくなるので分かりやすいです。真ん中のパターンが必ずOKというのはちょっと難しいのですが、「Aを使うもの」と「Bを使うもの」をそれぞれ固めて、その間を「AもBも使うもの」と「AもBも使わないもの」で上手く繋ぐようにするとサイクルを構成できます。（図では要素数が少ないですが、一応そのように構成しています。）

これでやることが決まりました。OKパターンを満たすように、その中で $A_{i}, B_{j}$ の合計がなるべく小さくなるように $N$ 個を選びます。

ということで、まず小さい方から $N$ 個選んでしまいましょう。この $N$ 個がOKかNGかを確認します。

OKパターンだった場合
- 何の問題もありません。そのまま出力します。
NGパターンだった場合
- この場合、取る値を変更しないといけません。2番目に合計が小さくなるのは、 $1, 2, ..., N-1, N+1$ 番目を選んだ場合です。これがOKパターンならこれが答えです。ただこれも、NGパターンになることがあります。

最後の詰めです。 $1, 2, ..., N-1, N$ 番目も $1, 2, ..., N-1, N+1$ 番目もNGパターンになるというのはどういう状態でしょうか。

f:id:betrue12:20181014113206p:plain

$1, 2. ..., N-1$ 番目を選んだ状態から、 $N$ 番目を選んでも $N+1$ 番目を選んでもNGになる場合、これらの2つの値は同じ頂点に属しています。これがとても重要です。

次の候補を考えます。 $1, 2, ..., N-1, N+1$ 番目がNGとなると、次に重み合計が小さくなるのは

$1, 2, ..., N-1, N+2$ 番目
$1, 2, ..., N-2, N, N+1$ 番目

のどちらかになります。このときこれら2つはどちらも、「 $N$ 番目と $N+1$ 番目は同じ頂点に属している」ということを使ってOKパターンになることが示せます。

$1, 2, ..., N-1, N+2$ 番目を選ぶと、同じ頂点に属する $N, N+1$ 番目がどちらも選ばれていない。そのため他の頂点どれか1つ以上で、 $A_{i}, B_{i}$ 両方が選ばれているはずである。
$1, 2, ..., N-2, N, N+1$ 番目を選ぶと、同じ頂点に属する $N, N+1$ 番目がどちらも選ばれている。

つまり、2つをそれぞれ計算して小さい方を出力すればよいです。

解法をまとめます。

各重みをソートし、小さい方から $N$ 個選び、OKパターンかどうか判定する。OKパターンなら合計値を出力して終了。
↑がNGパターンの場合、 $1, 2, ..., N-1, N+1$ 番目を選び、OKパターンかどうか判定する。OKパターンなら合計値を出力して終了。
↑もNGパターンの場合、以下の2つはともにOKパターンなので、2つのうち合計値が小さいほうを出力して終了。
- $1, 2, ..., N-1, N+2$ 番目
- $1, 2, ..., N-2, N, N+1$ 番目

ACコード

（C++）Submission #3402799 - AtCoder Grand Contest 028

さいごに

本番では、

Aは少し難しいなと思いながらもWAなしで突破。
Bは完全に方針を見誤る。愚直 $O(N^{3})$ 、累積和使って $O(N^{2})$ で回せそうな漸化式を見つけてしまい、そこに固執していました…。
Cは大筋の方針は良かったが、 $1, 2, ..., N-1, N+1$ 番目を選んでもNGとなるケースに気付かなくて詰められず。

という感じでした…。

最近2回ともAGCが解けなくて少しへこみますが、しっかり復習して、問題を解き続けるしかないですね。

2018-10-13

Codeforces Round #515 参加記録＆解説（A～E）

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

Dashboard - Codeforces Round #515 (Div. 3) - Codeforces

結果は5完で、Virtualの参加者を除くと121位。悪くはないですが、上を目指すなら全完したいところですね…

f:id:betrue12:20181013142347p:plain

5問振り返ります。

A. Vova and Train

Problem - A - Codeforces

問題概要

以下の問題 $t$ 個に答えよ。

1から $L$ までの整数のうち、 $v$ の倍数であり、区間 $\lbrack l, r \rbrack$ に含まれないものの数を求めよ。

制約

$1 \le t \le 10^{4}$
$1 \le L, v \le 10^{9}$
$1 \le l \le r \le L$

解法

1から $L$ までの整数のうち $v$ の倍数は $\lfloor\frac{L}{v}\rfloor$ 個あります。

区間 $\lbrack l, r \rbrack$ に含まれる $v$ の倍数のうち、（存在する場合）最小のものは $\lceil\frac{l}{v}\rceil v$ 、最大のものは $\lfloor\frac{r}{v}\rfloor v$ です。その間に含まれる $v$ の倍数の個数は $\lfloor\frac{r}{v}\rfloor - \lceil\frac{l}{v}\rceil + 1$ です。これを総数から引けばよいです。