ARMERIA

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

KEYENCE Programming Contest 2019 参加記録&解説

まあまあの速度で4完。Eは解きたかった…

f:id:betrue12:20190114020636p:plain

本番後に通したEも含めて5問解説します。→Fも書き足しました。

A - Beginning

解法

ソートして 1479 になるかどうかチェックするのが一番楽です。

ACコード

B - KEYENCE String

B - KEYENCE String

解法

文字列  S が100文字以下なので、取り除く範囲を全探索すればよいです。

部分文字列のとり方は各言語によって違いますが、ちゃんと漏れなく列挙できているかどうか不安になりますね…不安な場合は試しに abc などの短い文字列を入力にして、列挙した文字列を全部デバッグ出力して全部あるか確認してみるのが良いと思います。

ACコード

C - Exam and Wizard

C - Exam and Wizard

解法

準備度が余っているテストから、準備度が足りないテストに値を移動させます。このとき、そもそも合計値が足りていない場合は条件を満たすことが不可能です。

準備度を変更するテストの個数をなるべく少なくしたいですが、準備度が足りないテストは明らかに変更する必要があるので、準備度の余っているテストの変更数をなるべく少なくしたいです。これは余っている値が大きいものから順番に使っていくと最適になります。

まとめると、準備度が足りないテストの個数と不足値合計を計算しておきます。次に準備度が余っているテストの余剰値を大きい順にソートして、不足値を全部補えるまで大きい方から使っていきます。準備度が足りないテストの個数と、準備度が余っているテストを使った個数の合計が答えです。

ACコード

D - Double Landscape

解法

各行と各列の最大値が指定されているので、数を大きいほうから追加していくと上手くいきます。小さい方から追加していくと「最大値のために1つマスを空けておかないといけない」など条件が難しくなりますが、大きい方から追加していくと最大値を追加した後はその行/列に自由に数を追加していけるからです。

ということで大きい方から追加していきますが、例を使ってどのようになるかを見てみます。

f:id:betrue12:20190114030452p:plain

例にあるように、

  1. 行最大値と列最大値の両方に登場するときは、その交点に置く。
  2. 行最大値だけに登場するときは、既に最大値が置かれている行に置く。逆も同様。
  3. 行と列どちらの最大値にも登場しないときは、行にも列にも既に最大値が置かれているようなマスに置く。

という操作をすることになります。この操作を  NM, NM-1, ..., 1 と最後まで行って、各数字の置ける候補の個数を全部掛け算したものが答えになります。

1.の場合、もちろん候補の数は1つです。

2.の行最大値だけに登場するときは、既に列最大値が登場している列数がそのまま候補の数になります。

3.については、「行にも列にも既に最大値が置かれているような空きマスの個数」が必要です。これは (最大値が置かれた行の数)×(最大値が置かれた列の数)-(既に置いた数字の個数)で求めることができます。

この操作の途中で「置き場所がなくなった」、つまり置く候補の数が0になった場合は、答えは0になります。0に何を掛けても0なのでそのまま処理を続けてもよいですし、すぐに0を出力して終了しても良いです。状態がおかしくなってREになるかもしれないという不安がよぎるので、即終了のほうが安心かもしれません。

ACコード

C++Submission #4011139 - KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019

実装においては行最大値と列最大値をそれぞれソートしておくと楽です。これは盤面の行と行、または列と列を入れ替えるという操作に相当し、今回はこの操作によって答えが変わることはないのでソートして大丈夫です。

E - Connecting Cities

E - Connecting Cities

解法

コンテスト終了後に公式解説を見て通したので、公式解説ベースの解法で解説します。

作りたいのは最小全域木です。ただし辺の張り方が  O(N^{2}) 通りあるので、辺の選び方を工夫する必要があります。

辺のコストは都市間の距離  |i-j| と都市の規模  A_{i} に依存していて、「近いから」「規模が小さいから」というだけでは最適な辺を選ぶことはできません。ただし、「近いし規模も小さい」という辺は、「遠いし規模も大きい」という辺よりはコストが小さいはずです。

というわけで、そのような状況を考えてみます。

f:id:betrue12:20190114122008p:plain

図の縦軸が規模  A_{i} の値で、横軸が位置を表します。このとき辺  a, c を比べると、 c のほうが「近いし規模も小さい」という辺になっています。

ここでさらに図中の  b のような辺を考えると、この閉路を作る3辺のうちコストが最大の辺は最小全域木において使うことはありません(クラスカル法のアルゴリズムより)。さきほど見た  a \gt c という関係から、 a, b のうちコストが大きいほうが3辺の中でもコスト最大になり、その辺は考える必要がありません。

この考察は規模の等しい都市があったとしても成立します。また辺  a, b のコストがぴったり同じ場合は、どちらを使うと考えてもよいです。

この事実を一般化するために、3点の中で一番  A_{i} が大きい頂点、図中の頂点  i に注目します。そうするとさきほどの事実は

  • ある頂点  i から見て左右のどちらかを見たときに、そちら側にある「規模が  A_{i} 以下である頂点」2つと結ぶ辺のうち、コストが小さいもの1本以外は不要である

と言い換えられ、さらに一般化して

  • ある頂点  i から見て左右のどちらかを見たときに、そちら側にある「規模が  A_{i} 以下である頂点」と結ぶ辺すべてのうち、最もコストが小さいもの1本以外は不要である

と言うことができます。このように考えると、不要でない辺は1つの頂点につき高々2本しかないことが分かります。(これはあくまで規模が小さい都市に「繋ぎに行く」辺の本数であり、規模の自分より規模の大きい都市から「繋がれる」ことである頂点の最終的な次数が2を超えることはあります)

不要でない辺が高々頂点数の2倍であれば、クラスカル法などのアルゴリズムで十分間に合います。

f:id:betrue12:20190114122027p:plain

次は「頂点  i から見て片側にある、規模が  A_{i} 以下である頂点のうち、コストが最も小さいものはどれか?」という問題を解く必要があります。区間内最小値ということでセグメント木が使えそうですが、距離の条件があるのでコスト値そのものをセグメント木に入れることはできません。

ただコストの特徴として、例えばある頂点から右側を見る場合、1つ座標が右にずれるごとにコストの距離要素は  +D だけ変動します。2つ座標がずれると  +2D です。この距離が遠くなることによるコスト差を、最初からセグメント木に含めてしまうという手があります。つまり「右側を見る」用のセグメント木には、

  • 頂点1の要素としては  A_{1} + D
  • 頂点2の要素としては  A_{2} + 2D
  • ...
  • 頂点Nの要素としては  A_{N} + ND

を格納します。こうすれば距離によるコスト差を含んだ上での最小値がどれなのか判断できます。ただこれは「大小関係の比較」をするには正しいですが、頂点  i の位置が考慮されておらず実際のコストそのものではないので、実際のコストは求め直すか頂点  i のぶんを補正しましょう。

「左側を見る」用のセグメント木は別途作って、傾斜を逆にします。またこの問題の場合「最小コストはいくらか」だけでなく「最小コストを実現する頂点はどれか」という情報も必要なので、 (コスト, 頂点番号) の形のペアを格納できるセグメント木を使うとよいです。

規模が自分以下の頂点だけを繋ぎに行く対象にしたいので、「頂点を規模が小さい順にセグメント木に追加しながら、その時点で追加されている頂点の中から繋ぎ先を選ぶ」という処理の流れになります。

このようにすれば不要でない辺の選定も効率的に行うことができるので、最後にクラスカル法で最小全域木のコストを求めればOKです。

ACコード

Submission #4010825 - KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019

F - Paper Cutting

F - Paper Cutting

解法

最初の発想

操作列をそのまま列挙するのはもちろん無理です。少し考えると、 k 回目の操作後の破片の個数はその時点での縦の切断数と横の切断数から求めることができて、(破片の数)×(場合の数)みたいなのをどんどん足していけば答え自体は求まります。ただ計算量がかかりすぎてしまいます。

ここで発想を変え、「破片と1対1に対応する何か」を数え上げることができないか考えてみます。今回の場合、「破片の四隅のどこか1つ(例えば、左上隅)」を数えるように考えてみると上手くいきます。

つまり、「  k 回目の切断後に、紙の座標  (i, j) が、破片の左上隅になっている」という条件を満たす場合の数を数えます。これを  i, j, k 全てについて合計してあげれば求めたい答えが求まるはずです。

