ARMERIA

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

解説記事リクエストの募集をはじめました

アルメリアです。いつも記事を読んでいただきありがとうございます。

このたび、競プロ解説記事のリクエスト募集を始めます。過去の問題の記事も少しずつ増やしていきたいのと、せっかく書くなら困っている人の助けになれればいいかなと思ったので。

受付には以下の「お題箱」を使います。

odaibako.net

全部にお応えできるかは分かりません(なるべく頑張ります)。「問題を投げておくと忘れた頃に解説記事が生えているかもしれない」くらいの気持ちでいてもらえると助かります。

一応、ガイドライン的なものを書いておこうと思います。ゆるーく運営していきますので、ゆるーく投げていただければ。

【対象問題】

  • AtCoderCodeforcesの問題だとありがたいです。他サイトでもOKですが、私自身が全然解いていないので…
  • あんまり難しい問題だとそもそも私が解けないので、お手柔らかにお願いします。AtCoder基準で1000点以下なら何かしらの記事は書けると思います。

【必須】

  • 問題のURLは付けておいてください。

【推奨】

  • 差し支えなければレーティングの色を書いておいてください。記事を書く際に大いに参考になります。

【あればベター】

  • 「公式解説のここが分からない」みたいな一言があると、そこを重点的に補足するような書き方ができるのでありがたいです。

【その他】

  • 基本、無記名で大丈夫です。書いてもらってもいいですけど…。
  • もしかしたらその問題の記事を既に書いているかもしれないので、一度ブログの検索窓に問題名を入れて確認してみてください。
  • いつも通り「公式解説の行間を埋めるような、ちょっと丁寧な解説」を目指しますので、投稿前に是非まずは公式解説を読んでみてください。それでもよく分からない場合、お気軽にどうぞ。

AtCoder Beginner Contest 126 F - XOR Matching

F - XOR Matching

解法

結論を書いてしまうと、以下のような数列がもし作れれば答えになります。

f:id:betrue12:20190520210750p:plain

イデアとしては、まず  K を挟んで  K 以外の数字を鏡写しに並べます。こうすることで  K 以外のどの数字を選んでも、2つの位置の間(両端を含む)にあるものは「 K 1個と、同じ数字の2個ペアたち」となり、同じ数字のペアはXORで打ち消し合うので必ずXORの値が  K になります。

あとは  K 同士のXORも  K にならないといけませんが…  M \ge 2 の場合は もう1つの  K を端に置くことで間にある値のXORが必ず  K になります。これは、

  •  a を非負整数として、 4a, 4a+1, 4a+2, 4a+3 のXORを取ると必ず0になる

という性質によるものです。この性質は以前のABCにも登場しましたね。

 M \ge 2 であれば  0, 1, ..., 2^{M}-1 は上記のような4つ組のグループに分けられるので、そのXORは0になります。今回  K K の間(両端を含む)にある値はこれらの値1つずつと  K 1個だけが余っているので、そのXORは  K になります。

ということで、 K \le 2^{M}-1 かつ  M \ge 2 のときは答えを求めることができました。あとは残りのケースを考慮します。

もし  K \ge 2^{M} である場合には、 K の最上位ビットは  2^{M} の位以上になり、 0, 1, ..., 2^{M}-1 の値をどうXORで組み合わせてもこのビットを作ることはできません。つまり、この場合は構成不可能です。

 M = 1 の場合は入出力例に示されている通りなので、これをそのまま埋め込んでしまえばよいです。 M = 0 も実は制約に含まれていますが、この場合は 0 0 しか作れないので  K=0 の場合だけ答えが存在します(考慮していなくても  M \ge 2 と同じ実装で正しく処理できることが多いでしょう)。

ACコード

Submission #5462845 - AtCoder Beginner Contest 126

Codeforces Round #561 D. Cute Sequences

Problem - D - Codeforces

問題概要

以下の問題を  q 個解け。

  • 正整数  a, b, m が与えられる。以下の条件を満たす整数列  \lbrace x_{i} \rbrace を1つ構成するか、そのような数列が存在しないことを判定せよ。
    • 初項が  a で末項が  b である。
    • 項数を  n として、全ての  2 \le i \le n について  r_{i} = x_{i} - \sum_{k=1}^{i-1}x_{k} とすると  1 \le r_{i} \le m が成立する。

制約

  •  1 \le q \le 10^{3}
  •  1 \le a \le b \le 10^{14}
  •  1 \le m \le 10^{14}

解法

数列の長さ  n を全探索することを考えましょう。 n = 1 のときに条件を満たすのは  a=b の時だけなので、その場合は別扱いすることにして  n \ge 2 の場合を考えます。

