2018-07-21

ABC103 参加記録

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

今回はABCオンリーでしたー。

結果は14分台全完で14位。けっこう速いかなと思いましたが、それでも1桁順位は取れないのですね…。

f:id:betrue12:20180721221654p:plain

A - Task Scheduling Problem

100点問題にしては難しいような気もしていますが…（というか問題文の読解が少し難しい）

タスク3つにそれぞれ値があり、「1つ前に解いたタスクの値との差の絶対値」だけコストがかかります。小さい方から順番にやっていくのがムダがないです。大きい方からでも良いです。

ACコード：Submission #2876070 - AtCoder Beginner Contest 103

当日は開始後しばらく、出力末尾に改行コードがあるとWAになる？という状態だったようで…ratedな人の焦りは尋常じゃなかったと思います…。*1

B - String Rotation

文字数が最大100しかないので、最大100通りの回転を全部試せばOKです。

ACコード：Submission #2877161 - AtCoder Beginner Contest 103

余談ですが、Rubyの配列には rotate というそのものズバリなメソッドがあります。文字列には使えないので、配列に分解する必要はありますが。

C - Modulo Summation

答えを知ってれば一瞬だけど、考え方が難しい問題。

$m$ の選び方は非負整数なら何でもOKです。逆に言えば選択肢が多すぎるので、何らかの条件で探索範囲を絞ったり、数学的に一発で求める必要があります。

$m \mod a_{i}$ の値は $0, 1, ..., (a_{i} - 1)$ なので、全ての $i$ について値を $(a_{i} - 1)$ にできれば理想です。そして、そのような $m$ は実は存在します。それは、 $m = (a_{1} \times a_{2} \times ... \times a_{N}) - 1$ です。

知識または閃きがあると速い問題ではありますが、上記のように「それぞれの値の範囲はいくつで、それらを同時に大きくすることはできるだろうか？」と考えてみたり、サンプルや自作ケースで実験してみると手がかりが掴めると思います。

ACコード：Submission #2878101 - AtCoder Beginner Contest 103

余談中の余談ですが、「素数が無限にあることの証明」の1つに、「素数が有限と仮定して、"全素数の積+1"という数を考えると、それは全ての有限な素数で割って1余る数なので、これも素数である。よって矛盾」というものがあります。私はそこから連想して解きました。

D - Islands War

争っている島の間に橋が1つもなければアウトです。この問題は、島たちを端から見ていくと分かりやすいです。東西よりも左右のほうが分かりやすいので、西を左として以下「左から」と書きます。

f:id:betrue12:20180721224017p:plain

左から見ていって、既に切れていないペアの右端にぶつかったときは、そのすぐ左の橋を切ります。既に切れている場合は無視します。

感覚としては、切る本数を減らしたいので、なるべく切るのを先送りにする、という気持ちです。

実装はペアを右端の値でソートして、ペアを1つ1つ順に見ていくといいでしょう。

ACコード：Submission #2879237 - AtCoder Beginner Contest 103

さいごに

ABCオンリー回はC, Dも比較的解きやすい問題が多いですが、ARCやAGC-Aでもこのくらいの問題が出たらサクっと解けるようになりたいので、unratedでも良い訓練になります。

脚注

*1:出力末尾の改行コードなんですが、最近のAtCoderでは問題文に明記されておらず、ABC/ARCなどの公式コンテストでは「あってもなくてもいい」というのが慣習的に知られてはいるようです。非公式コンテストでは付いていないとWAになることが割とあるので、私も癖で毎回付けるようにしています。できればルールとして明記したほうが良いのではないかと思っています…。

2018-07-15

技術室奥プログラミングコンテスト #3 参加記録（H問題のみ）

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

技術室奥プログラミングコンテスト #3 - AtCoder

筑波大学附属駒場中学校・高等学校の皆さんによるコンテスト。

部分点がたくさんあるので順位表も複雑ですが、6完+部分点で16位でした。

f:id:betrue12:20180715082653p:plain

普段なら各問題の解説を書くのですが…今回公式解説がすごく丁寧で、解説を書こうとしてもこれを丸写ししたような内容になってしまうため、1問だけ。

Hの510点を解説と違うやり方で取ったので、それについて書いていきます。

H - 新入生歓迎数列 - Hard

基本アイデアは解説の最初の方に出てくる「2進数の各桁を分配する」です。

f:id:betrue12:20180715094741p:plain

このように $A_{1}$ を起点にして2進数の各桁を分配することでそれぞれの値を作ります。

分配されるそれぞれの値は $2^{30}-1$ 以下なので、2進数で30桁。 $N$ がおよそ $550000/30 = 18333.33...$ 以下であればこの方法でいけます。これで280点。