一見変数が多くてやっぱり計算量が多くなりそうですが、この考え方にはとても嬉しい性質があり、それは「座標  (i, j) が破片の左上隅になるような条件は、高々4種類だけに分類できる」ということです。具体例を見てみます。

f:id:betrue12:20190115002812p:plain

このように、左上隅のマス、上辺のマス(左上隅以外)、左辺のマス(左上隅以外)、それ以外のマスで分類できます。

これらの条件は「常に左上隅になる」「特定の1直線が切れていれば左上隅になる」「特定の2直線が切れていれば左上隅になる」の3種類に分けられて、上辺・左辺の性質もまとめることができます。それぞれのマスの個数も計算することができるので、あとは切断ステップ  k ごとに「  k 回目の切断後に、そのマスが左上隅になる条件が満たされている」ような場合の数を求めればよいです。

左上隅

これは簡単です。全部の場合の数を数えればよいです。

 H+W 個の直線を順序を付けて  K 個並べるので、全部の場合の数は  _{H+W}P_{K} になります。切断回数は全部で  K 回、マス数は1個なので、これらを全部掛け合わせて

 S_{1} = K \times (_{H+W}P_{k})

が左上隅についての合計破片数になります。

上辺/左辺

これらのマスが破片の左上隅になる条件は、ある特定の1直線が切断されていることでした。この直線を  a と表記します。

 k 回目の切断後に直線  a が切断されているような場合の数を考えます。このとき直線  a の入る場所は1回目から  k 回目までの  k 通りです。そして残りの  K-1 回分の切断は何でも良いので、残った直線  H+W-1 本から自由に並べます。このような場合の数の総数は

 k \times _{H+W-1}P_{K-1}

になります。これは  k に依存しているので1回目から  k 回目までの和を取って、さらに上辺と左辺のマス数(左上隅以外)のマス数  H+W を掛けて、

 S_{2} = (\sum_{k=1}^{K}k) \times (_{H+W-1}P_{K-1}) \times (H+W) = \frac{1}{2}K(K+1) \times (_{H+W}P_{k})

となります。 \sum_{k=1}^{K} = \frac{1}{2}K(K+1) の公式を使っています。

※ちなみに最後の式変形で  (_{H+W}P_{k}) と全事象数が出ていていますが、確率の考え方を用いると  k 回目の切断終了後にある直線  a が切れている確率は  \frac{k}{H+W} と求めることができて、(全事象数)×(確率)の計算をすることでも全く同じ式を導くことができます。

それ以外

それ以外の辺が破片の左隅になる条件は、ある特定の2直線が切断されていることでした。この直線を  a, b と表記します。

 k 回目の切断後に直線  a, b がともに切断されているような場合の数を考えます。このとき、まず直線  a の入る場所は先ほどと同じく  k 通り。そして直線  b の入る場所は、  a が入ったぶん空きが1つ少なくなるので  k-1 通りです。残りの  K-2 回分の切断は何でも良いので、残った直線  H+W-2 本から自由に並べます。このような場合の数の総数は

 k(k-1) \times _{H+W-2}P_{K-2}

になります。やはり  k で和を取ってマス数の合計  HW を掛けると、

 S_{3} = (\sum_{k=1}^{K} k(k-1)) \times (_{H+W-2}P_{K-2}) \times (HW) = \frac{1}{3}K(K-1)(K+1) \times (_{H+W-2}P_{K-2}) \times (HW)

となります。前2つと違ってあまりキレイな式にはなりません。 \sum の計算は先ほどの公式と  \sum_{k=1}^{K}k^{2} = \frac{1}{6}K(K+1)(2K+1) の公式で展開して変形するとこうなりますが、 k(k-1) の和を  O(K) で素直に求めても良いと思います。

最後に答えを計算

これらを全て計算すれば  S_{1} + S_{2} + S_{3} のmodを取ったものが答えになります。

必要な道具は高々  H+W までの階乗なので計算量は  O(H+W) で、 1 \le H, W \le 10^{7} といつもより大きめの制約ですが十分間に合います。

ACコード

Submission #4014003 - KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019

コードは数学をして求めた計算式をただ並べているだけという感じですが…  K^{3} が64bitでもオーバーフローするのでそこだけ注意です。

AISing Programming Contest 2019 参加記録&解説

AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019 - AtCoder

全完!

2000未満ratedコンテストだったのでパフォーマンスは付かず、ちょっと残念。

f:id:betrue12:20190112235728p:plain

A - Bulletin Board

A - Bulletin Board

解法

縦の位置が  N-H+1 通り、横の位置が  N-W+1 通りあるので、これらを掛け算したものが答えです。

ACコード

B - Contests

B - Contests

解法

「1問目になるもの」「2問目になるもの」「3問目になるもの」がそれぞれ排他、つまり点数の範囲が被っていないことが重要です。それぞれの問題数を数えて、一番小さいものを出力すればよいです。

ACコード

C - Alternating Path

C - Alternating Path

解法

黒→白→黒→白…と移動することは、「今いるマスと違う色のマスに移動する」ことと考えることができます。そう考えると、違う色で隣り合っているマスは「相互に行き来できるマス」ということになります。

この相互に行き来できるマス同士を繋いでいくと、グリッドの中で「この範囲内はどのマスからどのマスへも相互に行き来できる」という領域ができます。そうするとこの領域内の黒のマス数×白のマス数だけ、問題の条件を満たすペアを作ることができます。これを領域ごとに数えて全部足すと答えになります。

f:id:betrue12:20190113152616p:plain

あとは「領域の調べ方、数え方」ですが、これは幅優先探索/深さ優先探索などが楽だと思います。あるマスから始めて、違う色で隣り合っている未訪問のマスを探索していけばよいです。

ACコード

D - Nearest Card Game

D - Nearest Card Game

解法

ここから難易度が上がるので、解説もしっかりしていきたいと思います…

二人が取るカードの全体像を掴む

たくさんの  x の値について答えを出さなくてはいけませんが、まずは一旦それを忘れて、ある1つの  x について考えます。

問題の操作から、高橋くんと青木くんがどのようにカードを取っていくか考えてみます。

f:id:betrue12:20190113011859p:plain

全体の形としてはこのようになります。まず高橋くんは大きいほうから、青木くんは  x の周りからカードを取っていきます。こうするといずれ高橋くんが青木くんの取っていた領域に当たってしまうので(図中の  y のあたり)、その後は2人で交互に残った下の方のカードを大きい方から取っていきます。

もちろん、このうちどこかの領域は要素数がゼロかもしれません。例えば  x がものすごく大きいところにある場合、2人は単に一番上から交互にカードを取っていくだけになります。

「境界」を探す

これらのゾーンの境界が知りたくなります。境界が分かってしまえば、累積和を用いて高橋くんのカードの合計が分かりそうです。

 x より上にあるカードについて、そのカードを高橋くんと青木くんどちらが取るのか?を考えます。これを知るには、高橋くんと青木くんそれぞれについて「その人がそのカードを取るとしたら、何枚目に取るか?」を考えればよいです。

取る順番が早いほうがそのカードを取ります。同順の場合は先攻の高橋くんが取ります。

f:id:betrue12:20190113013314p:plain

高橋くんのほうは簡単で、一番上から取っていくので「そのカード以上にあるカードの枚数」がそのまま使えます。

青木くんのほうは少しだけ厄介ですが、 x に近いところから取る、距離が同じ場合は小さい方を先に取る、という条件から、カード  y を取る時点で青木くんは  x - A_{y} 以上  x+A_{y} 以下の範囲にあるカードを全て取っているはずです。なのでその範囲にあるカードの枚数を数えればよくて、ある座標範囲内にあるカードの枚数は二分探索などで求めることができます。

こうやって  x より上側のカードについて「どちらが取るか」を判定できるので、これが逆転するところがさきほど示したゾーンの境界になります。

大量クエリの高速処理を考える

これで答えを求めるための道筋は見えました。あとは計算量です。

答えを求めなければいけない  x がたくさんあるので、結局は「 x が与えられたときに高速にゾーンの境界を求められるか?」という話になります。これを解決する方法は2つあります。

  1.  x の値が数直線の右側に移動すると、ゾーンの境界も右側に移動していくこと(単調性)を利用する。与えられた  x をソートし、しゃくとり法で境界を求めていく。
  2. さきほどの「どちらが取るか」自体に単調性があることを利用し、これを二分探索する。

これはどちらでも良いです。計算量オーダーとして優位なのはしゃくとり法ですが、各クエリを独立に処理できたほうが分かりやすいので計算時間に余裕があれば二分探索でも良いでしょう。