長さ  n をある値に固定して、末項が最小でどのくらいの値になるか考えます。すなわち全て  r_{i} = 1 としたときの末項を計算してみます。

  •  x_{1} = a
  •  x_{2} = x_{1} + 1 = a+1
  •  x_{3} = x_{1} + x_{2} + 1 = 2a+2
  • ...
  •  x_{n} = x_{1} + \cdots + x_{n-1} + 1 = 2^{n-2}(a+1)

実際に計算してみるとこのような値になります。もしこの値が既に  b よりも大きい場合は、これ以上の長さでは絶対に答えを構成できないことが分かります。

 2^{n-2}(a+1) \le b のときは、ここから各  r_{i} を増やすことで  b との差を埋めることを考えます。各  r_{i} を1増やしたときに、末項の値はどれだけ増えるでしょうか。これも実際に手計算すると分かって、

  •  i \lt n のとき、 r_{i} が1増えると末項は  2^{n-1-i} だけ増える。
  •  r_{n} が1増えると末項は1だけ増える。

というようになります。

最小値の時点で既に1持っているので、各  r_{i} について増やせるのは  m-1 までです。これらの値をうまく決めて、先ほどの係数を掛けた合計が増やすべき値  d = b - 2^{n-2}(a+1) に一致するようにすればよいです。これは係数が大きい方から決めていって、足りない分を増やせるだけ増やすようにすることで求めることができます。

この方針で決めていっても合計が増やすべき値  d に満たない場合は、その数列の長さで条件を満たすものは存在しないことになります。これを  2^{n-2}(a+1) \le b となるような  n 全てについて計算し、条件を満たすものが見つからなかったら答えは存在しないと判定することができます。

2以上の長さの候補はおよそ  \log_{2} \frac{b}{a+1} 個なので、クエリが最大  10^{3} 個あることを加味しても計算時間は問題ないです。

ACコード

Submission #54298174 - Codeforces

コード中で  L という変数でループを回していますが、 L = n-2 として扱っているので読む場合はご注意ください…

Educational Codeforces Round 65 E. Range Deleting

Problem - E - Codeforces

問題概要

長さ  n の数列  \lbrace a_{i} \rbrace と整数  x が与えられ、 1 \le a_{i} \le x である。

以下の条件を満たす整数の組  (l, r) の個数を求めよ。

  •  1 \le l \le r \le x である。
  • 数列  \lbrace a_{i} \rbrace から  l \le a_{i} \le r を満たす要素をすべて取り除くと、残った数列は広義単調増加になる。(空数列でも可)

制約

  •  1 \le n, x \le 10^{6}
  •  1 \le a_{i} \le x

解説

削除する値の範囲  \lbrack l, r \rbrack について、ある左端  l を固定したとき、条件を満たす  r には単調性があります。これは区間を伸ばせば伸ばすほど多くの要素が消え、残った数列が単調増加になりやすいからです。

二分探索かしゃくとり法が使えないか考えてみましょう。二分探索ができれば楽ですが、 x 個の左端を全探索した上で判定問題を解くのに  n 要素の数列を走査しているようでは間に合いません。しゃくとり法を用いて、かつ区間に値を出し入れする処理を何らかの方法で差分更新できれば間に合いそうです。

この差分更新は様々な方法で実現している人がいました。この記事では私が本番中に実装したやり方をまとめておきます。

ある要素  a_{i} に注目します。数列を左から右に並べたときに、もしこの要素より左にあって  a_{i} より大きい要素があると数列は単調増加になりません。そのため条件を満たすためには、インデックス  i に関して

  1.  a_{i} が削除される。
  2.  i より左にあって  a_{i} より大きい要素の最小値を  m_{i}、最大値を  M_{i} として、範囲  \lbrack m_{i}, M_{i} \rbrack が全て削除される。

の少なくとも一方が満たされる必要があります。ただし  i より左に  a_{i} より大きい要素が存在しないような  i については常に条件が満たされていると考えてよいです。

f:id:betrue12:20190516222708p:plain

逆に全ての  i についてこれらの条件の少なくとも一方が満たされるとき、数列は単調増加になります。

そこでまず、それぞれの  i について  m_{i}, M_{i} を求めます。これは数列を左から見ていきながらsetやセグメント木に値を追加していくことで合計  O(N \log N) で実現できます。

そしてしゃくとり法を以下のように処理していきます。

  • 区間の右端に値  v を加えるときには、
    •  a_{i} = v である  i について、条件1を「満たす」に変更する。
    •  M_{i} = v である  i について、もし  l \le m_{i} ならば条件2を「満たす」に変更する。
  • 区間の左端から値  v を取り除くときには、
    •  a_{i} = v である  i について、条件1を「満たさない」に変更する。
    •  m_{i} = v である  i について、もし  M_{i} \le r ならば条件2を「満たさない」に変更する。
  • 上記の変更に伴って、「今、条件がどちらも満たされていないインデックス  i の個数」を差分更新する。

