2018-06-17

ABC100-D 8通り場合分けの「正当性」について説明を試みる

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

タイトルの通りです。

D - Patisserie ABC

おそらく色々な説明があると思いますが、私なりにしっくりきた考え方を書きます。是非、他の人の考え方も読んでみたいです。

一般の問題ではなく問題例を1つ考えるだけなので、厳密な証明の形式にはなっていませんが、似たような思考で一般的な証明ができる…はずです。

推奨理解度

本記事を読んでいただくにあたっての、一応の推奨理解レベルです。必須ではないですが、特にまだACしていない方は是非そちらからやってみてください！

この問題を「8通り場合分け」の貪欲 or DPでACしている
「8通り場合分け」を行った際に、そのうちのどれかで最適値（出力すべき値）が得られることを理解している
「8通り場合分け」において、「実際には実現しない値」が出てくることを理解している（or そんな気がしている）

そのうえで、「実際には実現しない値が出てきちゃうけど、それでいいの？」という疑問を解消しよう、という試みです。

今回の問題設定について

問題の本質は変えずに、~~書く量を減らしてサボるため~~問題を単純にするため、以下のように問題を変更します。

選ばれるものの総数 $N = 3$ , 選ぶ数 $M = 2$
評価値は2種類（ $x_{i}, y_{i}$ だけ）

評価値が2種類なので、求めたい値（以降、目標値と呼びます）は以下になります。

$\max_{S} (|\sum_{i \in S} x_{i}| + |\sum_{i \in S} y_{i}|)$

ここで $S$ は「 $N$ 個のものから $M$ 個選ぶ選び方」の集合です。記載煩雑になるので、以降は省略します。

問題例

前節で定義した問題設定の条件を満たす、以下の問題を考えます。

$i$	$x_{i}$	$y_{i}$
0	1	-1
1	-2	2
2	1	-3

この問題を、

組み合わせ全列挙
符号パターン全列挙

の2通りで解いてみます。

組み合わせ全列挙で解く

こちらの解き方は、「厳密な最適解」として納得しやすいと思います*1。

与えられた3個の要素から2個選ぶ、全ての選び方を考えます。これは ${}_{3}C_{2} = 3$ 通りです。

選び方	$\sum x_{i}$	$\sum y_{i}$	$\|\sum x_{i}\| + \|\sum y_{i}\|$
(0, 1)	-1	1	2
(0, 2)	2	-4	6
(1, 2)	-1	-1	2

それぞれの選び方の目標値は一番右に書いています。この中で一番大きいものを見ればよいので、これで問題の答えは6です。

ここで終わらずに、もう少し考えてみましょう。それぞれの選び方について、 $\sum x_{i}$ と $\sum y_{i}$ の符号を見てみます。

選び方	$\sum x_{i}$ の符号	$\sum y_{i}$ の符号	$\|\sum x_{i}\| + \|\sum y_{i}\|$
(0, 1)	-	+	2
(0, 2)	+	-	6
(1, 2)	-	-	2

登場する符号の組み合わせは「-, +」「+, -」「-, -」、全部で3パターンです。

ただし、2つの値に対する符号のパターンは実際には4パターンですよね*2。上表には出現していないパターンがもう1つあります。それは、「+, +」のパターンです。

このことを意識しつつ…もう1つの解き方を考えてみます。

符号パターン全列挙で解く

元々のD問題の想定解法と同じように解くことを考えます。具体的には、4通りの符号パターンについて場合分けし、大きい方から貪欲に選んでいきます。

まずは、それぞれの要素に対して4通りの符号パターンに対応する値を考えます。

$i$	$x_{i}$	$y_{i}$	$+ x_{i} + y_{i}$	$+ x_{i} - y_{i}$	$- x_{i} + y_{i}$	$- x_{i} - y_{i}$
0	1	-1	0	2	-2	0
1	-2	2	0	-4	4	0
2	1	-3	-2	4	-4	2

各符号パターンについて、大きい方から要素を2つ取ります。合計値が最大になる選び方とその合計値は以下の通りです。

符号パターン	合計最大になる選び方	合計
$+ x_{i} + y_{i}$	(0, 1)	0
$+ x_{i} - y_{i}$	(0, 2)	6
$- x_{i} + y_{i}$	(0, 1)	2
$- x_{i} - y_{i}$	(0, 2) or (1, 2)	2

この最大値を取って、問題の答えは6です。

比較

これらの結果を比較してみましょう。もちろん答えは6で一致していますが、選び方と符号パターンの関係に着目してみます。

まずは「全部の選び方を考えたとき、それぞれの選び方で符号パターンがどのようになるか？」です。

選び方	$\sum x_{i}$ の符号	$\sum y_{i}$ の符号	$\|\sum x_{i}\| + \|\sum y_{i}\|$
(0, 1)	-	+	2
(0, 2)	+	-	6
(1, 2)	-	-	2

次に「全部の符号パターンを考えたとき、それぞれの符号パターンで最適な選び方がどのようになるか？」です。

符号パターン	合計最大になる選び方	合計
$+ x_{i} + y_{i}$	(0, 1)	0
$+ x_{i} - y_{i}$	(0, 2)	6
$- x_{i} + y_{i}$	(0, 1)	2
$- x_{i} - y_{i}$	(0, 2) or (1, 2)	2

見比べてみると、符号パターン「+, +」で得られる「0」という値については、これを実現する選び方が存在しません。これがつまり、冒頭で書いた「実際には実現しない値が出てくる」という現象です。

もしこの「実際には実現しない値」が全符号パターン中で最も大きい値になってしまう場合があれば、符号パターン全列挙の解き方には正当性がない、ということになります。

今回の「0」という値は他のパターンの値よりも小さいので、最大値を求めるにあたっては実害を及ぼしません。とはいえ気になるのは、これが偶然なのか？必然なのか？ですよね。もう少しだけ考えてみます。