$N \le 25000$ で+230点もらえるので何か方法はないか考えたところ、「階差数列を使う」というアイデアが出ました。

f:id:betrue12:20180715100300p:plain

作りたい数列をソートし、その階差数列を取ります。そうすると、最小値が1、最大値が $2^{30}-1$ なので、階差数列の総和が $2^{30} - 2$ 以下となります。

「各項が $2^{30}$ 程度」と「総和が $2^{30}$ 程度」の違いは大きくて、 $N = 25000$ としてざっくり計算すると1つ1つの値の平均は $2^{30} / 25000 = 42949.672...$ くらいになります。これは16bitで作れるので、最後の数列復元に各1回使うことを加味しても $17 \times 25000 = 425000$ 回程度で完了します。

これを実装して510点を取ったのが以下のコードです。

510点コード：Submission #2839764 - 技術室奥プログラミングコンテスト #3

この方法だとここから発展性がないのでこれ以上の点数は望めませんが、510点までであれば公式解説の4進数よりも思いつきやすいのかな…？と個人的には思いました。

2018-07-15

AGC026 参加記録

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

AtCoder Grand Contest 026 - AtCoder

結果は69分台3完で182位でした。パフォーマンスも2327、過去最高なので上出来です。

1100点はまあ解けないので、欲を言えば600点問題の考察をもう少し速く詰められるようになりたいですね。

f:id:betrue12:20180714233449p:plain

解けたA～Cを振り返っていきます。

A - Colorful Slimes 2

番号の小さいほうから見ていって、色が一致している場合は「後のほうの」スライムの色を適当に変更します。前のスライムは既に両隣チェックされていますが、後のスライムはさらにその後のスライムとの比較が残っているため、こちらを変えたほうが得です。

適当にと書きましたが、実際にはさらにその後のスライムと違う色なら何でも良いです。実装上は -1 とかを代入してしまうといいと思います。

ACコード：Submission #2841191 - AtCoder Grand Contest 026

ちなみに例題情報です。同じ考え方が使えます。

D - Derangement

B - rng_10s

クエリを処理する問題ですが、クエリごとの関連性が薄いのと、クエリが300個しかないのもあって、「前計算をしてクエリを高速に処理する」タイプではないです。1つ1つクエリを処理していきます。

まず、いくつか必敗パターンがあります。

$A \lt B$ のとき、1日目にジュースを買えない。
$D \lt B$ のとき、買われる量より補充量が少ないので、いつか必ず不足する。

これらに対しては No を出力してそのクエリを即終了します。以降、これらではない場合を考えます。

気になるのは、「ジュースの残り本数としてあり得る値のうち、補充されない（すなわち、 $C$ より大きい）範囲で最も少ないのはいくつか？」です。これが $B$ 以上であれば、ジュースを永遠に買い続けられます。

例えばサンプル1の2行目、クエリが $A=9, B=7, C=6, D=9$ の場合。

買われる前	買われた後	補充後
9	2	11
11	4	13
13	6	15
15	8	(補充なし)
8	1	10
10	3	12
12	5	14
14	7	(補充なし)
7	0	9

これ以降はループします。補充されない範囲で最も少ない残り本数は7です。

例えばこれを、 $B=6, D=9$ に置き換えてみましょう。

買われる前	買われた後	補充後
9	3	12
12	6	15
15	9	(補充なし)

これでループします。補充されない範囲で最も少ない残り本数は9です。また、買われた後の値は3, 6, 9しか登場しません。

残り本数の変化に注目してみます。「6減らす」と「9増やす」を繰り返したとき、その変動量の和は必ず3の倍数になっているということが分かります。より一般的に言うと、 $B, D$ の最大公約数（ $G$ と書きます）の倍数になります。変動量が $G$ の倍数ということは、最初の値 $A$ からずっと $G$ で割った余りが変化しないということですね。

対して先程の「7減らす」「9増やす」の例では最大公約数が1なので、残り本数は2, 4, 6, 8, 1, 3, 5, 7, 9, ...と、余りによる制約を受けずに変動しています。

これで方針が立ちました。考えたい条件は、「ジュースの残り本数としてあり得る値のうち、補充されない範囲で最も少ない値は $B$ 以上か？」でした。その値は、

$X \% G = A \% G$
$X > C$

この2つを満たす中で最小の $X$ となります。後はこれを頑張って求めましょう。

ACコード：Submission #2849231 - AtCoder Grand Contest 026

本番中は最初からクリアな考察ができていたわけではないので、もっと場合分けが細かいコードで通しています。非常に自信が持てなくなるようなコードですが、サンプルがめちゃくちゃ親切だったので助かりました…