このようにすれば、区間に値を出し入れして差分更新する処理は合計で  O(N+X) になります。合計で  O(N\log N+X) となり、制約が大きいのでギリギリですが一応間に合いました。

ACコード

Submission #54241812 - Codeforces

Codeforces Round #560 F2. Microtransactions (hard version)

Problem - F2 - Codeforces

問題概要

※microtransactionは、オンラインゲームなどでのアイテム課金を指す言葉だそうです。文中では「アイテム」と訳します。

イヴァンはゲームのアイテムを買おうとしている。アイテムは  n 種類あり、種類  i のアイテムは  k_{i} 個必要である。

イヴァンは毎日の朝に1円を稼ぎ、夜にアイテムを買う。アイテムは通常1個2円だが、「 d_{j} 日目には、種類  t_{j} のアイテムを1円で買える」というセール情報が合計で  m 個与えられる。

イヴァンは所持金が足りる限り1日にアイテムを好きなだけ買うことができる。イヴァンが全てのアイテムを必要数買い終わるまでの最小日数を求めよ。

制約

  •  1 \le n, m \le 2 \times 10^{5}
  •  0 \le k_{i} \le 2 \times 10^{5}
  •  1 \le \sum k_{i} \le 2 \times 10^{5}
  •  1 \le d_{j} \le 2 \times 10^{5}
  •  1 \le t_{j} \le n

解法

この問題は、アイテムを全て買い終わる日を決めてしまうととても考えやすくなります。「アイテムを  X 日までに買い終わることは可能か?」という判定問題を考えて二分探索します。

アイテムの値段は全て同じなので、セールで買うアイテムの合計個数を最大化することを目指せばよいです。そしてアイテムは各日に好きなだけ買うことが可能なので、セールでの買い物は出来るだけ先延ばししたほうが使えるお金が多いので有利です。

そのため最適な戦略は

  • 各アイテム種類ごとに、 X 日までの間で一番最後のセール日しか買わないようにする。各アイテムごとに最後のセール日をリストアップしておく。
  • 前からシミュレートする。基本はお金を貯めて、リストアップしたセール日が来たらそのアイテムを買えるだけ買う。
  • 最終日に、セールで買えなかった不足分をまとめ買いする。

となります。買い終わる日を決めることで一番最後のセール日がいつなのかが分かり、最適な戦略が決まります。

二分探索の初期条件について考えましょう。 S = \sum k_{i} とします。アイテムの合計必要個数×2のお金があればセールなしで全部買えるので  ok = 2S とできます。一方、全部セールで買ったとしても間に合わない条件を考えると  ng = S - 1 とできます(適当に  ng = 0 などでも問題ないです)。

二分探索のループが  O(\log S) 回実行され、それぞれの判定問題は実装によりますが  O(N+M) で可能なので、全体計算量は  O((N+M)\log S) となり間に合います。判定問題は各アイテムごとの最後のセール日を調べた後にソート等をするともう1つ  \log が付きますが、日数が少ないことを利用してバケットで管理すると線形時間になります。

ACコード

Submission #54115676 - Codeforces

少し前に二分探索の記事を書いたばかりだったので、タイムリーでした。

AGC033 B - LRUD Game

B - LRUD Game

解法

まず気付くべき点は、縦と横は独立に考えられることです。これは今回のゲームのルールが

  • 盤外に落ちる条件が「縦座標が  1 \le r \le H の範囲から外れること」または「横座標が  1 \le c \le W の範囲から外れること」であること
  • 縦座標と横座標が互いに影響し合わないこと
  • 高橋くんも青木くんもあるターンには決まった方向にしか動けず、「1ターンに縦に動くか横に動くか選べる」という状況がないこと

から、独立に考えてもよいことが分かります。

そのため、高橋くんが駒を縦方向に落とすことができるか・横方向に落とすことができるかをそれぞれ考えます。判定方法は同じなので、以降は横方向の場合だけを説明します。横方向だけを考える場合においては、文字が U D であるターンは「何もできないターン」だと見なして良いです。

ここでもしゲームの進行順と同じように前から考えると、高橋くん・青木くんともに「最適な戦略」を考えるのがとても難しいです。高橋くんは左右どっちに落としても勝てるので、高橋くんも青木くんも駒を左右どちら側に寄せたほうが得なのか分かりません。ターンごとにそれぞれが動ける向きが決まっているので、高橋くんは端に向かう/青木くんは真ん中に向かうような戦略も最適ではないです。全局面をシミュレートすればもちろん最適解は分かりますが、計算時間が足りません。

そこで使えるのが「逆から考える」テクニックです。逆から考えることの嬉しい点は、ゲーム中の全てのタイミングで、「今、駒がどこにあればどっちの勝ちなのか」がバッチリ決まる という点です。