境界が分かった後は、各ゾーンの累積和で答えを求めます。交互に取るゾーンがあるところも考慮し、1つ飛ばしの累積和(添字の偶奇ごとに累積和を取ったもの)も求めておくと良いです。

ACコード

E - Attack to a Tree

E - Attack to a Tree

解法

木DPの着想を得る

ある適当な点を根とする根付き木とみなし、葉から順番に値を計算していく木DPを考えてみます。

DPテーブルが持つ情報として必要そうなものは、「その頂点以下で何本の辺を切ったか」「その頂点を含む連結成分の、現時点での電力合計」です。このうち電力合計はとても大きい値になり得ますが、切った辺の本数は最大でもその頂点以下にある辺の本数なので比較的少ないです。そこで

  •  dp\lbrack i \rbrack\lbrack j \rbrack = 頂点  i 以下の部分木を考えたときに、辺を既に  j 本切っているときの、頂点  i を含む連結成分の電力合計の最小値。ただし、辺を切ったことで既に確定している連結成分は問題の条件を満たしていなければならない。

と定義します。電力を足りなくさせることが目的、つまり電力合計をなるべく小さくしたいので最小値を取っています。

ただしこのままでは情報が不足しています。各連結成分が満たすべき条件は、「連結成分にコンピュータが存在しない」「連結成分内の電力合計が負」のどちらかなので、電力合計だけでなくコンピュータが存在するかどうかの情報が必要になってきます。そのため、

  •  dp\lbrack i \rbrack\lbrack j \rbrack\lbrack k \rbrack = 頂点  i 以下の部分木を考えたときに、辺を既に  j 本切っていて、部分木内にコンピュータが存在する( k=1)/しない( k=0ときの、頂点  i を含む連結成分の電力合計の最小値。ただし、辺を切ることで既に確定している連結成分は問題の条件を満たしていなければならない。

と各頂点が持つ値を定義します。以下はある状態において、各添字がどのようになるかを示す一例です。

f:id:betrue12:20190113160918p:plain

これなら、後に示すように遷移を構成することができます。

遷移を考える

子の情報から親の情報へ、どのようにDPの遷移を作ればよいか考えてみます。

イメージとしては、最初は親を要素数1の部分木として考え、そこに子の部分木を1つずつマージしていきます。親と子それぞれについて、さきほどの  j, k についてループを回します。

このとき、子からの辺を繋ぐか切るかという2通りが考えられます。

f:id:betrue12:20190113023514p:plain

添字が多いので式がややこしくなりがちですが、

  • 辺を繋ぐ場合、今までに切った辺の数・電力合計は加算し、コンピュータがあるかどうかはOR演算する。
  • 辺を繋がない場合、まずは子の部分木が条件を満たしているかどうかをチェック! 満たしている場合は、切った辺の数は合計に1を足したものになり、それ以外の情報は親の情報がそのまま残る。

という風に遷移先を求めることができます。この遷移先に対して「今の値より値が小さくなるなら更新」と操作することを繰り返すと遷移ができます。

計算量について、通称「二乗の木DP」

さきほどのDP、子をマージするたびに親子それぞれの切った辺の数についてループを回すので計算量がひどくなりそうな気がします。具体的には全頂点について辺の数の2乗ループを回しているので、全体  O(N^{3}) になりそうです。

ですが、「その時点で持っている部分木のサイズまでしかループを回さない」という実装をすることで、全体計算量を  O(N^{2}) とすることができます。これが通称「二乗の木DP」 と呼ばれるものです。部分木の辺の数は頂点の数-1なので、切った辺の数でループする場合はこのテクニックが使えます。

ACコード(&実装について)

私の実装について少し補足です。

DPテーブルに持つ値についてですが、 INF という値を使っています。先ほど書いたようにこのテーブルの中には添字で定義された状態における電力合計の最小値が入っていますが、ときには「そのような添字に対応する状態が存在できない」ということがあります。一番単純な例では、部分木内にコンピュータが1つもない場合は  dp\lbrack i \rbrack\lbrack j \rbrack\lbrack 1 \rbrack に対応する状態はありません。このようなときには値に  INF を入れています。

この問題ではDPを回した後、最後に「辺の切り方が合計  j 本であるような、問題文の条件を満たす分け方が存在するか」を根について調べて、一番小さい切断本数を答えることになります。このときに「 INF の場合はそのような状態が存在しない」という決めごとをしておくと判定を正しく行うことができます。コードでは以下の部分です。

for(int n=0; n<N; n++){
    if(dp[0][n][0] < INF) ans = min(ans, n);
    if(dp[0][n][1] < 0) ans = min(ans, n);
}

Hello 2019 (Codeforces) 参加記録&解説(A~D, F)

Dashboard - Hello 2019 - Codeforces

2019年最初のコンテストはABCDFの5完で111位!幸先いいですね。

f:id:betrue12:20190105143131p:plain

A. Gennady and a Card Game

Problem - A - Codeforces

問題概要

2文字の文字列でトランプのカードを表す。1文字目がランク、2文字目がスートに対応する。

場にあるカードが与えられ、さらに5枚の手札が与えられる。場にあるカードに対して、ランクまたはスートの少なくとも一方が一致するカードをプレイすることができる。

手札の中にプレイできるカードがあるかどうか判定せよ。

制約

省略

解法

手札を順に場のカードと比較し、1文字目または2文字目が一致するものがあるかを判定すればよいです。

ACコード

B. Petr and a Combination Lock

Problem - B - Codeforces

問題概要

 n 個の角度  a_{1}, ..., a_{n} が度数法で与えられる。それぞれの角度に対して左回り/右回りを自由に選んで、1周あたり360度のダイヤルを回す。操作が全て終わった時にダイヤルが最初と同じ位置にあるような回し方が可能であるかどうか判定せよ。

制約

  •  1 \le n \le 15
  •  1 \le a_{i} \le 180

解法

左回りをプラス、右回りをマイナスとして角度を符号付きで全て合計したときに、その値が360度の倍数になっていればよいです。

制約より  O(2^{n}) が十分間に合うので、回す方向を全探索してそれぞれ計算すればよいです。

ACコード

私の実装はbit全探索です。hackを狙ってコードを読んでいたら、再帰関数での実装も多く見られました。

C. Yuhao and a Parenthesis

Problem - C - Codeforces

問題概要

括弧だけで構成された文字列が  n 個与えられる。文字列2つをペアにして正しい括弧列をできるだけ多く作りたい。1つの文字列が2つ以上のペアに属することはできない。

作ることができるペアの最大数を求めよ。

制約

  •  1 \le n \le 10^{5}
  • 全ての文字数の合計は  5 \times 10^{5} を超えない

解法

正しい括弧列の条件は、( を+1、) を-1とする累積和を取ったときに、

  • 文字列全体の合計がちょうど0である。
  • 頭から見て、どの時点でも累積和が0以上である。

を満たすことです。

このことを考えると、2つの文字列をペアにして正しい括弧列とするためには、ある非負整数  k に対して

  • 前半の文字列
    • 合計が  k である。
    • 頭から見て、どの時点でも累積和が0以上である。
  • 後半の文字列
    • 合計が  -k である。
    • 頭から見て、どの時点でも累積和が  -k 以上である。

をそれぞれ満たす必要があります。

あとはそれぞれの文字列に対して累積和の最小値と合計を計算して、「合計が  x で、最小値の条件を満たすものの個数」を整数  x ごとに集計します。その値を  mp\lbrack x \rbrack とすると、正整数  k \gt 0 について正しい括弧列は  \min(mp\lbrack k \rbrack, mp\lbrack -k \rbrack) 個作れます。合計0の文字列は合計0の文字列とペアになるので、 \lfloor\frac{mp\lbrack 0 \rbrack}{2}\rfloor 個作れます。これらを全て加算すれば答えが求められます。

ACコード

D. Makoto and a Blackboard

Problem - D - Codeforces

問題概要

整数  v の初期値を  n とする。整数  v に対して、以下の操作を  k 回行う。

  • その時点での  v の約数の中からランダムに1つ選ぶ。どの約数が選ばれる確率も等しいものとする。 v をその約数で置き換える。

操作が終わった後の  v の値の期待値を求めよ。答えは有理数となるため、その値を既約分数  \frac{P}{Q} としたときの  PQ^{-1} \mod 10^{9}+7 の値を出力せよ。

制約

  •  1 \le n \le 10^{15}
  •  1 \le k \le 10^{4}

解法

「約数を等確率で1つ選ぶ」という操作をしたときに、 v のそれぞれの素因数の個数がどうなるか考えます。 v にある素因数  p m 個含まれているとすると、操作後の素因数  p の個数は  0, 1, ..., m 個の中から等確率に1つ選ばれると考えることができます。そしてこの事象は素因数ごとに独立であるとみなすことができます。

そのため、まず  n素因数分解してしまい、素因数ごとに考えます。ある素因数  p についてだけ注目すると、「 i 回操作後に素因数  p j 個含まれている確率」を  dp_{p}\lbrack i \rbrack\lbrack j \rbrack とするようなDPを考えることができます。

遷移は、 dp_{p}\lbrack i \rbrack\lbrack j \rbrack (j+1)^{-1} を掛けたものを  dp_{p}\lbrack i+1 \rbrack\lbrack j_{2} \rbrack (j_{2} = 0, ..., m) に加算することで計算できます。「  k 回の操作後に素因数  p j 個含まれている確率」、すなわち  dp_{p}\lbrack k \rbrack\lbrack j \rbrack を以降  P\lbrack p, j\rbrack と表記します。

これを全ての素因数について計算すると、全ての  n の約数について  v が最後にその数になっている確率を計算できます。ちょっと数式がごちゃごちゃするので、仮に  n の相異なる素因数が  p_{1}, p_{2} の2種類だとして、それぞれの個数を  m_{1}, m_{2} とします。

このとき  n の約数は  p_{1}^{j_{1}}p_{2}^{j_{2}} と表現できて、最後にその数が残る確率は  P\lbrack p_{1}, j_{1}\rbrack P\lbrack p_{2}, j_{2}\rbrack となります。求めたいのは期待値なので、 p_{1}^{j_{1}}p_{2}^{j_{2}} P\lbrack p_{1}, j_{1}\rbrack P\lbrack p_{2}, j_{2}\rbrack を全て合計すればよいです。

これらを約数ごとに全て計算してもよいですが、さらに簡単にする方法があります。求めたい値は  p_{1}^{j_{1}}p_{2}^{j_{2}} P\lbrack p_{1}, j_{1}\rbrack P\lbrack p_{2}, j_{2}\rbrack を全ての  j_{1} = 0, ..., m_{1} j_{2} = 0, ..., m_{2} の組み合わせについて合計したものですが、これを分配法則を使ってまとめると

 (p_{1}^{0}P\lbrack p_{1}, 0\rbrack + p_{1}^{1}P\lbrack p_{1}, 1\rbrack + \cdots + p_{1}^{m_{1}}P\lbrack p_{1}, m_{1}\rbrack) \times (p_{2}^{0}P\lbrack p_{2}, 0\rbrack + p_{2}^{1}P\lbrack p_{2}, 1\rbrack + \cdots + p_{2}^{m_{2}}P\lbrack p_{2}, m_{2}\rbrack)

という形になり、  p_{1} p_{2} を完全に分離できます。そのためそれぞれで値を求めておいて、最後に掛け算する方法でも期待値を求めることができます。

ここまでの話は素因数の種類数が2個でない場合でも成り立ちます。それぞれの素因数ごとに値を求めて全部掛け算すればよいです。

ACコード

分配法則使用コードのほうが圧倒的にシンプルなのでオススメです。

F. Alex and a TV Show

Problem - F - Codeforces

問題概要

 1, ..., n までの番号が付けられた多重集合がある。始めはどの集合も空である。

以下の4種類のクエリを  q 個処理せよ。

  1. 1 x v 番号  x の集合を  v 1つだけの集合に置き換える。
  2. 2 x y z 番号  x の集合を、番号  y, z の集合の和集合に置き換える。
  3. 3 x y z 番号  x の集合を、番号  y, z の集合の「直積集合」に置き換える。ただしここでは要素同士の組の代わりに、それらの要素の最大公約数を直積集合の要素とする。
  4. 4 x v 番号  x に含まれる要素  v の個数の偶奇を出力する。

制約

  •  1 \le n \le 10^{5}
  •  1 \le q \le 10^{6}
  • クエリ1, 4について、 1 \le v \le 7000

解法

それぞれの集合の状態として、単純に各値の個数や偶奇を持っていてはクエリの処理が間に合いません。特に最大公約数を求める処理が厄介なので、これを処理しやすいような状態の持ち方を考える必要があります。

状態  state\lbrack x \rbrack\lbrack v \rbrack を、「集合  x に含まれる要素のうち、 v を約数に持つ要素の個数の偶奇」とするような状態を持ちます。このときクエリ2は  v ごとに要素数を足せば良いので、偶奇をビットで管理している場合はXORで計算できます。

またクエリ3の結果  v を約数に持つ要素の個数は、集合  y, z それぞれで  v を約数に持つ要素の個数の積になります。そのためビットで管理している場合はANDで計算できます。

クエリ1は単純に  v の約数全てのビットを立てたものに置き換えれば良いので、これでクエリ1, 2, 3の処理が効率的にできることが分かりました。あとは肝心のクエリ4です。

このクエリを処理するためには、「 k を約数に持つ要素の個数の偶奇 (k=1, ..., 7000)」から「 v の個数の偶奇」を求める必要があります。これは包除原理を用いて求めることができて、結論を書くと

  •  v の倍数であり、 k = \alpha v と表現できるような  k について、
    •  \alpha が同じ素因数を2つ以上含むなら(つまり、1より大きい平方数を約数に持つなら)無視
    • そうでない場合、
      •  \alpha に含まれる素因数が偶数個なら、+1倍
      •  \alpha に含まれる素因数が奇数個なら、-1倍

したものをすべて足すと求めることができます。ただし今回は偶奇を表すビットなので、+1倍と-1倍を区別する必要はありません。

この証明はちょっと面倒なので書きませんが…AtCoder「LCM Rush」の解説、またその問題などを扱っているtsutajさんの包除原理まとめPDFなどが参考になると思います。

これでクエリ4の解を求めることができます…が、計算量を確認すると  O(7000q) となり単純計算で70億。全てのクエリをbitsetを用いて高速に処理できるよう前計算などをしておくことで、何とか間に合います。キツいですね。

ACコード

AGC030 B - Tree Burning

B - Tree Burning

今回は私自身がAB2完で実質的にこの1問しか解説を書けないのと、この1問だけでかなり説明が長くなりそうなので、単独記事にします。

Twitter見ていると微妙に色々違う解法があるようで…?私が本番で考察した内容をベースに書きます。他の人が書いていることとズレがあるかもしれないので、そこはご注意ください。

はじめに

以降の説明で使う方向を定義しておきます。高橋くんの家を円の上側に置き、問題文の座標と同じ反時計回りの向きを「左」、その逆向きを「右」とします。

また説明を簡単にするため、与えられる木の座標値  X_{i} とは別に、座標の測り方を逆にして、逆向きに回った時に  j 番目にある木の座標値  Y_{j} を定義しておきます。これらは同じ木をどちら側から訪れるかによって2通りの座標値を付けているだけであることに注意してください。

具体的には  Y_{N+1-i} = L - X_{i} で計算できます。 X_{i} Y_{j} も木の位置を1-indexedで扱い、  X_{0} = Y_{0} = 0 としておきます。

f:id:betrue12:20181230210016p:plain

部分点解法

まず部分点ですが、DPをします。「家から左に  i 本、右に  j 本の木を訪問済みで、最後に訪れたのが左側の木なら  k=0 、右側の木なら  k=1 であるときの最大移動距離」を  dp \lbrack i \rbrack\lbrack j \rbrack\lbrack k \rbrack とします。

このようにDPの状態を定義すると、左右合計で  N 本の木を訪れた時点で終わりなので、  dp\lbrack i \rbrack\lbrack N-i \rbrack\lbrack k \rbrack i=0, ..., N および  k = 0, 1 の範囲で全て求めたもののの最大値が答えになります。家の座標を  X_{0} = Y_{0} = 0 としているので、初期条件は  dp\lbrack 0 \rbrack\lbrack 0 \rbrack\lbrack k \rbrack = 0 です。

遷移を考えます。 dp\lbrack i \rbrack\lbrack j \rbrack\lbrack 0 \rbrack は左に  i 本、右に  j 本の木を訪問済みで、最後に左側  X_{i} の木を訪れている状態です。ここからは2通りの移動ができて、

  • さらに左に進み、 X_{i+1} の木を訪れる。加算される移動距離は  X_{i+1} - X_{i} で、 dp\lbrack i+1 \rbrack\lbrack j \rbrack\lbrack 0 \rbrack に遷移する。
  • 向きを変えて右に進み、 Y_{j+1} の木を訪れる。加算される移動距離は  X_{i} + Y_{j+1} で、 dp\lbrack i \rbrack\lbrack j+1 \rbrack\lbrack 1 \rbrack に遷移する。

という遷移になります。

f:id:betrue12:20181230211600p:plain

 dp\lbrack i \rbrack\lbrack j \rbrack\lbrack 1 \rbrack からの遷移も同様に考えることができます。このDPを回すと  O(N^{2}) で計算が終わり、部分点を取ることができます。

部分点獲得コード

DPの実装における違いとして、いわゆる「貰うDP/配るDP」というものがあります。本番中の実装は「貰うDP」でしたが、「配るDP」のほうが文章化しやすかったので今回の説明は「配るDP」で書いています。この問題はどちらで解いても大差ないです。

あと、 dp\lbrack N \rbrack\lbrack N \rbrack\lbrack k \rbrack とか実際に要らないところまで回してしまっているのですが、まあ計算時間が約2倍になるだけで十分間に合うので…添字の演算を増やしてつまらないバグを混入させたくないので、私はコンテスト本番だとこういう実装をたまにやります。

満点解法

満点解法は、どのような動きが最適になるのかをある程度考える必要があります。とはいえ、全探索できるものは全探索します。

私の解き方では、

  • 左側/右側に移動して訪れる木がいくつあるか( N+1 通り)
  • 最初に左右どちらに移動するか(2通り)
  • 最後に左右どちらに移動するか(2通り)

を全探索しています。これら全部の組み合わせは  4(N+1) 通りです。以降、これらを何か1つに固定したものを「パターン」と書くことにします。

左右に訪れる木の本数を固定すると、そこで円周を切り開くことができます。円周だと図も描きにくいので、以降は直線で考えていきます。

f:id:betrue12:20181230212358p:plain

以降、左右それぞれへの「移動回数」というものを考えます。これは一度その向きへの移動を始めてから、折り返すか止まるまでを1回とします。例えば上の図では、左の移動回数が3回、右の移動回数が2回です。移動は未訪問の木に向かって行うので、左右ともに移動回数が木の本数を超えることはできません。

最初と最後の移動の向きを決めると、それによって左右の移動回数の「差」が決まります。例えば最初も最後も左だった場合、先ほどの例のように左に移動する回数は右に移動する回数より1回多いです。最初と最後の移動の向きが異なる場合、左右の移動回数は同じです。

パターンを1つ固定すると、左右にいくつ木があるかが決まり、左右の移動回数の差も決まります。これらが決まると、左右の移動回数の最大値を求めることができます。

移動距離を稼ぐにはなるべく多くの回数折り返したほうが得なので、この最大値を満たすように移動するのが良いです。またなるべく遠い位置で折り返したほうが距離を稼げるので、左右それぞれについてスタート地点から遠い木を折り返し地点として選びます。結果として移動の経路は以下のようになります。

f:id:betrue12:20181230213301p:plain

このような移動の合計距離は以下のように計算できます。

  1. 左右それぞれ、移動回数と同じ本数だけ外側から木を選び、スタート地点からその木までの距離を2倍(往復分)したものを全て合計する。
  2. その後、最後に訪れる木だけはスタート地点から片道だけの距離しかないので、片道分の距離を引く。

これがこの固定パターンにおける最適値です。この計算で必要なのは  X_{i}, Y_{j} それぞれの「連続する要素の和」なので、累積和を用いれば1パターンあたりは  O(1) で計算できます。

これを  4(N+1) パターン全部試して最も良いものを答えとします。全体計算量が  O(N) となり、満点を取ることができます。

満点獲得コード

Submission #3895457 - AtCoder Grand Contest 030

コードでは

  • 左側に移動して訪れる木の本数を d とする
  • k1 == 0 のとき、最初に左側に移動する
  • k2 == 0 のとき、最後に左側に移動する

という3変数で各パターンを全探索しています。

また、cx, cy がそれぞれ左右の移動回数の最大値です。移動回数の差を処理するために変なことをしていますが、普通にif場合分けで十分だと思います…

Educational Codeforces Round 57 参加記録&解説(A~F)

 998244353 猛プッシュ回。その真意はG問題にありましたが、私は解けませんでした…

f:id:betrue12:20181229143906p:plain

※2019/01/16 E問題を追記。

A. Find Divisible

Problem - A - Codeforces

問題概要

以下の問題  T 個に答えよ。

  • 整数  l, r が与えられる。 l \le x, y \le r かつ  x \ne y かつ  x y の約数であるような整数  x, y を1組求めよ。

制約

  •  1 \le T \le 1000
  •  1 \le l \le r \le 998244353
  • 解の存在が保証されている

解法

 x y もある区間内に収めないといけないので、なるべく近くしたいです。そうすると  y = 2x となるような値を取りたくなります。

そのうえで  x区間の左端ギリギリに取ると  x = l, y = 2l であり、これが最も「区間に含まれやすい」ペアになります。これが区間  \lbrack l, r \rbrack に含まれない場合は解が存在しないので、入力としては与えられません。

ACコード

Submission #47625206 - Codeforces

B. Substring Removal

Problem - B - Codeforces

問題概要

長さ  n の文字列  s が与えられる。この  s の空でない連続部分列のとり方のうち、「その連続部分列を取り除くと、残った文字が1種類または0種類になる」という条件を満たすものの個数を求め、998244353で割った余りを出力せよ。

制約

  •  2 \le n \le 2\times 10^{5}
  •  s は英小文字からなる
  •  s には少なくとも2種類の文字が含まれている

解法

いくつかの場合に分けて考えます。

  • 全部の文字を取り除く
    • 問題文よりこれはカウント対象になるので、必ず1通りが加算されます。
  • 文字列の右側を取り除く
    • 左端の文字が残るので、「左端から連続して1種類だけの文字を残す方法は何通りあるか?」ということになります。これは左端から連続して同じ文字がいくつ続いているかの値と一致します。
  • 文字列の右側を取り除く
    • さっきと逆です。
  • 文字列の真ん中を取り除く
    • この場合、まず左端の文字と右端の文字が一致していることが必要です。一致している場合、左端から何文字残すか、右端から何文字残すかをそれぞれ掛け算すればよいです。

まとめると、左端から同じ文字が連続している個数を  l 、右端から同じ文字が連続している個数を  r とすると、

  • 左端と右端の文字が一致している場合:  1 + l + r + lr
  • そうでない場合:  1 + l + r

が求める数となります。オーバーフローと余りを取る操作については注意しましょう…

ACコード

Submission #47630409 - Codeforces

C. Polygon for the Angle

Problem - C - Codeforces

問題概要

以下の問題  T 個に答えよ。

  • 度数法の角度を示す整数  ang が与えられる。「正  n 角形においてある3頂点を取った時、なす角が  ang になる」という条件を満たす最小の  n を求めよ。またはそのような  n が存在しないことを判定せよ。

制約

  •  1 \le T \le 180
  •  1 \le ang \lt 180
  • 答えが存在する場合は  n \le 998244353 であることが保証される

解法

※説明中に点a, b, cという表記を使います。問題文中の図に合わせているのでそちらを参照してください。

正多角形は円に内接するので、円として考えます。円周角の定理を使うと、円周上の3点を取った時のなす角を計算することができて、これは

  •  180^\circ \times \frac{(弧acの長さ)}{(円周の長さ)}

となります。ただし弧acは点bと反対側の弧とします。

今回の場合は正多角形なので、弧acが正  n 角形の辺  k 本に対応している場合

  •  ang = 180 \times \frac{k}{N}

となります。この  k が整数で、かつ  k \lt N-1 である必要があります。 k = N-1 だと、弧acの反対側に1つも頂点がなく、点bを取ることができないからです。(サンプルにあるように90角形で2度を作れないのはこの条件によるものです)

あとは  n を総当たりしていけばよいです。実際にやってみると  3 \le n \le 360 で制約内の全ての  ang について答えが出るので、この範囲で総当たりすれば十分間に合います。

ACコード

Submission #47634550 - Codeforces

D. Easy Problem

Problem - D - Codeforces

問題概要

[tex n] 文字の文字列  s が与えられる。この文字列から0個以上の文字を取り除き、部分列(連続とは限らない)に hard という文字列を含まないようにしたい。

 i 文字目を取り除くコストは  a_{i} である。条件を満たすための最小コストを求めよ。

制約

  •  1 \le n \le 10^{5}
  •  s は英小文字からなる
  •  a \le a_{i} \le 998244353

解法

左からDPをします。「  i 文字目まで見て、 hard のうちちょうど  j 文字目までが部分列に含まれているようにするための最小コスト」を  dp\lbrack i \rbrack \lbrack j \rbrack とします。

例えば  j = 1 のとき、既に部分列は h を含んでいることになります。この状態で a を消さずに受け入れてしまうと、 j = 2 に遷移をしてしまいます。 j = 4 になるとアウトです。

より一般的に  dp\lbrack i \rbrack \lbrack j \rbrack からの遷移を考えます。次の文字  s\lbrack i+1 \rbrackhard j+1 文字目と一致していない場合はノーコストで  dp\lbrack i+1 \rbrack \lbrack j \rbrack に遷移できます。一致している場合は、

  • 取り除くためのコストを加算し、 dp\lbrack i+1 \rbrack \lbrack j \rbrack に遷移する。
  • その文字を受け入れて、コストを加算せずに  dp\lbrack i+1 \rbrack \lbrack j+1 \rbrack に遷移する。

の2通りがあります。

これを文字列の最後まで行い、 dp\lbrack N \rbrack \lbrack 0 \rbrack dp\lbrack N \rbrack \lbrack 3 \rbrack のうち最も小さいものが答えです。

ACコード

Submission #47636462 - Codeforces

E. The Top Scorer

Problem - E - Codeforces

問題概要

 p 人の人がゲームを行った。全員の得点は非負整数で表され、その合計は  s 点だった。一番点数が高い人が優勝者であり、複数人いる場合は等確率で誰か1人が優勝者に選ばれる。

あるプレイヤー(ハサン)の得点は  r 点以上だったことが分かっている。プレイヤー同士は区別され、全員の得点分布としてあり得るもの全てが等確率で起こるとしたとき、ハサンが優勝する確率を求めよ。

答えは有理数となるため、答えを既約分数  \frac{P}{Q} としたときの  PQ^{-1} \mod 998244353 を出力せよ。

制約

  •  1 \le p \le 100
  •  0 \le r \le s \le 5000

解法

「一番点数が高い人が複数いる場合は等確率で誰か1人が優勝者となる」の部分がとても厄介に見えます。幸い人数  p は小さいので、「同着一位が何人いるか」を全て場合分けすることを考えます。

さらに優勝者の点数も全探索すると、「ハサンが  a 点取って一位となり、ハサンも含めた同着一位が  b 人いるような場合の数」というものを考えることができます。それぞれの動く範囲は  r \le a \le s 1 \le b \le p で、さらに  ab \le s が満たされている必要があります。

この場合、まずハサン以外に  a 点を取った人は誰かという選び方が  _{p-1}C_{b-1} 通り。そして残った  s-ab 点を  p-a 人で分ける分け方で、残り全員の点が  a 点未満であるような場合の数を掛け算すると、パラメータ  (a, b) に対応する場合の数が求められます。

というわけで必要なものは、「 x 点を  y 人で分ける分け方で、全員の点が  z 点未満であるような場合の数」です。これは包除原理を用いると、

  •  x 点を  y 人で分ける分け方で、ある  i 人を選んだ時にその  i 人が  z 点以上を取っているような場合の数」 \times (-1)^{i}

を、全ての  i=0, 1, ..., y および全ての  i 人の選び方について足したものとして求められます。

これを求めます。 y 人の中で  i 人選ぶのが  _{y}C_{i} 通り。そしてその人達に予め  z 点ずつを割り振っているので残りの点数は  x - iz 点となり、この点は  i 人の中に選んだかどうかに関わらず自由に  y 人に割り振って良いので、重複組合せを用いて  _{x-iz+y-1}C_{y-1} 通りとなります。この2つを掛け算すると求めたい場合の数が求められます。

最後に、求めたいものは確率なので、場合の数から確率にするために全ての場合の数が必要です。これも重複組合せを用いて求めることができて、 r 点をハサンに割り振った残りの  s-r 点を自由に割り振ると考えると  _{s-r+p-1}C_{p-1} となります。

これで全ての材料が揃いました。解法の手順としては、

  1. 必要な分の階乗と階乗逆元を前計算しておく。
  2. 「ハサンが  a 点取って一位となり、ハサンも含めた同着一位が  b 人いるような場合の数」を、組み合わせや包除原理を用いて求める。これを同着人数  b で割ったものを取り得る全ての  (a, b) について計算し合計しておく。
  3. 上記の合計を、全ての場合の数で割る。これが求めたい確率である。

となります。 a, b そして包除原理における  i を全探索するので、 r が小さい時(計算量がより悪い時)を考えると全体計算量は  O(sp^{2}) となります。

ACコード

Submission #48426919 - Codeforces

F. Inversion Expectation

Problem - F - Codeforces

問題概要

長さ  n の数列  p_{1}, ..., p_{n} が与えられる。これは  1, ..., n を並び替え、いくつかを  -1 に置き換えたものである。

 1, ..., n のうち数列に登場しない整数を1つずつ  -1 の場所に当てはめる。どのような当てはめ方も同じ確率であるとする。このとき、数列の転倒数の期待値を求めよ。

答えは有理数となるため、答えを既約分数  \frac{P}{Q} としたときの  PQ^{-1} \mod 998244353 を出力せよ。

制約

  •  1 \le n \le 2\times 10^{5}
  •  p_{i} 1, ..., n または  -1 であり、 -1 でない要素は相異なる

解法

与えられた数列において  -1 でない要素を確定済み、  -1 である要素を未確定の要素と呼ぶことにします。

転倒数を、「確定済み・確定済みのペア」「未確定・未確定のペア」「確定済み・未確定のペア」の3種類に分けて計算していきます。

確定済み・確定済みのペア

これは普通に転倒数を求めればよいです。BITを使うことができます。

入力に  -1 が存在しない場合は、ここで計算をやめて出力すればよいです。

未確定・未確定のペア

入力に含まれる  -1 の個数を  k 個とします。このとき、未確定同士のペアは全部で  \frac{k(k-1)}{2} 個あります。

これらそれぞれのペアについて、「転倒している」つまり大きい値が小さい値よりも左に置かれる確率は  \frac{1}{2} です。

つまり未確定同士のペアによる転倒数の期待値は  \frac{k(k-1)}{4} となります。4で割り切れない可能性があるので割り算には逆元を使いましょう。

確定済み・未確定のペア

これが一番面倒でしょうか。

f:id:betrue12:20181229142508p:plain

この図に、「確定済み要素 > 未確定要素」である転倒ペアの数え方をまとめています。確定済み要素それぞれについて、「右側にいくつ未確定要素があるか」を重みとしてBITに加算します。

次に未確定の整数それぞれについて、BITで自分より数値が大きい範囲の区間和を求めます。そうするとこれは、「その未確定の整数を  -1 のどこかに置いたときに転倒ペアがいくつできるか」を、全ての  -1 の位置について合計したものになります。

ある未確定の整数がある  -1 の位置に入る確率は  \frac{1}{k} なので、期待値はさきほどの値を  \frac{1}{k} 倍したものになります。

「確定済み要素 < 未確定要素」である転倒ペアの個数も同じようにして求めることができます。

また、この計算では確定済みの要素について全部BITに加えてから区間和を取るので、BITではなく通常の累積和でも可能です。どのみち確定済み・確定済みのペアの計算でBITを使うので、BITを使ってしまったほうがバグりにくくて楽だとは思います。

これらのパターン全てを合計すると答えが求められます。

ACコード

Submission #47644155 - Codeforces

Codeforces Round #529 参加記録&解説

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

だいたい1時間で全完。平和なDiv3でした。

f:id:betrue12:20181228151449p:plain

A. Repeating Cipher

Problem - A - Codeforces

問題概要

ある文字列  s に対して、各文字を「1文字目を1個、2文字目を2個…」と並べた文字列  t が与えられる。 t から  s を復元せよ。

制約

  •  1 \le |s| \le 10
  •  1 \le |t| \le 55
  • 解の存在が保証されている

解法

解の存在が保証されているので、 s のそれぞれの文字が  t の何文字目に存在するかを計算して集めてくればよいです。

ACコード

Submission #47556204 - Codeforces

B. Array Stabilization

Problem - B - Codeforces

問題概要

長さ  n の数列  a_{1}, ..., a_{n} が与えられる。この数列から1つ要素を取り除いて「要素の最大値 - 要素の最小値」を最小にするとき、その値を求めよ。

制約

  •  2 \le n \le 10^{5}
  •  1 \le a_{i} \le 10^{9}

解法

最も大きい値を取り除くか、最も小さい値を取り除くかのどちらかが最適となるので、両方試します。要素をソートして「1番目に大きい要素 - 2番目に小さい要素」と「2番目に大きい要素 - 1番目に小さい要素」を両方計算して小さい方が答えです。

ACコード

Submission #47558356 - Codeforces

C. Powers Of Two

Problem - C - Codeforces

問題概要

整数  n, k が与えられる。 n をちょうど  k 個の2冪数の和で表現する方法を1つ出力せよ。またはそれが不可能であることを判定せよ。

制約

  •  1 \le n \le 10^{9}
  •  1 \le k \le 2\times 10^{5}

解法

まず、 n を最も少ない個数の2冪数の和に分解します。これは2進数展開をすればよいです。この時点で  k 個を超えてしまった場合は分割不可能です。

その後、「1でない2冪の数を1つ選んで半分ずつに分割する」という操作を  k 個になるまで繰り返せばよいです。個数が足りないのに分割できない場合(具体的には  n \lt k のとき)は不可能です。

実装は「 2^{m} の数が今いくつあるか」を  m ごとに個数で管理して、大きい方から見ていくと良いと思います。

ACコード

Submission #47563042 - Codeforces

D. Circular Dance

Problem - D - Codeforces

問題概要

 1, ..., n までの番号を持つ人が円形に並び、全員が時計回りの方向を向いている。各人について1つ先の人と2つ先の人の番号の情報が与えられるが、どちらがどちらかは与えられない。人の並び方としてあり得るものを1つ出力せよ。

制約

  •  3 \le n \le 2\times 10^{5}
  • 解の存在が保証されている

解法

まず  n = 3 の場合を除外しておきます。このときは各人について自分以外の2人の番号が与えられる場合しかないので、どのように並べても条件を満たします。適当に 1 2 3 などを出力しておけばよいです。

 n \gt 3 の場合、まず基準として1人目を番号1の人とします(誰でも良いです)。この1人目の次の2人、つまり2人目と3人目が  a_{1, 1} a_{1, 2} のどちらかです。

このとき、2人目の「次の2人」には3人目が含まれていて、3人目の「次の2人」には( n \gt 3 であれば)2人目は含まれていません。そのため  a_{1, 1} a_{1, 2} のうち、「次の2人」にもう片方を含んでいるほうが2人目になります。

これを最後の1人まで順番に繰り返していくと全ての順番が決まります。

ACコード

Submission #47565769 - Codeforces

E. Almost Regular Bracket Sequence

Problem - E - Codeforces

問題概要

長さ  n の括弧列  s が与えられる。 s の文字のうち、「その1文字を反転させることで  s が正しい括弧列になる」という条件を満たす文字の個数を求めよ。

制約

  •  1 \le n \le 10^{6}

解法

( を+1、) を-1として、 s の累積和を求めます。正しい括弧列の条件は

  • 任意の区切り位置で、累積和が0以上である。
  • 全ての文字の合計がちょうど0になる。

の2つを満たすことです。

まず合計だけを考えます。1文字の変更後に合計が0になることが必要条件なので、

  • 合計が2の場合、() に変えることで正しい括弧列になる可能性がある。
  • 合計が-2の場合、)( に変えることで正しい括弧列になる可能性がある。
  • そうでない場合、1文字変更後に正しい括弧列になることはない。

と場合分けできます。ここでもし合計が2の場合は  s 全体を鏡写しに(実装においては、文字列全体を反転させ、() を反転)することで合計が-2の場合と同一視できるので、こちらだけを考えます。

全体の合計が-2のときに、)( に変えることで正しい括弧列になる条件を考えます。

f:id:betrue12:20181228022040p:plain

上の図のように、文字を変更することで変更箇所より右側の累積和が+2されます。この状態で全ての位置の累積和が0以上になればよいので、

  • 変更位置より左側の累積が0以上である
  • 変更位置より右側の累積が-2以上である

ような ) が条件を満たします。あとはこれを順番に探していけばよいです。