C - String Coloring

これは完全に制約からエスパーなんですが…とりあえず制約を見ると $N \le 18$ なので、 $O(2^{N})$ とか $O(N 2^{N})$ っぽいなーという気がしてきます。 $N$ 文字くらいなら塗り分け方を全列挙できそうです。

文字列の前半部 $N$ 個について、どちらの色に塗るか？を固定します。

f:id:betrue12:20180715010159p:plain

前半部を塗り分けると、赤の文字列は頭から、青の文字列は反転するので末尾から埋まっていきます。そのため、「その分け方をした時に完成する文字列」がぴったり確定します。

上の図の分け方はつまり、「前半部の分け方であって、赤に2文字使っていて、完成する文字列が caba であるもの」を示します。これと「後半部の分け方であって、赤に2文字使っていて、完成する文字列が caba のもの」を組み合わせることで、条件を満たす分け方となります。

f:id:betrue12:20180715010230p:plain

逆に言うと、「赤に何文字使ったか」と「完成する文字列」が一致していれば、それらはまとめて数えてよいです。

解法をまとめると、

前半部の分け方を全通り試す。「赤に $i$ 文字使っていて、完成する文字列が $s$ であるもの」をそれぞれ数えておく。
後半部の分け方を全通り試す。「赤に $N-i$ 文字使っていて、完成する文字列が $s$ であるもの」と、さきほどの値を掛け算したものを足していく。

これで解けます。こういった解法を「半分全列挙」と言います。

ACコード：Submission #2845141 - AtCoder Grand Contest 026

解説だと計算量が $O(N^{2} 2^{N})$ なんですが、2個目の $N$ がどこから来ているのかは分かりません…

さいごに

配点を見た時にこれは3完必須だなあと思っていましたが、結構良い速度で3完できてよかったです。いつか橙パフォを出したいですね。

2018-07-08

ウクーニャたんお誕生日コンテスト参加記録

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

ウクーニャたんお誕生日コンテスト - AtCoder

チーム参加OKの非公式コンテスト。ウクーニャたんさん誕生日おめでとうございます！

外出の予定があったので途中からでしたが、ゆかもちさんに急遽お誘いいただき参加しました。ありがとうございました！

f:id:betrue12:20180708131909p:plain

私はBの実装をやりました。2問振り返っていきます。

A - UkuNumber

式の形がフィボナッチ数列によく似ています。実際計算してみると、

$u_{1} = a$
$u_{2} = b$
$u_{3} = a + b$
$u_{4} = a + 2b$
$u_{5} = 2a + 3b$
$u_{6} = 3a + 5b$

と、各項の係数がフィボナッチ数列になっています。具体的にはフィボナッチ数列 $f_{i}$ を1, 1, 2, 3, 5, ... として、 $u_{i+2} = f_{i} * a + f_{i+1} * b$ です。

数列が $X$ を含むような「辞書順最小」のペアを求めるにあたり、 $a = 1$ の解が必ず存在することに気づけるかどうかがカギとなります。例えば $a = 1, b = X - 1$ とすると $u_{3} = X$ となります。また、もっと単純に $a = 1, b = X$ でもいいです。

そのため、 $a \ge 2$ の解は上記のものより必ず辞書順で後ろになるので、 $a = 1$ のものだけを探索すればよいです。

$a = 1$ とすることで、この問題は「 $X = f_{i} + f_{i+1} * b$ となる $i$ が存在するような $b$ の最小値を求めよ」という問題に帰着できます。

あとはどうするかですが、フィボナッチ数を全探索します。 $10^{18}$ という値が恐怖を感じさせますが、フィボナッチ数列の増加スピードも恐怖で、これ以下のフィボナッチ数は87個しかないです。 $X$ は100個ありますが、100回やっても大丈夫です。

ACコード：Submission #2800522 - ウクーニャたんお誕生日コンテスト

（ACコードのリンクは、チームではなく私のアカウントで出したものにしています）

B - Sprinkler

限られたスプリンクラーの操作回数で与える水の合計を最大化したいので、1回1回の効率を最大化するなら、一番広く水を与えられる範囲を選び続ければよさそうです。ただ水を最大に与えてしまった甜菜は範囲に選べなくなるので、「水をあげる」ことがデメリットになるかもしれない、という気も少しだけあります。

以下の図のように考えると、一番広い範囲を選ぶことが得である（少なくとも、損をしない）ことがわかります。つまり、あえて狭い範囲を選んだ時に、「範囲を広く選んだほうが得」または「範囲を広く選んだとしても同じ構造が作れる」のどちらかが言えます。

