ARMERIA

放置していたけど更新再開、Rubyと競技プログラミングの話が中心になっていく予定です

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

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

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

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

f:id:betrue12:20180715082653p:plain

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

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

H - 新入生歓迎数列 - Hard

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進数よりも思いつきやすいのかな…?と個人的には思いました。

AGC026 参加記録

AtCoder Grand Contest 026 - AtCoder

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

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

f:id:betrue12:20180714233449p:plain

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

A - Colorful Slimes 2

A - Colorful Slimes 2

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

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

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

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

D - Derangement

B - rng_10s

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

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完できてよかったです。いつか橙パフォを出したいですね。

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

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

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

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

f:id:betrue12:20180708131909p:plain

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

A - UkuNumber

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

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完はけっこう上出来なんじゃないかと思います。ゆかもちさんありがとうございました!

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

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

A - F

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

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

B - Acrostic

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

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 が一般の場合でも同じことが言えます。そのため、

  1. 隣り合う2項だけを考え、その全ての場合(  n^{2} 通り)に対して、差が  d となる場合を数える。差が  d となった場合美しさは+1、そうでない場合+0されるので、平均は(差が  d となる場合の数)/(全ての場合の数)となる。*1
  2. それを「隣り合う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

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

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

ARC100 参加記録

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

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

f:id:betrue12:20180701235243p:plain

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

C - Linear Approximation

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

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

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

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

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

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

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

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

さいごに

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

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

脚注

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

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

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

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

codeFlyer (bitFlyer Programming Contest)オープンコンテスト - AtCoder

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

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

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

f:id:betrue12:20180630214549p:plain

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

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

A - 値札

A - 値札

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

ACコード:Submission #2758182 - codeFlyer (bitFlyer Programming Contest)オープンコンテスト

B - 交通費

B - 交通費

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

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

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

f:id:betrue12:20180630220207p:plain

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

  1.  X_{i} \lt C - D である  X_{i} に対しては、交通費は  D 。個数が分かれば(個数) ×  D でまとめて計算できる。
  2.  C - D \le X_{i} \lt C である  X_{i} に対しては、交通費は  C - X_{i}
  3.  C \le X_{i} \lt C + D である  X_{i} に対しては、交通費は  X_{i} - C
  4.  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} で計算可能です。

これで全ての計算を効率的に出来る方法が揃ったので、実装すれば解けます。

これらを図に描き足してみました。文章と図、分かりやすいほうで理解していただければと思います。

f:id:betrue12:20180630221845p:plain

ACコード:Submission #2758650 - codeFlyer (bitFlyer Programming Contest)オープンコンテスト

C - 部分文字列と括弧

C - 部分文字列と括弧

「括弧の対応が取れている文字列」は、AtCoderの過去問でもいくつか出題されている題材ですが、

  • ( を+1、) を-1として累積和*3を取った時に、
    • 最後にちょうど0になる
    • 途中で一度も負の値にならない