表にしてみる

この2つの解き方の差を、このようにイメージしてみましょう。

f:id:betrue12:20180617120112p:plain

全ての選び方、全ての符号パターンに対する値を列挙しました。組み合わせ全列挙はこれを「行ごと」に、符号パターン全列挙はこれを「列ごと」に解いていく方法と言えます。

紫の丸が付いているものは、その選び方の絶対値として正しいもの、つまり「実現可能な値」です。

それぞれの行を見ると、紫の丸がついた値は、4つの値の中で最も大きいことがわかります。これは絶対値の性質を考えると確かにそうで、紫の丸がついていない値は「絶対値によって0以上になっているものを、わざわざ符号反転させたもの」ですので、必ず小さくなります*3。

さきほど登場した「実際には実現しない値」は、左上にある0です。この値は、その選び方の「絶対値として正しい値」である2よりも小さい。すなわち、この2が属している列である「-, +」の符号パターンにおける最大値よりも小さいことが保証されます。別の符号パターンで得られる最大値よりも小さいのであれば、それが全ての符号パターンの中での最大値（最終的な計算結果）になることはありません。

同じことを言っていますが、少し一般性を持たせて書くと以下のようになります。

符号全パターン列挙で、ある符号パターン（列）についての最大値として「実現可能でない値 $A$ 」が得られたとする。
その値に対応する組み合わせ（行）の中で、絶対値として正しい値 $B$ が存在し、 $A \lt B$ である。
$B$ に対応する符号パターン（列）で得られている最大値 $C$ について、 $B \le C$ である。
すなわち、 $A \lt C$ が成り立つため、 $A$ は全ての符号パターンの中での最大値（最終的な計算結果）にはなり得ない。

おわりに

私含め、本当にこれでいいのかモヤモヤが残っている人が多そうだったので書いてみました。長文読んでいただきありがとうございました。

一般化、同一視、言い換え、図示、色々な説明方法がありそうな気がしています。冒頭にも書きましたが、「こう考えたらしっくりきた！」というものがあれば、是非とも書いて公開していただけると嬉しいです。

脚注

*1:AtCoderの元々の問題でこれをやると、余裕でTLEします。

*2:0を除いた場合です。0が出てきた場合は「どちらに含めても良い」と解釈してください。

*3:一般には絶対値は0以上なので「以下」とするべきですが、イコールになる場合は、それも正しい絶対値を実現する符号パターンである（紫の丸が両方についている）はずです。絶対値として正しくない値は、正しい値よりも厳密に小さくなります。

2018-06-16

ABC100 参加記録

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

AtCoder Beginner Contest 100 - AtCoder

記念すべき100回目のABC！おめでとうございます！ 次は目指せABC200。

ということでおめでたい回なのですが、私の成績は全完37分台で144位。うーん…2WAが痛いです。

f:id:betrue12:20180616223134p:plain

平方数賞ですね（そんなものはない）

振り返っていきます。

A - Happy Birthday!

A問題からちょっと頭を使う内容。

A - Happy Birthday!

入力例2の図が分かりやすいですが、1人が取る個数が8個までなら1個飛ばしで取ることができます。逆に9個取ってしまうと、必ずどこかが隣り合ってしまいます。