f:id:betrue12:20180708154730p:plain

というわけで、1回1回の効率を最大化するよう貪欲に範囲を選んでいけばよいです。

また、 $A_{i}$ が大きいので、水やり1回ずつ考えていくのは無理です。その時点での一番広い範囲を決めたら、その範囲で水をあげられるだけあげてしまいましょう。範囲内で残り容量が一番小さいものを探し、その容量だけ水をあげることができます。その後は、残り容量が0になった点で範囲を分割します。

f:id:betrue12:20180708154524p:plain

これを、全部の甜菜の残り容量が0になるか、水やり回数が $M$ に達するまで続けます。

ということで、実装です。以下のことができる必要があります。

貪欲に広いほうから範囲を取るため、範囲たちを管理し、それらを広い順に取り出す。→プライオリティキュー
水をあげられる回数を得るため、範囲の最小値を求める→セグメント木
範囲を分割する点を得るため、最小値を持っている点を求める→後述（※1）
水をあげたということを反映するため、範囲の全ての値から、決まった値を引く→後述（※2）

まず（※1）についてですが、蟻本記載のセグメント木では最小値を求めることはできてもそれがどの点なのかは分かりません。ですが、実は $A_{i} \ne A_{j}$ という条件があるので、インデックス→値の逆写像をmap等で持っておけば最小値→インデックスが得られます。

また（※2）についても蟻本のセグメント木では求められませんが、各区間ごとに「それまで累計いくつ水が与えられたか」の情報を付与しておけば、セグメント木にその情報を入れる必要はありません。

Submission #2800469 - ウクーニャたんお誕生日コンテスト

計算量オーダーですが、区間を1つ処理するごとにどこかの甜菜の残り容量が0になるので、区間を処理する回数は高々 $N$ です。1回の処理につきセグメント木やプライオリティキューの操作で $O(\log N)$ かかるので、全体は $O(N \log N)$ となります。

さいごに

今回はチーム戦ということで、slackのDMで意見交換しながら進めていきました。しっかり作戦を決めて臨んだわけではないので緩い感じでしたが、1人ではなかなか気づけないコーナーケースや考察ミスが早く発覚したり、問題の分担を考えたり、ソロとはやっぱり感覚が違うなと思いました。チームプレイをしっかり回すのは難しいんだろうな、とも。

デバッグに関しては、やっぱり言語が揃っていたほうが良いのかなという気もしました…

何はともあれ、2完はけっこう上出来なんじゃないかと思います。ゆかもちさんありがとうございました！

2018-07-08

SoundHoundコンテスト予選　参加記録

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

SoundHound Inc. Programming Contest 2018 -Masters Tournament- - AtCoder

既卒者（社会人etc.）限定オンサイトコンテストの予選。また、レート2000未満の参加者にとってはratedなコンテストでもありました。ABCとARCの中間くらいですね。

結果は133分台全完で121位！最後2分でEが通りました…前回といい今回といい、ギリギリの時間で1問通ることが最近多くて心臓に悪いです。

f:id:betrue12:20180708093336p:plain

パフォーマンスは2200超えで申し分ないのですが、オンサイト枠に入れているかどうかは…うーん。無理かなあ。

全問振り返っていきます。

A - F

書いてあるとおりにif文で分岐すればOK。久々にratedで100点問題を解きました。問題名のFは16進数で15という意図だと思います。

ACコード：Submission #2801575 - SoundHound Inc. Programming Contest 2018 -Masters Tournament-

B - Acrostic

先頭を0文字目として $0, w, 2w, 3w, ...$ 文字目を順番に出力すればOK。文字数が $\frac{|S|}{w}$ の切り上げになるので、整数割り算の切り上げは書けるようになっておきましょう。

ACコード：Submission #2803017 - SoundHound Inc. Programming Contest 2018 -Masters Tournament-

問題名のAcrosticの意味については以下参照。「縦読み」みたいなものですね。

折句 - Wikipedia

C - Ordinary Beauty

取りうる数列の数が $n^{m}$ と非常に多いので、簡単な計算方法を考えなければいけません。

要素数が $m$ なので、隣り合う2項の間は $m-1$ 個あります。実はこの $m-1$ 個を、独立に考えることができます。

試しに $n = 3, m = 3$ の時の場合を全列挙してみましょう。

f:id:betrue12:20180708095511p:plain

このとき、 $(a_{1}, a_{2})$ に着目すると、これらの値が $(1, 1)$ となるのは3通り。同じように $(1, 2)$ も3通りであり、全てのペアが3通りという等しい数で登場します。