ACコード

Codeforces

F. Make It Connected

Problem - F - Codeforces

問題概要

 n 個の頂点からなる無向グラフがあり、初期状態においては辺が存在しない。各頂点には整数  a_{i} が書かれている。

このグラフには以下の方法で辺を追加できる。

  • 通常の方法:頂点  i と 頂点  j を、コスト  a_{i} + a_{j} で結ぶ。
  • 特別な方法:「頂点  x と頂点  y をコスト  w で結んでよい」という条件が  m 個与えられるため、それを使う。

辺を追加し全ての頂点を連結にするまでの最小コストを求めよ。

制約

  •  1 \le n \le 2\times 10^{5}
  •  0 \le m \le 2\times 10^{5}
  •  1 \le a_{i} \le 10^{12}
  •  1 \le w \le 10^{12}

解法

最小全域木を作るように辺を追加していけばよいです。

あり得る辺を全て考えようとすると、  O(n^{2}+m) 本の辺を扱わないといけないので間に合いません。ただしこの問題の場合は、コストの最も小さい頂点を1つ固定すると、その頂点以外の2頂点を「通常の方法」で連結する辺は不要であることが分かります。

その理由をクラスカル法のアルゴリズムを元にして考えてみます。クラスカル法ではコストの小さい辺から順に、「その辺の両端が既に連結済みでなければ辺を追加する」ということを繰り返します。また、同じコストの辺はどちらを先に使っても正しい解が得られます。