を満たすものとして考えることができます。途中で負の値になるものというのは、例えば )( みたいなやつです。

求めるのが「区間の数」ということでしゃくとり法を考えたくなりますが、残念ながら単調性が成り立ちません。

どう考えるかですが、「最初から計算した累積和」を折れ線グラフとして図示してみると、見通しがよくなります。

f:id:betrue12:20180630223820p:plain

過去に出現した「そこまでの累積和が同じ点」を始点とすれば、「最後にちょうど0になる」の条件を満たせます。これを数えるには、「累積が  X になった点の数」を配列やmapなどで管理しておけばよいです。

「途中で一度でも負にならない」のほうの条件は、「区間内に、始点&終点の累積和を下回っているところがない」となります。これをどう実装すればいいか考えてみます。

f:id:betrue12:20180630224829p:plain

( によって+1されて累積和が  X になったとすると、それより前の点は累積和  X で揃える区間の始点として使うことはできません。そのため、一度「累積が  X になった点の数」をリセットして数え直します。

以上の内容を実装すれば解けます。hash[0] = 1 を書きそこねると文字列の一番最初から始まるパターンを数え漏らすので注意しましょう。(1敗)

ACコード:Submission #2759109 - codeFlyer (bitFlyer Programming Contest)オープンコンテスト

F - 配信パズル

F - 配信パズル

間の2問を飛ばして何でFが解けているんだって感じですが…実は過去問に類題があるので、それを覚えていると難易度が下がります。

F - Flip and Rectangles

詳しくはこの問題の解説を参照していただきたいのですが、「行または列の色反転を繰り返すことで、全体を同じ色にできる」ことと「全ての2×2成分について、その中に含まれる黒マスが偶数個である」ことが同値になります。

「2×2成分」は、その中心にある交差点*4と対応付けることができます。解説にならい、周囲の黒マスが奇数個である交差点を「悪い交差点」と呼びます。

さて、各クエリごとに行う操作は

  1. 前回配信された盤面と差分が1マスだけの盤面が配信されてくる
  2. 最大1回、盤面の中の長方形領域を指定し、領域中の全てのマスの白黒を反転させることができる
  3. 行または列の色反転を好きなだけ行うことができる

です。最後に目的を達成できるかどうか、逆から考えてみましょう。

操作3によって全マスを同じ色にできる条件は先ほど示した通りなので、

  • 操作3の開始時点で、悪い交差点が0個であればよい

です。そのため、操作2によって悪い交差点を0個にできる条件について考えます。

f:id:betrue12:20180630231737p:plain

「長方形領域を指定し、領域中の全てのマスの白黒を反転」することで、その四隅(外周を除く)にある交差点の「周囲の黒マスの偶奇」が変化します。それ以外の交差点は、周囲のマスで反転するものが偶数個なのでそのままです。

これを考慮すると、操作2によって悪い交差点を0個にできる条件は、

  • 悪い交差点が0個
  • 悪い交差点が1個。どこでもよい
  • 悪い交差点が2個で、縦または横に並んでいる
  • 悪い交差点が4個で、長方形を作るように並んでいる

のいずれかです。

ここまでくればあと一息です。各盤面について「悪い交差点」を列挙すればよいのですが、全部の交差点を毎回計算していると間に合いません。

配信される盤面は「前回との差分は1マスだけ」ということに着目します。1マスだけ反転することで、影響を受ける交差点は周りの最大4つです。

f:id:betrue12:20180630232630p:plain

そのため、その1マスの周囲の交差点について、悪い交差点かどうかを反転させればよいです。これで計算量を抑えられます。

まとめると、以下のような解き方になります。

  1. 最初の盤面について悪い交差点を列挙する。
  2. 悪い交差点を0個にできる条件に応じてYes/Noを判定する。
  3. 次の盤面で反転している1マスについて、その周囲の交差点(最大4つ)が悪い交差点かどうかを反転させる。
  4. 悪い交差点を0個にできる条件に応じてYes/Noを判定する。
  5. 以降、繰り返し。

ACコード:Submission #2759805 - codeFlyer (bitFlyer Programming Contest)オープンコンテスト

このコードはC++です。「Flip and Rectangles」の方でもRubyだと前計算だけでTLEした経験があり、絶対間に合わないと踏んで最初からC++で書きました。まだ速い書き方に慣れてなくて制限時間もギリギリなのですが、通ってよかったです。

おわりに

解けた問題だけの解説ということでちょっといびつな感じになりましたが、どれもなかなか解説しがいのある問題でした…。

この記事の作成時点ではまだ公式解説が公開されていないので、少しでも理解の助けになれば幸いです。

明日はABC/ARCがあります!ratedコンテストでも良い成績を残していきたいですね。こちらも頑張りましょう。

脚注

*1:等号はどちらにあっても構いませんが、ダブって数えないように注意。

*2:2は符号を反転させたものなので、同じ方法でできます。

*3:プログラマ的に言うと、「ネストの深さ」として理解すると分かりやすいかもしれません。

*4:辺の交点のうち外周に含まれないものを「交差点」と呼んでいます。

ARC099 参加記録(WIP)

AtCoder Regular Contest 099 - AtCoder

今回は26分台1完で685位、ダメダメな結果でした…

f:id:betrue12:20180624190725p:plain

レートも大きく下がり、水色に戻ってしまいました。次頑張ります。

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

C - Minimization

C - Minimization

「最初,この数列の要素は  1,2,...,N を並び替えたものになっています.」 という記載が重要で、これを見落とすと無駄に難しい問題を解くハメになります。(1敗)

「選んだ範囲内の値をその中の最小値で置き換える」という操作で全ての要素を等しくしたいので、最終状態では全ての要素が全体の最小値、つまり1になります。そして上記の条件から、初期状態では1が存在するのは1箇所だけです。

そのため、問題は以下のように単純化できます。

  • 初期状態では1が1つだけ
  • 1を含む幅  K の範囲を選択することで、その範囲の数値を全て1にできる
  • 全ての要素を1にするために必要な操作は何回か?

具体的には最初に1を含む範囲を取って、そこから広げていくような操作になりますが、最初の範囲の取り方を間違えるとムダが出てしまいます。少し発想を変えて、「隣同士で共有部分を持ちつつ、全体をムダなく覆う範囲の取り方」 を考えます。

f:id:betrue12:20180624195036p:plain

この範囲たちを最初に全部決めてから、1が含まれているものから順に選んでいけば、最小の範囲数で全体を1にできます。共有部分*1があることを考慮すると、1つ目の範囲では  +K 、2つ目以降の範囲では  +(K-1) だけカバー可能な数が増えていくので、その合計が  N に到達するのに必要な範囲数を求めればよいです。

スマートなACコード:Submission #2739168 - AtCoder Regular Contest 099

一応、最小値が1つだけという条件を見落としても解けないことはないです…

問題文を見落としたACコード:Submission #2722704 - AtCoder Regular Contest 099

D - Snuke Numbers

D - Snuke Numbers

本番中には解けませんでしたが…

すぬけ数がどんな形になるのか直感的に分かりづらいのと、サンプルの情報がとても少ないので、まずは値が小さい範囲で実験してみます*2

Snuke Numbers実験用スクリプト · GitHub

最後のほうの値は正確ではないので一部切っています。すぬけ数のおおよその形を掴むことができます。

[1, 2, 3, 4, 5, 6, 7, 8, 9, 19, 29, 39, 49, 59, 69, 79, 89, 99, 199, 299, 399, 499, 599, 699, 799, 899, 999, 1099, 1199, 1299, 1399, 1499, 1599, 1699, 1799, 1899, 1999, 2999, 3999, 4999, 5999, 6999, 7999, 8999, 9999, 10999, 11999, 12999, 13999, 14999, 15999, 16999, 17999, 18999, 19999, 20999, 21999, 22999, 23999, 24999, 25999, 26999, 27999, 28999, 29999, 39999, 49999, 59999, 69999, 79999, 89999, 99999, 109999, 119999, 129999, 139999, 149999, 159999, 169999, 179999, 189999, 199999, 209999, 219999, 229999, 239999, 249999, 259999, 269999, 279999, 289999, 299999, 309999, 319999, 329999, 339999, 349999, 359999, 369999, 379999, 389999, 399999, 499999, 599999, 699999, 799999, 899999, 999999, 1099999, 1199999, 1299999, 1399999, 1499999, 1599999, 1699999, 1799999, 1899999, 1999999, 2099999, 2199999, 2299999, 2399999, 2499999, 2599999, 2699999, 2799999, 2899999, 2999999, 3099999, 3199999, 3299999, 3399999, 3499999, 3599999, 3699999, 3799999, 3899999, 3999999, 4099999, 4199999, 4299999, 4399999, 4499999, 4599999, 4699999, 4799999, 4899999, 4999999, 5999999, 6999999, 7999999, 8999999, 9999999, 10999999, 11999999, 12999999, 13999999, 14999999, 15999999, 16999999, 17999999, 18999999, 19999999, 20999999, 21999999, 22999999, 23999999, 24999999, 25999999, 26999999, 27999999, 28999999, 29999999, 30999999, 31999999, 32999999, 33999999, 34999999, 35999999, 36999999, 37999999, 38999999, 39999999, 40999999, 41999999, 42999999, 43999999, 44999999, 45999999, 46999999, 47999999, 48999999, 49999999, 50999999, 51999999, 52999999, 53999999, 54999999, 55999999, 56999999, 57999999, 58999999, 59999999, 69999999, 79999999, 89999999, 99999999]

この数列から、以下のようなことが観察できます。

  • 2桁以上の数は、末尾が9で埋まっている
  • どのくらい9で埋まっているかは固定されていないように見える(1099はあるけど、2099はない)
  • 遷移として、以下の2パターンが存在する
    • 9で埋まっていない最小の桁に1を足す(9→19、1099→1199、1999→2999)
    • 9で埋まっている範囲のうち一番高い桁に1を足し、繰り上がる(999→1099、19999→20999)

エスパーで解く

とりあえずこれらの観察を証明抜きで全面的に信頼すると、遷移として考えられる2パターンのうち、  \frac{n}{S(n)} が小さいほうを取れば次のすぬけ数が求められそうな気がします…が、この方法は通りません。より上のほうの桁で、99999999999999→100999999999999のような遷移が登場するからです。

(このような遷移を本番中に発見できるかはともかく、)これを考慮して、もう少し遷移の候補を広く考えることにします。「(最上位の0も含めて)どこかの桁に1を足す」を全部探索することにします。

結果的にはこれで、ACが取れます*3

Submission #2739590 - AtCoder Regular Contest 099

より高速なエスパー

すぬけ数の「差」を取ってみます。

[1, 1, 1, 1, 1, 1, 1, 1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000]

すぬけ数の差を数列としてみると、初項が1で、2番目以降の項は「前の項と同じ数」または「前の項の10倍」になっていることが分かります。そのため、差を2通り試して \frac{n}{S(n)} が小さいほうを取る、という方法が考えられます。

例えば、8→9の差は1なので、9の次の数の候補としては「+1した10」と「+10した19」を試す、という感じです。これでもACが取れます。

Submission #2739671 - AtCoder Regular Contest 099

ちゃんと証明して解く(未)

ちゃんと証明しようとする場合も、遷移先の候補をいくつかに絞って、それ以外の値をとった場合はすぬけ数にならないことを示すことになりそうです。公式解説PDF*4がそういった方針になっているように見えますが、まだ飲み込めていないです。

解説放送で話されていた方法は上記のエスパーより少し遷移の候補が広いですが、そのぶん証明が楽そうです。

もし可能であれば、「より高速なエスパー」で示したような2つの候補だけを考える方法を、証明(または反証)してみたいです。

さいごに

まずはC問題の問題文を読み落としたのが痛いですね…たらればですが、これを最初に読み落としてなければ10分以内には解けていたと思います。

D問題はとても面白い問題だっただけに、本番で通せなかったのが悔やまれます。計算量が予測できずTLEを恐れてしまったこともあり、「ある程度候補を絞ってからの全探索」よりも「一発で次の値が求まる必勝法」を探そうとしてしまいました。

反省内容の多い回でした。今後に活かさなければと思います。

脚注

*1:「のりしろ」と表現されている人がいました。上手い喩え!

*2:このスクリプトをN=10の16乗くらいまで回せば解が出ますが、O(NlogN)なのでこれを提出コード内でやると余裕でTLEです。高速な言語で手元計算して埋め込みACするには使えるかもしれません

*3:n/S(n)を計算するにあたり、本来は浮動小数の有効桁数を考慮する必要がありますが、今回はnが10の15乗以下なのでさほど問題はありません。より高い値を計算する場合は、後述の候補2つだけを用いる方法を使い、通分して整数演算に持ち込むと良いです。

*4:誤植があると思うので、そのへんも整理してまとめたいです。