そしてこれは、 $(a_{2}, a_{3})$ にも同じことが言えます。上の表だと位置がバラけていますが、全てのペアが3通りずつ登場していることが分かります。

これは $n, m$ が一般の場合でも同じことが言えます。そのため、

隣り合う2項だけを考え、その全ての場合（ $n^{2}$ 通り）に対して、差が $d$ となる場合を数える。差が $d$ となった場合美しさは+1、そうでない場合+0されるので、平均は(差が $d$ となる場合の数)/(全ての場合の数)となる。*1
それを「隣り合う2項の間」の数、つまり、 $(m-1)$ 倍する。

と、問題を単純化することができます。あとは、「2つの数の差が $d$ となる場合の数」を求めれば解けます。 $d = 0$ のときだけ特殊なので注意しましょう。

f:id:betrue12:20180708101119p:plain

ACコード：Submission #2804184 - SoundHound Inc. Programming Contest 2018 -Masters Tournament-

D - Saving Snuuk

問題文が長いので頑張って整理しましょう。

頂点 $s$ からスタートし、円を使って両替所のある点のどこかに移動する。
ここで両替をして、スヌークを使って頂点 $t$ に移動する。
使った金額の合計を最小化したい。

こうなります。そして、両替所は年々減っていくので、それぞれの年について金額合計の最小値（正確にはそれを $10^{15}$ から引いた値）を求めたい、という問題です。

この $s \rightarrow (どこか) \rightarrow t$ という感覚を持つことが大事で、 $s$ からどこかまでの円での移動と、どこかから $t$ までのスヌークでの移動についてそれぞれ最小金額が求められれば、それを組み合わせることで合計金額を最小化できそうです。

そこで最短路問題を解くダイクストラ法の出番です。ただし、ナイーブなダイクストラ法は $O(n^{2})$ で通りそうにないので、プライオリテイキューを用いた $O(m \log n)$ のほうを使いましょう。始点を $s$ とする円でのダイクストラと、終点を $t$ とするスヌークでのダイクストラ…なのですが、今回は無向グラフなので $t$ を始点として考えても問題ないです。

めでたく両方の最短路問題が解けたら、次は「どこの両替所を使うか？」を考えます。最初は $1, 2, ..., n$ 全ての両替所が使えますが、どんどん減っていって最後は都市 $n$ でしか両替できなくなります。毎回全ての候補を試していると $O(n^{2})$ になってしまいます。

こういう時はどんどん候補が増えていく順番で考えると効率的です。今回は時間順に考えると候補が減っていくので、時間を逆回しすると良いです。

都市 $n$ でしか両替できない状態では、候補が1通りなので自動的に決まります。次に都市 $n-1, n$ が使える場合、候補が1つ増えたので、さっきの値と $n-1$ を使ったときの値を比べて良いほうをとります。このようにして、「それまでの最適値」と「新しく使えるようになった都市を使ったときの値」を比較することで、効率的に計算できます。

ACコード：Submission #2807882 - SoundHound Inc. Programming Contest 2018 -Masters Tournament-

RubyだとTLEしたのでC++に切り替えました…

E - + Graph

木とは限らない連結グラフ、ということは閉路があるかもしれません。そのため、「どの辺 $i$ についても、頂点 $u_{i}$ と $v_{i}$ に書かれた正の整数の和は $s_{i}$ に等しい」という条件が結構厳しそうに思います。

状態数が多いので、なんとか仮決めして考えやすくしたいです。全ての辺について和の制約があるので、もし1点の値を固定すれば、DFSやBFSによって全ての値を決めることができます。

仮に頂点1の値を「0」とします。仮に固定しただけで、この時点では頂点1の値に制約は見つかっていません。またこの時点では、「正の整数」という制約は一旦考えないことにします。これから、「頂点1の値の取り方にはどんな制約があるか？」をグラフ探索によって見つけていきます。

f:id:betrue12:20180708110717p:plain

左端を頂点1だと思ってください。このように、隣り合う辺の値が順番に決まっていきます。マイナスがありますが、とりあえず気にしません。

このとき、固定した点を赤として、その隣を青、その隣を赤…とします。これは「固定する頂点1の値を増やした時、値が増えるか、減るか？」を示しています。実際に左端の値を1にしたのが下側の図で、赤の値は1増え、青の値は1減っているのが分かります。

探索途中で閉路が見つかったとします。このとき、隣り合った2点の色が同じかどうかで、判断が異なります。これは、閉路を構成する辺の数が偶数か奇数か、の言い換えです。

違う色（偶閉路）の場合

f:id:betrue12:20180708112417p:plain

2つの頂点が違う色の場合、最初に決めた頂点1の値をいくら増加させても、赤の値が増加し、同じだけ青の値が減少します。つまりこの和は一定です。