例えば頂点1のコストが最も小さく、  a_{1} \le a_{2} かつ  a_{1} \le a_{3} であるとします。頂点  i, j を通常の方法で結ぶコストを  e_{ij} と表記すると、  e_{12} \le e_{23} かつ  e_{13} \le e_{23} が成立します。

つまりクラスカル法のアルゴリズムに基づいて辺を追加するならば、辺2-3よりも先に辺1-2と辺1-3の追加が行われて、その時点で頂点1, 2, 3が連結になります。そうなると、辺2-3を追加する意味はなくなります。

これをより一般的に考えると、「通常の方法」で追加する辺については、コストの最も小さい頂点を1つ固定し、そこから他頂点に伸びる  n-1 本の辺だけを考えれば十分であることが言えます。

あとはこれを「特別な方法」で追加できる  m 本の辺と混ぜてソートし、クラスカル法を回すことで答えが得られます。辺の数  E = n-1+m に対して計算量  O(E \log E ) なので間に合います。

ACコード

Submission #47575989 - Codeforces

Codeforces Round #528 参加記録&解説(A~D)

Dashboard - Codeforces Round #528 (Div. 1, based on Technocup 2019 Elimination Round 4) - Codeforces

配点の高いDを通し、なんとDiv1で81位!これはそうそう出るものじゃないですね。レートも爆上げ。