このことを具体的に見ていきましょう。以下の入力例1を使います。

2 3 3
2 2
RRL
LUD

まず、最終局面については簡単です。ゲームのルールから、横座標を  c として  1 \le c \le W = 3 の範囲にあれば青木くんの勝ち、そうでなければ高橋くんの勝ちです。

f:id:betrue12:20190514221358p:plain

最終ターンである第3ターンの青木くんの行動には意味がないので、第3ターンの高橋くんの行動を考えましょう。高橋くんは自分のターンの行動によって、先ほどの範囲  1 \le c \le 3 から駒を出すことができれば勝ちです。第3ターンの高橋くんの文字は L なので、もし  c = 1 であれば左に動かして範囲から出すことができます。 c = 2, 3 のときは範囲から出すことができません。

つまり第3ターンの直前時点では、「横座標がこの範囲にあれば青木くんの勝ち」という範囲は  2 \le c \le 3 と変わります。

f:id:betrue12:20190514221428p:plain

次は第2ターンの青木くんの行動ですが、文字は U なので青木くんは横方向に駒を動かせません。範囲はそのままです。

次は第2ターンの高橋くん、文字は R です。つまり「もしこのターンの前に  c = 3 だったら、 2 \le c \le 3 の範囲から出せる」ので、このターン直前時点での青木くんが勝てる範囲は  2 \le c \le 2 です。

f:id:betrue12:20190514221502p:plain

次は第1ターンの青木くん、文字は L です。この場合、「もしこのターンの前に  c = 3 だったら、左に動かすことで  2 \le c \le 2 に入れることができる」ので、このターン直前時点での青木くんが勝てる範囲は  2 \le c \le 3 です。

f:id:betrue12:20190514221515p:plain

最後に第1ターンの高橋くん。これは先ほどと全く同じで、このターン直前時点(つまりゲーム開始時点)での青木くんが勝てる範囲は  2 \le c \le 2 となります。

f:id:betrue12:20190514221527p:plain

この入力例1において初期座標は  c = 2 だったので、このゲームは(横方向に関しては)青木くんの勝ちとなります。

…と、このように逆から考えることで各ターンにおける「横座標がこの範囲にあれば青木くんの勝ち」という範囲を求めていくことができます。

各プレイヤーの文字が L または R であるターンにおいて、その方向に応じて高橋くんはこれを1マス分縮めることが、青木くんはこれを(盤外を含まない範囲で)1マス分広げることができます。そして途中で存在できる範囲が1マスもなくなってしまったり、最後の(つまりゲーム最初の)範囲に初期座標が入っていなければ高橋くんの勝ちです。

図を見ても分かるように青木くんの勝てる範囲は必ず1つの区間になるので、その最小値と最大値を持っておくことで範囲の伸び縮みを処理できます。縦横それぞれこのような判定をして、どちらかで高橋くんが勝てば駒は落ちるので結果は高橋くんの勝ち、両方で青木くんが勝てば駒は縦にも横にも落ちないので結果は青木くんの勝ちです。

実装コード

Submission #5259153 - AtCoder Grand Contest 033

実装テクですが、縦と横で別々にコードを書いて、ほとんど処理は同じなのに  H, W と初期座標と見る文字は違ってて…みたいな実装はあまり得策ではないです。コピペして1箇所変数を変え忘れた、などの悲劇が起こります。

できればリンク先の実装コードのように、共通化して2度同じコードを回るような実装にするのがオススメです。

diverta 2019 Programming Contest D - DivRem Number

D - DivRem Number

解法

この問題は「割り算して切り捨て」と「余り」の関連性に気付くととても考えやすくなります。実際、割り算して切り捨てたときに捨てられる部分は割った余りそのものです。

具体的に数式で表すと、 N m で割った余りを  r とすると  \lfloor\frac{N}{m}\rfloor = \frac{N-r}{m} が成立します。つまり問題の条件式は  \frac{N-r}{m} = r となり、これは整理して  m = \frac{N}{r} - 1 となります。ただし、 N m で割った余りが  r であることから  r \lt m も成立している必要があります。

 m は整数で、右辺が整数になるためには  r N の約数である必要があります。そのため  N の約数を列挙して、それを  r としたときの  m = \frac{N}{r} - 1 について「正かどうか」「本当に元の条件式を満たすか」を調べればよいです。

「本当に元の条件式を満たすか」を調べるには実際に計算してみても良いですし、  m = \frac{N}{r} - 1 かつ  r \lt m であれば必要十分になるのでそれをチェックしても良いです。

約数列挙は計算量  O(\sqrt{N}) で行えるため、 N \le 10^{12} でも間に合います。

ACコード

Submission #5351859 - diverta 2019 Programming Contest

このコードでは条件を満たすかの確認に  r \lt m を使っていますが、実際に計算してみるほうが安心できるのでオススメです。