その値がたまたま辺に書かれた値と同じであれば、必ず整合性が取れるので探索を続けてよいです。もし異なる値だったときは、どうやってもこの矛盾を解消することはできないので、この時点で0を出力して即終了してよいです。

同じ色（奇閉路）の場合

f:id:betrue12:20180708113014p:plain

同じ色の場合は少し事情が違います。というのも、頂点1の値を変化させることで和を変化させられるからです。頂点1の値を1増加させると、赤・赤ペアの合計は2増加し、青・青ペアの値は2減少します。

もし頂点1の値を変えて、辺の条件を満たすようであれば、その時点で頂点1の値が確定します。（変えなくても条件を満たす場合は、頂点1の値は0で確定します）

ただし、整合性が取れないケースもいくつか存在します。1つは、条件を満たす頂点1の値が整数にならない場合。ずれが奇数の場合はこうなります。次に、奇閉路が2箇所以上見つかって、それぞれが要求する頂点1の値が異なっている場合。これもダメです。0を出力して即終了します。

f:id:betrue12:20180708113948p:plain

仕上げ

これでグラフを全て探索できたら、最後に残った「全頂点の値は正の整数」の条件を考慮して答えを出します。

前準備として、赤い点の数字の最小値 $r_{\min}$ 、青い点の数字の最小値 $b_{\min}$ を計算しておきます。これらは頂点1の値を0としたときのものです。

まずは、奇閉路があって頂点1の値が確定している場合。その値を $a_{1}$ とすると、赤い点の数字の最小値は $r_{\min} + a_{1}$ 、青い点の数字の最小値は $b_{\min} - a_{1}$ となります。これらが両方正の値であれば、全ての頂点の値が正となるのでOK。答えは1通りです。そうでないなら0通りです。

次に、奇閉路がない場合。その場合、 $r_{\min} + a_{1}$ と $b_{\min} - a_{1}$ が両方正になる範囲で $a_{1}$ を自由に選ぶことができます。結局答えが0通りになる場合もあります。

ACコード：Submission #2812884 - SoundHound Inc. Programming Contest 2018 -Masters Tournament-

本番のコードがあまりにぐちゃぐちゃだったので、書き直すついでにコメントマシマシにしてみました。

さいごに

今回の好成績でレートが+105も上がり、青に復帰できました！

f:id:betrue12:20180708120141p:plain

黄色になるにはこのパフォーマンスを出し続ける必要があるわけで…道程は長い。精進します。

脚注

*1:公式解説では「確率」「期待値」という言葉を使っていますが、不確定に変動する要素があるわけではないので、この記事ではなるべく使わずに解説しています。ただ、考え方としてはよくある確率の計算に非常に近いです。

2018-07-02

ARC100 参加記録

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

先日のABC100に続き、ARCも記念すべき100回目。

成績は…130分台2完で349位。Cでドツボにハマったので今回もレート大幅減を覚悟しましたが、最後5分でDが通って本当に良かった…！

f:id:betrue12:20180701235243p:plain

C, Dの2問を振り返っていきます。

C - Linear Approximation

まず、求めたい値は

$|A_{1} - (b+1)| + |A_{2} - (b+2)| + ... + |A_{N} - (b+N)|$

の最小値ですが、このままだと考えにくいので $A_{i} \leftarrow A_{i} - i$ と置き換えてしまいます。これにより求めたい値が

$|A_{1} - b| + |A_{2} - b| + ... + |A_{N} - b|$

の最小値となり、考えやすくなります。

この値を最小にする $b$ は、結論を言ってしまうと（置き換え後の） $A_{1}, A_{2}, ... , A_{N}$ の中央値になります。これを証明してみます。

「差の絶対値の総和」は、数直線上の距離の総和と見なすことができます。数直線を図示します。

要素数が奇数の場合

f:id:betrue12:20180702002648p:plain

要素数が奇数の場合、中央値は順序で見て真ん中の要素の値になります。そのため、「中央値から見て左右にある要素の数は等しい」ということが言えます。

そのため図示したように、 $b$ の値を中央値に近づけると距離総和は小さくなり、遠ざけると大きくなります。また中央値から値を動かすと、必ず距離総和は大きくなります。そのため、 $b$ は中央値に等しい値であることが最適です。

要素数が偶数の場合

f:id:betrue12:20180702003832p:plain

要素数が偶数の場合、順序で見て真ん中の要素が2つあるため、中央値はその2つの平均値と定義されています。