f:id:betrue12:20181225203444p:plain

A~Dを振り返ります。Div2ではC~Fに対応します。

A. Connect Three

Problem - A - Codeforces

問題概要

2次元グリッド上の3つのマス  A, B, C の座標が与えられる。マスを選んで道を作り、これら3マスを相互に通行可能にしたい。道同士は辺で連結されている場合に通行可能であり、マス  A, B, C も道にする必要がある。

最小のマス数で道を作る時、その道の例を1つ示せ。

制約

  • 与えられるマスの座標は  1 \le x, y \le 1000

解法

色々場合分けが必要そうに見えたり、コーナーケースが怖くなるような問題ですが、私の解法を書きます。

  1. 3点の  x 座標のうち真ん中のものを1つ選び  x_{c} とする。3点の  y 座標の最小値・最大値をそれぞれ  y_{m}, y_{M} として、 x= x_{c}, y_{m} \le y \le y_{M} の点を全て道にする。
  2.  x_{c} として選んだもの以外の2点から、先ほどの線に垂直に道を作る。  x 座標が  x_{c} と一致している点については何もしない。

図で表すと以下のようになります。座標が重複している場合等も含めてこれで上手くいきます。

f:id:betrue12:20181225231315p:plain

ACコード

B. Minimum Diameter Tree