そのため両方の個数が8以下なら Yay! 、そうでなければ :( が答えです。

ACコード：Submission #2675152 - AtCoder Beginner Contest 100

素直に YES NO にしない問題が多いのは、今回のライターさん（通称「双子」さん）の特徴ですね。楽しいですが、タイプミスが少し心配になります。問題文からコピペするのが吉。

B - Ringo's Favorite Numbers

2WA出しました…ひどい:(

パッと見て問題文がよく分からなかったのですが、サンプルの記載を見るとイメージが掴めます。

100でちょうど「0」回割り切れる正整数：1, 2, 3, 4, ...
100でちょうど「1」回割り切れる正整数：100, 200, 300, 400, ...
100でちょうど「2」回割り切れる正整数：10000, 20000, 30000, 40000, ...

そのため、 $N * 100^{D}$ が答えになりそうです…が、 $N = 100$ の時は100で割り切れる回数が増えてしまうので飛ばさなくてはいけません。

これを0WAで通してる人、すごい。

ACコード：Submission #2680984 - AtCoder Beginner Contest 100

C - *3 or /2

問題文が少し回りくどく書かれていますが、「全ての $i$ に対して3倍することはできず、操作後の $a_{i}$ の値は整数でなければならない」ということは、全ての値が2で割れなくなったら終了です。

また、「3倍する」という操作は、「2で割れるかどうか」に影響しないので考慮する必要がありません。これは3が2と互いに素だから言えることです。

というわけで、問題を単純化します。

2で割れる数を1つ以上選び、2で割る。
全ての数が2で割れなくなったら終了する。

「1つ以上」と書きましたが、操作回数を最大にしたいので、1つずつ選んでいくのが最善です。ということで、与えられた $a_{i}$ の「2で割れる回数」の総和を出力すれば答えになります。

計算量は、入力 $a_{i}$ の最大値を $A$ として $O(N \log A)$ 。 $N \le 10000, A \le 1000000000$ なので通ります。

ACコード：Submission #2676571 - AtCoder Beginner Contest 100

D - Patisserie ABC

$(x_{i}, y_{i}, z_{i})$ の組 $N$ 個から $M$ 個選び、 $x_{i}, y_{i}, z_{i}$ のそれぞれの「総和の絶対値」の和を最大化する問題。…数式で書いたほうが誤解がなくていいですね。

$\max ( |\sum_{i} x_{i}| + |\sum_{i} y_{i}| + |\sum_{i} z_{i}| )$

さてどう考えるかですが…絶対値というのは元の数に対して、+1倍、-1倍のどちらかになります。これは当たり前のことに見えますが、「2通りしかない」というのが大きな手がかりになります。

求めたい値には絶対値が3つ含まれているので、これを8パターンに場合分けすることができます。書き下すと以下の8つです。

$\max ( + \sum_{i} x_{i} + \sum_{i} y_{i} + \sum_{i} z_{i} )$
$\max ( + \sum_{i} x_{i} + \sum_{i} y_{i} - \sum_{i} z_{i} )$
$\max ( + \sum_{i} x_{i} - \sum_{i} y_{i} + \sum_{i} z_{i} )$
$\max ( + \sum_{i} x_{i} - \sum_{i} y_{i} - \sum_{i} z_{i} )$
$\max ( - \sum_{i} x_{i} + \sum_{i} y_{i} + \sum_{i} z_{i} )$
$\max ( - \sum_{i} x_{i} + \sum_{i} y_{i} - \sum_{i} z_{i} )$
$\max ( - \sum_{i} x_{i} - \sum_{i} y_{i} + \sum_{i} z_{i} )$
$\max ( - \sum_{i} x_{i} - \sum_{i} y_{i} - \sum_{i} z_{i} )$

これを全部計算すれば答えが出ます。 全探索、「間に合う時には」シンプルで強力な解法です。

各符号を決めてしまえば、 $x_{i}, y_{i}, z_{i}$ それぞれに符号を掛けて和を取ったものを $N$ 個計算し、ソートして大きい方から足していけばいいです。

計算量は $O(8 \times N \log N)$ です（8も一応書きました）。 $N \le 1000$ なので全く問題ありません。

ACコード：Submission #2678544 - AtCoder Beginner Contest 100

おわりに

A, Bと少しクセのある問題でした。Dはとても良い問題だったと思います。

ABCオンリーが続いていますが、来週はついにARCが予定されています！頑張りましょう！

2018-06-10

ABC099 参加記録

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

AtCoder Beginner Contest 099 - AtCoder

unratedですが参加しました。

36分台全完で96位。C, Dにペナルティ込みで30分以上費やしていることを考えると「ARCじゃなくてよかった…」と思いますが、けっこう問題が難しめだったので相対的には健闘したほうかも？

f:id:betrue12:20180610232725p:plain

1問ずつ振り返っていきます。

A - ABD

100回目記念で出そうな問題。 $N$ が999以下か1000以上かで場合分けすればOKです。

ACコード：Submission #2643670 - AtCoder Beginner Contest 099

B - Stone Monument

「隣り合った塔の高さの差」は等差数列になっていて、1ずつ増えていきます。

そのため、隣り合った塔の高さの差を見るだけで、それらが何番目の塔で、高さがいくつなのか特定することができます。

具体的には隣り合った塔の高さの差 $b-a$ を $d$ とおくと、

低い方の塔の高さを $h_{1}$ とすると、 $h_{1} = 1+2+...+(d-1)$
高い方の塔の高さを $h_{2}$ とすると、 $h_{2} = 1+2+...+(d-1)+d$

です。そのため、 $h_{2} - b$ で答えが求まります。

$h_{2}$ の求め方は $1+2+...+X = X(X+1)/2$ を使うとよいです。

ACコード：Submission #2644569 - AtCoder Beginner Contest 099

C - Strange Bank

想定解法が分からなくてC問題なのにDPしました。 えー…

$dp(i)$ を $i$ 円引き出すのに必要な操作回数とすると、

$dp(0) = 0$
$dp(i) = 1 + \min(dp(i-1), dp(i-6), dp(i-6^{2}), ..., dp(i-9), dp(i-9^{2}), ...)$

という遷移ができます。 $\min(...)$ の中身は、「1手前」としてあり得る数を全て列挙しています（終端は書き表しにくいので省略していますが、もちろん非負の値だけです）。

これを1から $N$ まで計算すれば $dp(N)$ が答えです。

計算量的に若干の不安がありますが、DPの遷移元である $\min(...)$ の中身の個数は、大雑把に言えば「 $i$ は6や9のおよそ何乗か」なので $O(\log N)$ で抑えられます。そのため全体の計算量は $O(N \log N)$ であり、 $N \le 100000$ なので間に合います。

ACコード：Submission #2646945 - AtCoder Beginner Contest 099

D - Good Grid

問題がややこしいですが、ほぼ全探索に近いやり方で解けます。愚直すぎる全探索だと $O(C^{3} N^{2})$ になるので流石に通りませんが…

「良いグリッド」は、盤面が $(i+j) \mod 3$ で3色に色分けされた状態です。余りが異なるマスの色が被ってはいけません（言い換えると、1色や2色になってはいけません）。

「色が被ってはいけない」という制約を除けば、3色それぞれを独立に考えることができます。 具体的には、余り $k = 0, 1, 2$ および色 $c$ それぞれについて

「 $(i+j) \equiv k \mod 3$ のマスの色を全て $c$ に変えると、コスト（問題文中では「違和感」）の合計はいくつになるか？」

を、独立に計算することができます。各計算において $N \times N$ のマスを全て見るので、この計算量は $O(C N^{2})$ です。（余りの個数である3も考慮すべきですが、今回は定数なので省略）

これを前計算した後に、余りが 0, 1, 2 それぞれについてどの色を使うかを全通り試し、コストの最小値を出します。このとき、色が被っている組み合わせはちゃんと除外しましょう。この計算量は $O(C^{3})$ です。

最大サイズの $N=500, C=30$ で単純に計算してみると、 $C N^{2} = 7.5 \times 10^{6}$ 、 $C^{3} = 2.7 \times 10^{4}$ なので十分間に合う…と思いきやRubyで1500msでした。怖いよー。

ACコード：Submission #2648372 - AtCoder Beginner Contest 099

さいごに

4問振り返ってみました。今回は難しかったんじゃないでしょうか…。

2018-06-05

AtCoder青になりました

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

前回の記事にも書きましたが、AtCoderのレートが1600を突破し、青色になることができました！

f:id:betrue12:20180604224841p:plain

「まずは青を目標に」と思ってやってきたので、とても嬉しいです。TwitterやSlackなどで交流や情報交換などしてくださった方々、本当にありがとうございます。今後ともよろしくお願いいたします。

コンテスト履歴＆ちょっと自分語り

コンテスト履歴はこんな感じです。

f:id:betrue12:20180605201840p:plain

先週の時点でレート1465、あと3～5回くらい良いパフォーマンスが出せれば青に届くなーと思っていたら、自己ベスト大幅更新の数値が出て一気に届いてしまいました。嬉しいより前に、超ビックリしました。AGCこわい。

初参加のABCでパフォ1600とか出してたりしますが、情報系で修士を出てエンジニア6年目、数学もプログラミングも元々好きだったので、最初から経験値の高い状態で競プロを始めています。RPGでいうと「初期レベルの高い途中加入のおっさんキャラ」みたいな感じです。そのぶんレベルアップが遅いです。

あとは自分より10歳以上も若くて実力のある人達が本当にたくさんいて、「負けてられない！」と思って精進した、という面も正直あります。

やったこと

前置きはこのくらいにして、やったことを書いていきます。自分の経験とアドバイスが混ざったりしてますが、少しでも参考になれば幸いです。

過去問を600問くらい解いた

微妙に600に届いていないのですが、現時点のAtCoderでのAC数は594です。使用言語は全てRubyです。

主要コンテストであるABC/ARC/AGCの内訳はこんな感じです。

f:id:betrue12:20180605203219p:plain

既に100000007回くらい言われていることですが、とにかく問題を解くことが一番大事だと、これだけは自信を持って主張できます。

埋めた順番は以下の通りです。

ABCのA～D
AGCのA～B（Cも一応開いて、解けそうなら解いた）
ARCのA～B（ABCと重複してないもの。修行でした）

ただ、ABC-Cにまだ少し苦戦するかなって段階であれば、D問題を後回しにしてA～Cを埋めるのがいいと思います。

あと、意見が分かれるかもしれない解説ACについて。私はABC-C, Dについては、1時間くらい考えて全然思い付かなかったらサクサク解説ACしてしまいました。発想よりもテクニックやアルゴリズムを知っていることが重要な問題は、それを知らない状態で考えていてもなかなか解けないので、早く身に付けてしまったほうが良いと個人的には思います。

ただ解説ACする場合でも、「1度愚直解を書いてTLEを食らう」経験は、時間に余裕があればしてみると良いです。愚直解が書ける、全探索が書けるって、とても大事なことだと思います。

コンテストに出た

とにかくAtCoderのコンテストに出ました。非公式コンテストや企業コンテストにも出ました。AtCoderに登録してから開催されたコンテストは同時開催を除けば全て出ています。

コンテスト後にはTwitterで情報を集めました。あと、解説放送を観ました。これ本当に大事だと思います。

そして本番中に取り組んだけど解けなかった問題は、なるべく翌日にACしました。決して本番中に解けなかったとしても、その問題について考えた数十分は絶対に無駄じゃないと思います。記憶が新しいうちに身に付けて、次回以降に活かしましょう。

総じて言えば、コンテスト大事、復習大事。これに尽きます。

バチャに参加した

特にゴールデンウィークにバチャを開催してくれる人がたくさんいたのでひたすら参加しました。ありがとうございました！

解いたことのある問題は復習になるし、解いたことのない問題は適度な緊張感で臨むことができます。またコンテスト後と同じように、同時に参加していた人とは解法の意見交換ができます。良い事ずくめです。

蟻本を読んだ

ひとくちに「読んだ」といっても、ものすごい分量があるので、未だに全部理解できているわけではありません。ただ、最初から最後まで流し読みはしました。

実装まで含めて理解できていなくても、「こんなことができるアルゴ・データ構造があるよ」っていう記憶が頭の片隅にあると、いざ問題を解く時に思い出せるかもしれません。コーディングは、実際に問題を解いていて必要になった時にしていけばいいと思います。

ライブラリを作った

頻出のデータ構造やアルゴリズムは、実際に問題で使う機会があったときに、再利用可能なクラスや関数にするようにしました。

ほぼ全て蟻本の写経ですが、当然蟻本のコードはC++で私はRuby使いなので翻訳が必要になりました。ただ、翻訳するという作業もコードを理解するのに役立ったと思います。

ライブラリとして別ファイルに切り出しているものは以下です。あまり使っていないものも含まれています。

データ構造（ビットセット、優先度付きキュー、union-find、セグメント木、BIT）
グラフ（ベルマン・フォード、ダイクストラ、ワーシャル・フロイド、木の直径、木の重心、クラスカル、LCA）
平面幾何（凸包、線分の交差）
その他（座標圧縮、素数modの階乗・逆元・二項係数、ナップサック問題、部分和問題、LIS）

f:id:betrue12:20180605220546p:plain

一般的なDFS・BFS、二分探索、しゃくとり法などは関数化しにくいので、その都度書いています。エラトステネスの篩やユークリッドの互除法などはRuby標準ライブラリにあるので持っていません。

もちろん、ライブラリを作りすぎると手で書く頻度が減って定着が遅くなるというデメリットはあります。ただ私は、考察が合っているのにコーディングが間に合わなくて解けないというのがとても悔しいので、なるべくコーディングでは楽をしたいです。

あと早いうちにライブラリを作って積極的に使っていると、バグを踏んで直せたり、足りない機能に気づけるようになります。ライブラリは使えば使うだけ成長するものだと思っています。

言語について勉強した

私の使用言語はRubyです。競プロを始めて以降、公式リファレンスを本当にたくさん読むようになりました。

Rubyの標準メソッドは多彩で、特に文字列や配列の操作についてはとても充実しています。標準メソッドを沢山知っていれば、そのぶん自力で書く処理を減らせるので、読みやすくてバグりにくいコードが速く書けるようになります。

また、とにかく実行速度が気になる言語でもあります。アルゴリズムは解説通りなのにTLE、ということはザラに起こります。どのような処理が遅く、どのような処理が速いのか、色々実験しました。時にはRuby処理系のソースコードを読むこともありました。自分の使っている言語の特性を知るのはとても大事なことだと思います。

同じ言語を使っている人の提出コードを読むのも良いと思います。C++とかだと無限に提出がありますが、RubyだとARC/AGCのACコードは読もうと思えば全部読めるくらいの量しかないので、けっこう読み漁ってます。あとPythonのコードもとても参考になるのでよく読んでいます。

ブログ記事を書いた

コンテストごとに記事を書くようにしたのは最近のことですが、それ以前にもネタがあれば何件か書いていました。

記事を書くのは本当に時間がかかりますが…書いていると自分の理解できてないところが洗い出されます。World Wide Webに公開するというプレッシャーもあるので、追加で調べたり色々と実験するようになります。そうすることで理解が深まり、記憶が定着していきます。コードを書くのとは全く違う脳みそを使っている感じがします。

本当に時間がかかるので（二度目）人によりけりだと思いますが、文章を書くのが好きな人にはオススメです。

さいごに＆次の目標

ということで、長々と色々と書いてきました。既にたくさんの人が同じことを書いているんじゃないかと思いますが、自分なりにまとめてみました。

次の目標ですが、

水色に落ちない（わりと落ちそうでこわい）
ARCで3完する（未達成です。これからはARC-Eを埋めます）
黄色を目指す！！！

月並みですがこんな感じです。あとはまあ、無理をせずに「趣味」として競プロを長く続けていけたらなと。

ここまで読んでくださってありがとうございました。競プロerの皆様、そしてAtCoder社の皆様、今後ともよろしくお願いいたします！

2018-06-04

AGC025 参加記録

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

AtCoder Grand Contest 025 - AtCoder

90分台3完で201位。パフォーマンスは自己最高の2282を叩き出しました。AGC、ハマるとすごい。

f:id:betrue12:20180604201801p:plain

A～Cについて振り返ってみます。Dも本番中に考えていましたが、根本的に解法が違っていたようなので…いずれ、ちゃんと勉強して通します。

A - Digits Sum

公式解説の解法が天才ですが、 $N \le 10^{5}$ なので愚直で通ります。200点を信じろ。

ただ私のコードがあまりに愚直すぎて、 $N = 10^{5}$ の手元実行で1.5秒くらいかかってたので、ビビって対称性を利用して範囲を半分にしました。色々と真似してはいけないコードになりましたが、通ったのでよし。

本番コード（真似してはいけない）：Submission #2606932 - AtCoder Grand Contest 025
もうすこしマシな愚直コード：Submission #2617672 - AtCoder Grand Contest 025
公式解説の方法を使ったコード：Submission #2617683 - AtCoder Grand Contest 025

B - RGB Coloring

各色のブロックの点数が

赤色： $A$
緑色： $A+B$
青色： $B$
無色： $0$

であり、 $N$ 個のブロックの合計点数を $K$ にする。ということは、 $a, b$ を $0$ 以上 $N$ 以下の整数として $aA+bB=K$ が成り立っている必要があります。この時点で、この式を満たす $(a, b)$ の組それぞれについて数え上げを行い全部足す、という発想が浮かびます。

このような $(a, b)$ の組は、 $A, B$ が十分大きくて互いに素だったりすると数が減るのですが、残念ながら制約上は $A=B=1$ みたいなこともあり得るので、最大 $N+1$ 個あると思っておいたほうが良いでしょう。

では $(a, b)$ を固定した時に、赤、青、緑の内訳としてはどのようなものが考えられるでしょうか。緑の個数を $g$ とすると、赤の個数は $a-g$ 、青の個数は $b-g$ となります。なのであり得る緑の個数全てについて計算すれば、あとはひたすらcombinationを計算して答えにたどり着きますが…

TLEコード：Submission #2608378 - AtCoder Grand Contest 025

まあ、当然間に合いません。ダメ元で投げたらやっぱりダメでした（よくない）

$(a, b)$ の組を全部試すのがよくないのか、緑の個数を全部試すのがよくないのか。「緑の個数を全部試さなくていい方法はないかなあ」と考えていると、 赤と青を独立に塗って、たまたま重なったものは緑とみなす という発想が浮かびました。…何で浮かんだのかは自分でも分かりません。

というわけで無事に、 $(a, b)$ の組を全部試す1重ループで解けました。コンテスト本番特有の無駄な保険コードとかが入ってますが気にしないでください。

本番コード：Submission #2609206 - AtCoder Grand Contest 025

ちなみに…上記コードの上半分は、素数modでの組み合わせ（二項係数）を計算するライブラリです。使う問題はけっこう多いので用意しておいたほうが良いと思います。せっかく考察が合っているのにここが原因でACできないのは、やっぱりもったいないですよね（過去に1敗）

素数modの二項係数は、解説やコード例も含めて蟻本などに載っていますが…Rubyだと蟻本の方法では逆元計算だけでTLEしてしまうので、以下のブログで紹介されている方法を用いています。

Tech Tips: 素数を法とする世界の逆元をまとめて計算

私も他の人の提出コードをきっかけに知ったので、何か名前が付いているアルゴリズムなのかどうかも分かっていませんが…遅い言語を使っている人は是非活用してください。

C - Interval Game

高橋くんがぴょんぴょんする問題。

青木くんは高橋くんを沢山動かしたい。高橋くんはなるべく動きたくない。どういう動きになるのか厳密に考察するのは難しいですが、何となく青木くんの戦略としては、高橋くんを左右交互に動かしまくる のがいいんじゃないかと思います。

具体的なイメージを掴むため、サンプルを図示してみましょう。入力例3が一番イメージしやすいです。

f:id:betrue12:20180604214811j:plain

動作のイメージは以下のような感じです。あえてアルゴリズムっぽく言えば貪欲法です。

高橋くんをできるだけ大きく右に動かすため、青木くんは「一番右側にある区間」を選ぶ。高橋くんはなるべく動きたくないので、その区間の左端に移動する。
今度は高橋くんを左に動かすため、青木くんは「一番左側にある区間」を選ぶ。高橋くんはその区間の右端に移動する。
これを、「高橋くんが動かなくてもよくなる」まで繰り返す。

この記述で曖昧なところを、より厳密に考えてみます。

まずは「一番右側にある区間」。区間が重なっていたりすると一意に決めづらいですが、高橋くんが動くのは選んだ区間の左端なので、これは「まだ使っていない区間のうち、左端が一番右側にあるもの」を選ぶべきです。「左側」についても同様です。

次に「高橋くんが動かなくてもよくなる」とはどういうことか。単純に「一番右側にある区間の左端」→「一番左側にある区間の右端」と動いていくと、いずれこれはクロスする可能性があります。

f:id:betrue12:20180604225825j:plain

上図のように、クロスした後も「右端」「左端」と動き続けるのは、高橋くんにとって無駄です。

クロスしたということは、左端は現在地より左側に、右端は現在地より右側にあるので、高橋くんの現在地は区間に入っているはずです。そのため高橋くんはその位置からじっと動かず、最後に原点に戻りさえすればいいですね。

これで動きがシミュレーションできますが…最後に大事な点がひとつ。それは高橋くんを 最初に一番右側の区間に動かすべきか、一番左側の区間に動かすべきか はケースバイケースだという点です。どっちでも変わらないという場合もありますが、例えばサンプル2では結果が変わってきます。泥臭いですが、どっちも試して大きい方を取るのが堅実だと思います。

本番中に通したコードは以下です。上記の「最初どっちに動かすか」の2通りをコピペで処理しているのでコードが長くなっています…

本番コード：Submission #2610818 - AtCoder Grand Contest 025

もっと本質的な考察をして無駄を省いたり複数のケースを同一視できるようになると、地道なシミュレーションよりも簡潔な論理で解くことができて、その極致が以下のようなコードなんだと思います。これはすごい。

touristのコード：Submission #2609185 - AtCoder Grand Contest 025

さいごに

というわけでAGCの前から3問を振り返ってみました。ペナルティ込みで90分、決してスラスラ解けたわけではありませんが…3完できたのはとても嬉しいです。

そして…このコンテストでレートが1600を突破し、青色になることができました！

f:id:betrue12:20180604224841p:plain

というわけで次の記事は「AtCoder青になりました」の予定です。

2018-06-03

codeFlyer予選参加記録

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

codeFlyer （bitFlyer Programming Contest） - AtCoder

初めて参加した企業コンテスト。結果は30分台3完で159位でした。

f:id:betrue12:20180603102618p:plain

企業コンテストは変わった問題が出たり配点基準がいつもと違ったり…という話を聞いていましたが、今回は普通だったと思います。ABC/ARCでも出そうな問題。

解けたA～Cと、解こうとして解けなかったDを振り返っていきます。

A - 本選参加者数

$A$ 人以下でかつ $B$ 人の倍数となる最大の人数を求める問題。

$A$ 人から $B$ 人で割った余り（あぶれる人）を切り捨てる　と考えると、 A - A%B
$A$ 人から $B$ 人の組がいくつできるかを求めて $B$ 倍する　と考えると、 A/B * B

など何通りか書き方がありますが、最初に思い付いたものを素直に書いてしまえばいいと思います。（サンプルはもちろん通しましょう）

ACコード：Submission #2596471 - codeFlyer （bitFlyer Programming Contest）

B - 洋菓子店

問題文をよく読んで、その通りの動きをコードにすると解けます。解説書くのが難しいですね…

ACコード：Submission #2597462 - codeFlyer （bitFlyer Programming Contest）

C - 徒歩圏内

この問題からちょっと詳しく振り返ってみたいと思います。

C - 徒歩圏内

数直線上に点がたくさんあるので、以下のような位置関係になっている3点のトリオを数え上げてください、という問題。数式で書くと $i \lt j \lt k$ かつ $X_{k} - X_{j} \le D, X_{j} - X_{i} \le D, X_{k} - X_{i} \gt D$ をすべて満たすものです。

f:id:betrue12:20180603110024j:plain

愚直解は3点のトリオを全て調べる $O(N^{3})$ です。当然間に合いません。

各点は数直線上に座標順に並んでいるので、 「距離が $D$ 以下であるか」には単調性があります 。二分探索やしゃくとり法が使えそうです。全ての点それぞれに対して「右側にある距離 $D$ 以下の点の数」を求めることは、しゃくとり法を使うと $O(N)$ でできます。もちろん左側も同様です。

f:id:betrue12:20180603113609j:plain

そのため、例えば3点のうち左側の2点を固定してしまえば、前計算したしゃくとりの結果を使って条件を満たす右側の1点の範囲がすぐに計算できます。これで $O(N^{2})$ に落ちますが…入力サイズが $N \le 10^{5}$ なのでそれでも間に合いません。まだ落とす必要があります。

元の条件をそのまま考えて $O(N^{2})$ 未満に落とすのはかなり難しそうだと思い、「 いくつかの場合分けに分割して、足し算する 」や「 少し広い条件を考えて、余計なぶんを引く 」のような、条件の変形ができないか考えてみます。

ここで 3点の組を数え上げるときに、真ん中を固定すると楽 ということを思い出します。この考え方は、以下の問題からの類推でした。

C - Snuke Festival

真ん中を固定すると、左右それぞれにある「距離 $D$ 以下の点の数」は前計算したしゃくとりの結果を使えます。それらを掛け算すると、真ん中を $J$ に固定したときの $X_{k} - X_{J} \le D, X_{J} - X_{i} \le D$ を満たすトリオの数になります。全ての「真ん中の点」についてこれを足し算すれば、「答えに近いもの」が求まります。これがそのまま答えにならない理由は、もう1つの条件である $X_{k} - X_{i} \gt D$ が考慮できてないからです。

というわけで、上記のうち $X_{k} - X_{i} \gt D$ を満たさないもの、つまり3点全てが距離 $D$ に含まれているものを数えて引き算します。これは、左端を固定した時に「右側にある距離 $D$ 以内の点」から2個を選べばよくて、これもしゃくとりの前計算が使えます。

これで答えが計算できます。振り返ってみると、いくつかのテクニックの組み合わせが要求される問題だったなと思います。ABC/ARC-D 400点でも、このくらいは出そうですね。

1次元上の点がソートされている時、距離には単調性があるので、しゃくとり法を使う（二分探索でも可です）
数え上げの条件が扱いにくい場合、少し広い条件を考えて、余計なぶんを引く（これの発展が「包除」ですね）
3点のトリオを、真ん中を固定して数え上げる

ACコード：Submission #2599368 - codeFlyer （bitFlyer Programming Contest）

※余談ですが、（現時点での）公式解説の書き出しにミスがあるのでご注意ください。公式解説の書き方を真似つつ修正するなら、以下が正しいと思います。

$i \lt j \lt k$ かつ $X_{k} - X_{i} \le D$ を満たす $(i, j, k)$ の個数 $A$
$i \lt j \lt k$ かつ $X_{j} - X_{i} \le D, X_{k} - X_{j} \le D$ を満たす $(i, j, k)$ の個数 $B$

答え： $B - A$

D - ハンコ

数え上げの問題。公式解説とは少しだけ違った解き方をしています。

最大サイズだと紙には $HW = 10^{18}$ 個のマスがあるため、1個ずつ数えていては間に合いません。何とかして、まとめて数える必要があります。

ハンコの中のあるマスが黒であるとき、その黒マスによって塗られる領域は以下のようになります。四隅の赤がハンコのサイズです。

f:id:betrue12:20180606201143p:plain

例えば、真ん中あたりの領域は1つ黒があっただけで全部塗られてしまいます。これはまとめられそうです。

上下左右の領域（赤いところを除く）もまとめられそうです。例えば左側の領域を考えると、ハンコを紙左端に沿って上下に動かしたときに「ハンコの中で一番左にある黒マス」が縦線を引きます。そこから右側は全て塗られます。上下左右、それぞれ同様です。

ということで、紙の領域を以下のように分けて考えます。

f:id:betrue12:20180606202240p:plain

A領域：四隅でハンコがあまり届かない場所なので、ちょっと数えにくい。
B領域：左端と右端。それぞれ、ハンコのうち最も左にある黒マスと、最も右にある黒マスを考えればいい。それよりも内側のマスは全部塗られる。
C領域：上端と下端。B領域と同じ考え方ができる。
D領域：真ん中。ハンコに1つでも黒マスがあれば全て塗られる。

上図は、 $H, W$ がともに十分大きい時の分け方です。例えば $W$ が $2M$ 以下の場合は、下図のようにC領域とD領域は潰れます。

f:id:betrue12:20180606202535p:plain

$H, W$ がともに小さいと、B領域も潰れてA領域だけになります。このあたりは場合分けが必要です。

さて最後に残ったA領域ですが、最大サイズは $2N \times 2M = 4 \times 10^{6}$ です。できれば $O(NM)$ 以下で計算したいところです。

領域内のマスが最終的に黒マスになる条件は、ハンコの黒マスが作る長方形のうちいずれか1つ以上に含まれていることです。

f:id:betrue12:20180606203911p:plain

このように長方形がたくさんあって、各座標点が長方形に属しているかどうかや、その個数などを求めたい。そんな時に役立つのが「いもす法」です。

https://imoz.jp/algorithms/imos_method.html

上記のページで丁寧に解説されていますが、二次元の理解はなかなか難しいんじゃないかと思います。自分なりの理解を表した図を描いてみました。

f:id:betrue12:20180606210307p:plain

この方法を使えば、長方形を「4つの点」として考えることができます。全ての長方形について4点を取り終わったあと、まとめて累積和を取ることで、長方形領域の重ね合わせが効率的に計算できます。

これでA領域も計算できるので、全ての領域の黒マスが計算できました。

本番中は処理速度ゆえのTLEが取れずに結局通せませんでしたが、細かい書き方を改善することでACすることができました。

ACコード：Submission #2605290 - codeFlyer （bitFlyer Programming Contest）

なお、公式解説では大まかな考え方は同じですが、図のB～D領域を縦横それぞれ1マスに圧縮し、二次元いもす法を行った後に引き伸ばす、という方針になっています。

2018-05-29

AtCoder ARC098 参加記録

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

復習を兼ねて、参加記録をなるべく書くようにしたいなと思います。

結果は2完・17分台で270位でした。Eとずっと格闘してましたが結局通せませんでした…。パフォーマンスは1861。

f:id:betrue12:20180528205015p:plain

解けたCDと解けなかったEを、1問ずつ振り返ります。解法だけではなく思考の過程を書いていくので少し冗長かもしれませんが、公式解説にない情報をちょっとでも付与できたらと思っているので、参考になる部分があれば幸いです。

C - Attention

似たような過去問をたくさん解いていると直感で 累積和 またはそれに似た解法が思い浮かぶかもしれませんが、少し丁寧に書きます。

誰かがリーダーになったときに、他の人が向きを変えるかどうかは、その2人の位置関係で決まります。

そのため例えば、西から1番目の人がリーダーになろうが、2番目の人がリーダーになろうが、彼らより東にいる他の人達にとってはどうでもいいです。どっちがリーダーになっても、リーダーは自分より西側にいるので。

さらに一般化すると、 リーダーを $i$ 番目の人から $i+1$ 番目の人に変更することは、その2人以外の人にとってはどうでもいい ということが分かります。

そのため、

1番目の人がリーダーになった時の、向きを変える人数を調べる
リーダーを2番目の人に変更する。1番目の人はリーダーでなくなるので、向きを変える必要がある場合は+1。2番目の人はリーダーになるので、さっき向きを変えていた場合は-1。
これを端まで繰り返す。

で、全てのパターンを試せます。累積和というよりは、リーダーを変更した時の差分を見て効率的に計算、という感じですね。

もちろん、「 $i$ 人目より左にいて左を向いている人数」と「 $j$ 人目より右にいて右を向いている人数」を累積和で事前に全部計算しておけば、リーダーを決めた際に向きを変える人数が一発で求められるので、それでも良いです。2つの方法で、やっていることは結局あまり変わりません。

本番中にACしたコードが以下です。

Submission #2562967 - AtCoder Regular Contest 098

D - Xor Sum 2

この問題は以前出題されたXor Sumの続編であり、前作がABC範囲としては非常に難しい問題だったため、タイトルを見てヒィッと思いました。ただ前作よりも難易度は低く、前作の知識も使えたのでイメージほど苦戦はしませんでした。

具体的には、(xorでの総和) $\le$ (+での総和) という知識が役に立ちました。これは、「xorは+の繰り上がりを無視したものと同じ」と思うと理解しやすいと思います。そして、繰り上がりが1度でもあると両者の値は一致しなくなります。

そこから、「 値が一致しない状態からさらに範囲を広げてもダメ 」という発想に至り、しゃくとり法にたどり着きました。本番中のACコードは以下です。

Submission #2564362 - AtCoder Regular Contest 098

ところでこの「値が一致」判定、私は単純にxorと+を独立に計算して == で比較していました。この方法の他に、「繰り上がりが起こるのは両方のビットが1のとき」という性質から & を使って判定しているコードもありました。比較していませんが、多分 & のほうが速いんじゃないかと思います。

あとは地味な補足ですが、しゃくとり法って「右端を進めて区間に入れる」処理と「左端を進めて区間から除く」処理が必要なんですよね。だいたいこれらは逆演算になるので、今回は「xorの逆演算って何？」って知識が必要です（答えはxorです）。基礎知識だと言う人も多そうですが、初めて考える人には思い付きづらいかもしれません。あると便利な知識です。

しゃくとり法についての解説は是非こちらをお読みください！素晴らしい記事です。

しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ

E - Range Minimum Queries

本番中に通せなかった問題。タイトルに釣られてRMQのセグメント木使えないかなとか考えましたが（単純）、最初の取っ掛かりとして 小さい方から見て1番目と $Q$ 番目の差は必ず解の候補になる というところから考えました。一番小さいものから順に取っていくことは、数列の配置によらずできるからです。

では、2番目と $Q+1$ 番目の差は解の候補になるか？と考えたときに、必ずしもそうでないことが分かります。最小の値を2番目にしようと思うと、1番目の値を「避けて」区間を選び続けなければなりません。そうなると、孤立して選べない数が出てきます。

一般化すると、 $i$ 番目を最小にしたいならば、 $i-1$ 番目までの数を全て避けて区間を選び続けなければならない ということになります。最小値を固定すると考えやすくなり、制約もまあまあ小さめなので、最小値を固定して全部試そうと思い至ります。

「避けなければいけない値」で数列は分割され、それらをまたがるように範囲を選ぶことはできません。部分列それぞれからいくつ値を取れるかは、例としては以下のようになります。式で書くと $(部分列長)-K+1$ 個（負になるときは取れない）です。

f:id:betrue12:20180528235029j:plain

ここまでは想定解法と同じです。…で、ここで私が始めたのは最大値の二分探索です。

Submission #2569443 - AtCoder Regular Contest 098

確かに最大値に単調性はある。計算の答えは（きっと）正しい。計算オーダーも $O(N^{2}\log N)$ でいける…と思いましたが、さすがに無駄が多すぎましたね。

というわけで、コンテスト後に想定解法である「分割された列をソートして小さいほうから取れるだけ取る」方法を実装しました。

最初は分割された列たちをどう管理するのかイメージが付きませんでしたが、実装のやり方として2通り思い付き、それぞれ書いてみました。

まずは、実際には列を分割「しない」方法です。分断箇所をフラグで管理しておき、数列を普通に最初から見ていきます。分断箇所に当たった時点で、そこまでの部分列を処理します。最後に「番兵」を置かないとバグります。

Submission #2573110 - AtCoder Regular Contest 098

次に、実際に列を分割「する」方法です。列を1つずつ見ていって、分割箇所を探してそこで列を分けます。たくさんの列の中から分割箇所を見つけるのは一見大変そうですが、見る要素の数は合計で結局 $N$ 個なので大丈夫です。ただRubyの場合は配列の破壊的操作を上手く使わないと結局遅くなりそうです。

Submission #2573193 - AtCoder Regular Contest 098

さいごに

以上3問、私なりの思考と実装方針をまとめてみました。

CD速解きができたのでパフォーマンスは良かったですが、逆にたっぷり時間をかけてEが通らなかったのは悔しいですね。しばらくは「ARC/AGCで3完する」が毎回の目標になりそうです。