このとき、真ん中の要素2つの間に $b$ があれば、その両側にある要素の数は等しいので、真ん中の要素2つの間からはみ出ない範囲で $b$ を動かしても距離総和は変わりません。それ以外のところに $b$ がある場合は、奇数のときと同じように中央値に近づけるほうがよいです。そのため要素数が偶数の場合は、真ん中の要素2つの間に $b$ があることが最適であり、中央値はもちろんその条件を満たします。

以上より、要素数が奇数・偶数の場合ともに、 $A_{1}, A_{2}, ... , A_{N}$ の中央値に $b$ を取るのが最適となります*1。

実装においては、中央値はソートした後に真ん中の添字を指定して取ってくるのがシンプルです。

ACコード：Submission #2777708 - AtCoder Regular Contest 100

コンテスト本番では中央値ではなく平均値が性質を満たすとずっと思っていて、平均値の周囲を探索するコードを投げまくってWAを量産してしまいました…

D - Equal Cut

数列を4分割し、和の最大値と最小値をなるべく近づけるという問題。部分和の計算は累積和を使えばよいとして、分ける境界が3つもあるので何とかして効率的に探索しなければなりません。 $N \le 2 \times 10^{5}$ なので $O(N^{2})$ 以上は通らず、全探索できるのは1箇所が限界です。

「1個＋3個の境界」「2個＋2個の境界」のどちらかを全探索したくなりますが、1個+3個だと行き詰まります。今回の場合、結果的には2個+2個、つまり真ん中の境界を固定するのが正解です*2。

真ん中の境界を1つに固定して数列を2分割し、それぞれの和を $S_{1}, S_{2}$ とします。2分割した領域それぞれを、さらにどう分けていくのがよいか考えていきます。

f:id:betrue12:20180702220155p:plain

4分割した際のそれぞれの部分和は、非負の整数 $d_{1}, d_{2}$ を用いて

$(S_{1} - d_{1})/2$
$(S_{1} + d_{1})/2$
$(S_{2} - d_{2})/2$
$(S_{2} + d_{2})/2$

と表すことができます。ここで $d_{1}, d_{2}$ は、 $S_{1}, S_{2}$ をさらに分割した時の差であり、0の時に完全な2等分であることを意味します。

そしてこれら4つの部分和の最大値と最小値は、

最大値： $\max( S_{1} + d_{1}, S_{2} + d_{2} )/2$
最小値： $\min( S_{1} - d_{1}, S_{2} - d_{2} )/2$

となります。 $d_{1}, d_{2}$ の値が増えると、最大値は大きくなり最小値は小さくなるので、その差は広がってしまいます。 $d_{1} = d_{2} = 0$ になれば理想です。

もちろん数列の並びによっては、都合よく $d_{1} = d_{2} = 0$ とできないことのほうが多いでしょう。ですが、これらの値をできるだけ小さくするように分割しようという方針が立ちます。

二分探索で解く

「部分和の差を最も小さくするように分割する」ことを効率的に行える1つの方法は二分探索です。例えば $S_{1}$ を分割したそれぞれの部分和を左から $s_{1}, s_{2}$ とすると、最初に $s_{1} \gt s_{2}$ となる境界の中で一番左にあるものは二分探索で求めることができます。

とはいえこれが最適とは限りません。 $s_{1} \le s_{2}$ *3の場合のほうに最適解があるかもしれないからです。この場合、先程とは逆に $s_{1} \le s_{2}$ を満たす中で一番右にある境界を使いたいので、先程求めた境界の1つ左を考えればよいです。これを2通り試して、より差の小さい方を取ります。

f:id:betrue12:20180702231030p:plain

$S_{2}$ についても同じことをすれば、4つの部分和が出揃うので、最大値と最小値の差を取れば「真ん中の境界を1つ固定した時の」最適値が求まります。あとは真ん中の境界を全探索すれば良いです。

二分探索ACコード：Submission #2780112 - AtCoder Regular Contest 100

しゃくとり法で解く

また、しゃくとり法で解くこともできます。節がいっぱいあるので、ちょっと気持ち悪いしゃくとり虫の動きになりますね。

具体的には、

真ん中の境界を、左から1ずつずらしていく。
その真ん中の境界について、 $d_{1}$ が最も小さくなるまで左の境界をずらす。具体的には、「境界を1つ右にずらして $d_{1}$ が改善するならば、1つずらす」を繰り返す。
その真ん中の境界について、 $d_{2}$ が最も小さくなるまで右の境界をずらす。同上。
部分和4つが出揃うので、最大値と最小値の差を計算する。
以降繰り返し。

のような流れになります。

このとき、左右の境界の最適な位置は単調性がある、つまり後戻りすることがありません。この理由は直感的には以下のように説明できます。