Problem - B - Codeforces

問題概要

 n 頂点の木が与えられる。この木の各辺に非負実数の重みを割り当て、重み合計が  s となるようにする。

この木におけるパスの重みを通る辺の重みの合計とし、木の直径を全てのパスの重みの最大値とする。木の直径を最小にするように重みを割り当てるとき、その直径の値を求めよ。

制約

  •  2 \le n \le 10^{5}
  •  1 \le s \le 10^{9}
  • 与えられるグラフは木

解法

結論から言ってしまうと、葉から伸びる各辺に重みを均等に割り振ってしまうのが最適となります。葉の数が  k のとき1辺の重みは  \frac{s}{k} であり、任意のパスは葉を高々2個含むので、直径は  \frac{2s}{k} となりこれが答えです。

コンテスト本番はサンプルの例から類推するか、「中途半端な辺は多くのパスに含まれるので、ここに重みを割り振るのは損になりそう」という感覚で解いてしまうかもしれません。一応証明します。

証明

異なる葉同士を繋ぐ全てのパスを考えます。木における任意のパスの重みの最大値  D は、異なる葉同士を繋ぐパスの重みの最大値と一致します。葉と葉をつないでいないパスは、適当に両端を葉まで伸ばすことでそれ以上の長さのパスが作れるからです。