例えば左半分を考えると、真ん中の境界を右にずらすごとに、右側の要素がどんどん増えていきます。それをほぼ半分に分ける境界も、右に右にずれていくはずです。

右半分についても、真ん中の境界を右にずらすと左側の要素が減るので、半分に分ける境界も右にずれていくはずです。

厳密には不等式をこねくり回すと多分示せます。（雑）

しゃくとり法ACコード：Submission #2780125 - AtCoder Regular Contest 100

さいごに

前回に引き続き、C問題でハマってしまいました…最近は600～800点くらいの問題を少しずつ進めていましたが、300～400点くらいの問題を少し復習したほうがいいのかなあ、とも思ったり。

次のratedコンテストは、レート2000未満の人にとってはSoundHoundコンテストになりますね。社会人対象オンサイトコンテストの予選ということで、ほんの少しだけ本選出場の望みも持ちつつ、レートも上げられるように頑張りたいです。

脚注

*1:今回は「bの値を動かすとどうなる」ということだけで説明しました。数学的に言うと、凸性から局所最適＝全体最適だということを使うとスマートだと思います。

*2:このへんの判断は難しいですが、「どれかの値を固定するときに、問題が対称になるようにする」という考え方は役立つ場面が多いように思います。他には例えばARC084-C「Snuke Festival」など。

*3:等号はどちらにあっても良いです。

2018-06-30

codeFlyer(オープンコンテスト) 参加記録

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

codeFlyer （bitFlyer Programming Contest）オープンコンテスト - AtCoder

「codeFlyer 本選」のほうは、予選突破した参加者のみで行われるオンサイトコンテスト。オープンコンテストは、それと同じタイミングで同じ問題を解けるオンラインコンテストです。

オンサイトはやっぱり狭き門なので、オンラインで開催してくれるのはとてもありがたいです。

そして結果はABCFの4完、オープンコンテスト3位でした！

f:id:betrue12:20180630214549p:plain

これがratedだったらなーと少しだけ思いますが、それでも嬉しいです。Fを通せたのがとても大きい。

というわけで解けた4問を振り返っていきます。

A - 値札

10で何回割れるかを全部数えて、その最小値が答えです。整数を10で割る代わりに、文字列として処理して末尾の0の数を数えてもいいです。

ACコード：Submission #2758182 - codeFlyer （bitFlyer Programming Contest）オープンコンテスト

B - 交通費

データに対して大量のクエリを処理する問題は、前計算 → クエリを効率的に処理 が王道パターンです。全クエリを毎回真面目に計算すると $O(NQ)$ で $10^{10}$ くらいになりTLEします。

とはいえ、何を前計算すればよいかの見当を付けるため、まずはクエリの処理方法を考えてみます。

クエリ $C$ と $D$ が与えられた時、参加者の家の位置 $X$ を横軸に取ると、交通費（縦軸）は以下のようなグラフになります。

f:id:betrue12:20180630220207p:plain

このため、 $X_{i}$ たちを次の4つにグループ分けできます*1。

$X_{i} \lt C - D$ である $X_{i}$ に対しては、交通費は $D$ 。個数が分かれば(個数) × $D$ でまとめて計算できる。
$C - D \le X_{i} \lt C$ である $X_{i}$ に対しては、交通費は $C - X_{i}$ 。
$C \le X_{i} \lt C + D$ である $X_{i}$ に対しては、交通費は $X_{i} - C$ 。
$C + D \le X_{i}$ である $X_{i}$ に対しては、交通費は $D$ 。個数が分かれば(個数) × $D$ でまとめて計算できる。

というわけで、以下の2つのことができれば交通費の総和が効率的に求められます。

1～4それぞれの範囲の境界となる $X_{i}$ を効率的に求める。境界が分かれば、範囲内の要素の個数も求められる。
範囲2, 3の交通費の総和を効率的に求める。

境界を求めることは二分探索で効率的にできます。1回あたり $O(\log N)$ なのでクエリごとに行っても大丈夫でしょう。

次に2, 3の交通費総和です。3の式で考えてみます*2。

交通費の総和は $\sum (X_{i} - C) = \sum X_{i} - nC$ です。ここで $\sum$ は範囲内の $X_{i}$ それぞれについて加算することを示し、 $n$ はその要素数です。要素数の計算は、二分探索で解決済みです。

$\sum X_{i}$ は、ある範囲内の連続する要素の和になっています。これは累積和を事前に求めておくことで高速に計算できます。具体的には $S_{i} = X_{1} + ... + X_{i}$ を事前に求めておけば、 $X_{x} + ... + X_{y} = S_{y} - S_{x-1}$ で計算可能です。