異なる葉同士を繋ぐパスは葉の数を  k として  _{k}C_{2} 本あります。これらの重みの総和を  S とします。

任意の割り振りで辺に重みを割り当てたとします。ある辺  e に割り振った重みを  w_{e} とすると、 w_{e} はどれほど  S に寄与するでしょうか?

 e によって葉は2つの集合に分断されます。その一方の個数を  a 、もう一方の個数を  k-a とすると、異なる葉同士を繋ぐパスで辺  e を通るものは全部で  a(k-a) 本あるため、辺  e の重みは  S a(k-a)w_{e} 寄与します。

このとき  1 \le a \le k-1 であり、 a(k-a) - (k-1) = -(a-1)(a-(k-1)) \ge 0 であることから  a(k-a) \ge (k-1) が成り立ちます。そのため全ての辺について重みの寄与分を足すと、

  •  S \ge (k-1) \sum_{e} w_{e} = (k-1)s

となります。  _{k}C_{2} 本のパスの重み合計が  (k-1)s 以上であるため、重みの最大値  D について

  •  D \ge \frac{(k-1)s}{_{k}C_{2}} = \frac{2s}{k}

が成立します。この右辺の値は冒頭の最適解(仮定)と一致するため、冒頭の構成方法の最適性が証明できました。

ACコード

C. Vasya and Templates

Problem - C - Codeforces

問題概要

以下の問題が  t 個与えられる。

  • a から順に  k 種類のアルファベットからなる文字列  s, a, b が与えられる。 k 種類のアルファベットを置換する方法で、 s を置換した後に辞書順で  a \le s \le b となるようなものを1つ答えよ。またはそのような置換が存在しないことを判定せよ。

制約

  •  1 \le t \le 10^{6}
  •  1 \le k \le 26
  •  1 \le |s| = |a| = |b| \le 10^{6}
  • 全ての入力文字列の合計文字数は  3\times 10^{6} を超えない

解法

DFSで文字列を前から順番に見ていきつつ、置換の割り当てを決めていきましょう。イメージとしては桁DPです。

「既に割り当て済みの置換がこれこれで、  k-1 文字目までが辞書順の条件を満たしているとき、 k 文字目の割り当てを決める」という処理を考えます。このとき、「それより前のインデックスで、 a より真に大きい状態になっているか?  b より真に小さい状態になっているか?」という情報を追加で持ちます。これがちょうど桁DPの「上限値より真に小さいことが確定しているか」という情報と似ています。

DFSの探索において、 s\lbrack k \rbrack が既に割り当て済みのアルファベットだった場合は大小関係だけをチェックします。新しいアルファベットだった場合は、次のように割り当てを行います。「真に大きい/小さい」という条件を確定させたほうが有利なので、なるべくそれが成立するものを優先的に選ぶようにします。

  •  a より真に大きく、 b より真に小さいことが確定している場合、それ以降は任意に割り当てて良い。空いているものを好きに選ぶ。
  •  a より真に大きい場合、 b についての条件だけを考えれば良いので、  b\lbrack k \rbrack 以下のアルファベットで空いているものを選ぶ。特に   b\lbrack k \rbrack より真に小さいものが空いていれば優先的に選ぶ。
  •  b より真に小さい場合、 a についての条件だけを考えれば良いので、  a\lbrack k \rbrack 以上のアルファベットで空いているものを選ぶ。特に   a\lbrack k \rbrack より真に大きいものが空いていれば優先的に選ぶ。
  • どちらでもない場合、 a\lbrack k \rbrack 以上かつ  b\lbrack k \rbrack 以下のアルファベットで空いているものを選ぶ。特にその間にあるアルファベットが空いていれば優先的に選ぶ。

このようなDFSを行う時、そのステップ数はどうなるでしょうか。1度「 a より真に大きく、 b より真に小さい」という状態にたどり着ければ、その後はストレートで解にたどり着くため探索が終了します。これらの条件が確定しないままのDFSは、 a または  b に「沿った」探索しかないため、全体の分岐の中でも高々2本だけです。そのため分岐の本数は高々3本しかなく、ステップ数は文字列の長さを  n として  O(n) となります。

各ステップの計算量で入力に依存しそうなのは空いているアルファベットの探索であり、全探索しても全体  O(kn) です。これでオーダーとしては間に合いますが…とにかく入出力の数が多いので、高速な言語および入出力(C++なら scanf/printf )を使わないとひたすらTLEします。つらい。

ACコード

D. Rock-Paper-Scissors Champion

Problem - D - Codeforces

問題概要

 n 人のプレイヤーが一列に並び、じゃんけんをする。各プレイヤーが出す手は決まっている。このとき以下のルールでじゃんけんを進める。

  1. 隣り合う2人を選び、じゃんけんをさせる。あいこの場合はどちらを勝たせても良い。
  2. 負けた方を列から取り除く。
  3. これを最後の1人が残るまで繰り返す。

「じゃんけんをさせる組の選び方やあいこの勝敗も含めて好きなように操作をするとき、優勝する可能性があるのは何人か?」を求めたい。

ただしクエリが  q 個与えられ、各クエリは「  p_{j} 番目の人の手を  c_{i} に変更する」というものである(クエリの効果は累積する)。初期状態および各クエリを処理した後の全ての状態について、優勝する可能性のある人数を求めよ。

制約

  •  1 \le n \le 2\times 10^{5}
  •  1 \le q \le 2\times 10^{5}

解法

とりあえずクエリは無視して、各参加者の手が固定されているときにそれぞれの人が優勝できる条件を考えます。

例としてグーの手の人が優勝できるかを考えます。もちろん、グーだけでなく全ての手の人の優勝可能性について同じ方法が使えます。

パーと当たらなければ良いので、グーの人は「全てのパーを、自分が当たる前にチョキ(または他のパー)に倒してもらえる」場合に優勝できます。この条件は、

  • 自分より左にパーがいないか、自分より左にチョキがいる
  • 自分より右にパーがいないか、自分より右にチョキがいる

ことの両方を満たすこと、と言い換えられます。片側にいる全てのパーを同じ側のチョキと必ず戦わせることができるのかは考えなければいけませんが、その間にいる人同士を残り1人になるまで適当に戦わせることにすれば、最後に残った1人はパーとチョキの少なくとも片方で倒せるので、戦わせることは必ず可能です。

ということで、グーの人がどの範囲にいれば優勝できるかを考えると、次のようになります。

  • パーがいない場合、全てのグーが優勝できる。
  • パーがいてチョキがいない場合、全てのグーが優勝できない。
  • 両方いる場合、以下の範囲以外のグーが優勝できる。
    • 最左のパーより右で、最左のチョキより左。
    • 最右のパーより左で、最右のチョキより右。

f:id:betrue12:20181226001525p:plain

かなりシンプルな形になりました。あとはこれをどう効率的に処理するかをクエリ込みで考えていきましょう。

ある範囲内にいるグーの人数は累積和、クエリによる変動を考慮するとBITで処理できます。最左/最右にいるチョキ/パーの位置はsetに入れて最小値/最大値を見ればよいです。このように処理すればクエリ処理と答えを求める処理をともに  O(\log n ) で実現でき、初期状態の構築込みで全体計算量  O((n+q)\log n ) となり間に合います。

ACコード

私の印象としてはCよりこちらのほうが簡単だったり…?考察寄りの問題が多いAtCoderに慣れていると、こちらのほうが解きやすく感じるかもしれません。AGCで出てきそう。