AtCoder Beginner Contest 241（Sponsored by Panasonic）のきろく

AtCoder 競技プログラミング AtCoder Beginner Contest 参戦記

AtCoder Beginner Contest 241（Sponsored by Panasonic）に参加。

A - Digit Machine (100点)

a_{a_{a_0}} が答えです。
見にくいので別表記すると f(x) = a_x として f^3(0) = f(f(f(0))) となります。

B - Pasta (200点)

std::mapで各長さの麵の本数を管理すると楽。

C - Connect 6 (300点、実行時間制限: 3 sec)

4 マス以上が黒であるような連続 6 マスが存在するとき、答えはYes、そうでないときNoとなります。
連続 6 マスは各マスから8方向へ6回探索すればよく、それぞれについて黒マスの数を数えればいいです。
尚、全てのマスについて調べるので8マスのうち半分は調べなくてもいいです((上, 下), (左, 右), (左上, 右下), (右上, 左下)の各組について片方のみでよい)。

斜めについて 6 マスに達してないのにYesにしてしまうというミスで4WAしました...

D - Sequence Query (400点)

k は高々 5 であるので、std::multisetやstd::mapで管理したとき、イテレータの移動が高々 5Q 回なので、間に合います。
前にbegin()を超えるかよりも後ろにend()を超えるかを判定する方が楽だったりするので、c_i = 2 のクエリについては全体に -1 を掛けたもので行うと少し楽になるかも(人に依る?)。

std::multisetでbegin()やend()を超えて操作を行ってしまったコードを出してしまい、1TLEしてしまいました...

E - Putting Candies (500点)

ダブリングを行います。

{\mathrm{dp}}_{i,j} = (\text{\(X=i\) から \(2^j\) 回の操作を行った後の飴の個数})
とします。このとき N で割った時の商と余りに注目することで
{\mathrm{dp}}_{i,j} = \left\{ \begin{array}{ll} i + A_i & (j = 0)\\ \displaystyle \left\lfloor \frac{{\mathrm{dp}}_{i,j-1} }{N} \right\rfloor N + {\mathrm{dp}}_{{({\mathrm{dp}}_{i,j-1} \mod N)},j-1}& (j \neq 0) \end{array} \right.
となるので、K を二進数で表した時、1 である桁を下から s_1,\,s_2,\,\dots,\,s_n とした時、最初 a = 0 として i を 1 から n へ順に
a \leftarrow \displaystyle \left\lfloor \frac{a }{N} \right\rfloor N +{\mathrm{dp}}_{{(a \mod N)},s_i}
を繰り返して、最終的な a が答えとなります。
本番では各DPの値は (商, 余り) の組として実装しました。

F - Skate (500点)

H も W も最大で 10^9 まで取りえるので、全てのマスについて調べることはできません。しかし、途中で立ち寄ることができるマスは障害物の上下左右いずれかの隣接マスのみなのでスタート地点を入れても高々 4N + 1 箇所です。そのため、これらの限定した頂点についてのBFSで答えを求めることができます。
ぶつかる障害物についてはstd::map<int, std:::vector>での二分探索によって求めることができます。

G - Round Robin (600点)

終了後に解説ACしました。
この解説のとおりに実装しました。
試合からプレイヤーへの辺のうち一方にしか流せないようにすることで一方のみが勝つという状況を表せるのがすごいと思いました。
ちゃんとフローについて勉強しなきゃ...

Ex - Card Deck Score (600点、実行時間制限: 3 sec): 未提出

多項式.... 分かんね...

結果、感想

f:id:Flkanjin:20220227030343p:plain
1700附近まで回復させることができました。でもCの4WAで焦ってしまったのは要反省だなと思いました。

Educational Codeforces Round 123のきろく

Codeforces 競技プログラミング Educational Codeforces Round 参戦記

問題文和訳はこちら

A. Doors and Keys / Двери и ключи

R, G, Bの各文字について大文字よりも前に小文字があるかを調べます。find関数を用いたり、配列で既出かどうかを記憶するなどの方法があります。

B. Anti-Fibonacci Permutation / Антифибоначчиевы перестановки

降順順列 (n,\,n-1,\,\dots,\,2,\,1) は条件を満たします。また、この順列の連続する2要素を入れ替えたものも条件を満たすので、これで n 通りの順列を作ることができました。

C. Increase Subarray Sums / Увеличь суммы подотрезков

1 \leq n \leq 5000 であるので O(n^2) であっても大丈夫なので、初期状態での全ての部分列の和を計算することができるので、長さ毎にその最大値を記憶します。長さ i のものを m_i とします。
この時 f(k) = \displaystyle \max_{i} (m_i + x\min\{k,\,i\}) となるのでそれぞれ計算することができます。

D. Cross Coloring / Раскраска крестиками

最終的な盤面において各セルのについて何番目の操作で着色されたのかが分かれば、最終的な彩色に関わる操作が l 個存在するとき答えは k^l \bmod 998244353 となります。

i 番目の操作は、それ以降に行 x_i と列 y_i の両方が塗り替えられる、もしくは全ての行か全ての列が塗り替えられる、のいずれかを満たした時、最終的な彩色に関わず、そうでないとき、関わります。そのため、最後の操作から逆順にどの行や列が操作されたかを記憶しておくことで答えを出せます。しかし、「全てのテストケースでの q の和は 2 \cdot 10^5 を超えない」という制約はありますが、n についてはそうでないため、その和は 4 \times 10^{10} にまでなる可能性があるので、配列で管理するとTLEとなります。そのため、出てきた行や列をstd::setやstd::unordered_setで管理して計算量を落とす必要があります。(これに気附かず、何度もペナルティを食らいました...)

E. Expand the Path / Расширь маршрут: 未提出

分かりそうで分からない...

F. Basis / Базис (実行時間制限: 6 sec): 未提出

さっぱりですね。

結果、感想

f:id:Flkanjin:20220223213015p:plain
レートが上がりましたが、Dのペナルティ酷いなぁ... ちゃんと条件を読むようにしないと...

Educational Codeforces Round 123 問題文和訳

Codeforces 競技プログラミング Codeforces 和訳 Educational Codeforces Round 和訳

A. Doors and Keys / Двери и ключи

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
騎士が細長い廊下の前に立っています。その反対側に姫が待っています。

廊下には、赤、緑、青の扉の3つの扉があります。扉は順々に並んでいますが、順番は違うものかもしれません。次の扉に進むためには、騎士はまず、先の扉を開かなければなりません。

それぞれの扉は、対応する色の鍵でのみ開けることができます。赤、緑、青の鍵の3つの鍵も廊下のどこかに置かれています。扉を開けるためには、騎士はまず、その色の鍵を拾う必要があります。

騎士は廊下の地図を所持しています。その地図は、6文字から成る文字列として記述することができます。

  • R, G, B: それぞれ赤、緑、青の扉を表す
  • r, g, b: それぞれ赤、緑、青の鍵を表す

この6文字はそれぞれちょうど1度ずつだけ文字列の中に現れます。

騎士は通路の前、即ち地図の左側に立っています。

廊下の地図が与えられたとき、騎士が全ての扉を開けて廊下の先にいる姫に会うことができるかどうかを判定して下さい。

入力

1行目には単一の整数 t (1 \leq t \leq 720) が与えられる、これはテストケースの個数である。

各テストケースは単一の文字列から成る。各文字はR, G, B(扉)、r, g, b(鍵)のいずれかで、それぞれちょうど一回ずつ現れる。

出力

各テストケースについて、騎士が全ての扉を開けることができる場合、YESを出力せよ。そうでない場合、NOを出力せよ。

入出力例

4
rgbBRG
RgbrBG
bBrRgG
rgRGBb
YES
NO
YES
NO

注記

1つ目のテストケースでは、騎士はまず全ての鍵を集め、そしてその鍵で全ての扉を開けます。

2つ目のテストケースでは、騎士の目の前に赤い扉がありますが、騎士はその扉用の鍵を持っていません。

3つ目のテストケースでは、それぞれの扉の前に鍵があるので、騎士は鍵を集めてすぐに使用することを3回行います。

4つ目のテストケースでは、騎士は青い扉を開けることができません。

B. Anti-Fibonacci Permutation / Антифибоначчиевы перестановки

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
長さ n の順列 p が、全ての i (3 \leq i \leq n) に対して条件 p_{i-2} + p_{i-1} \neq p_i が成り立つとき、anti-Fibonacciと呼ぶことにします。順列とは、1 から n までの各整数をちょうど1回ずつ持つ、長さ n の配列のことです。

与えられた数 n に対して、長さ n の相異なるanti-Fibonacci順列を出力して下さい。

入力

1行目には単一の整数 t (1 \leq t \leq 48) が与えられる、これはテストケースの個数である。

各テストケースの単一行には、単一の整数 n (3 \leq n \leq 50) が与えられる。

出力

各テストケースについて n 行出力せよ。各行には長さ n のanti-Fibonacci順列が含まれていなければならない。各テストケースにおいて、各順列を2回以上出力してはいけない。

答えが複数存在する場合、そのうちのいずれかを出力せよ。この問題の制約の下では，長さ n の相異なるanti-Fibonacci順列を得ることが常に可能であることは証明できる。

入出力例

2
4
3
4 1 3 2
1 2 4 3
3 4 1 2
2 4 1 3
3 2 1
1 3 2
3 1 2

C. Increase Subarray Sums / Увеличь суммы подотрезков

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
n 個の整数からなる配列 a_1,\,a_2,\,\dots,\,a_n が与えられます。また、整数値 x も与えられます。

f(k) を、次の操作を行った後の a の連続部分列の最大和とします: ちょうど k 個の異なる位置の要素に x を加える。空部分列も考慮し、その和は 0 です。

部分列は、増加した要素全てを含む必要はないことに注意してください。

0 から n までの全ての k について、f(k) の最大値を独立に計算してください。

入力

1行目には単一の整数 t (1 \leq t \leq 5000) が与えられる、これはテストケースの個数である。

テストケースの1行目には2個の整数 n,\,x (1 \leq n \leq 5000; 0 \leq x \leq 10^5) が与えられる、これらは配列の大きさと加算値である。

2行目には n 個の整数 a_1,\,a_2,\,\dots,\,a_n (-10^5 \leq a_i \leq 10^5) が与えられる。

全てのテストケースでの n の和は 5000 を超えない。

出力

各テストケースについて n+1 個の整数を出力せよ、それらはそれぞれ 0 から n までの全ての k についての f(k) の最大値である。

入出力例

3
4 2
4 1 3 2
3 5
-2 -7 -1
10 2
-6 -1 -2 4 -6 -1 -4 4 -5 -4
10 12 14 16 18
0 4 4 5
4 6 6 7 7 7 7 8 8 8 8

注記

1つ目のテストケースでは、どの要素に x を足すかは関係ありません。和が最大となる部分列は常に配列全体です。k 個の要素を x だけ増やすと、k \cdot x が和に足されます。

2つ目のテストケースでは、

  • k = 0 では、空部分列が最適である。
  • k = 1 では、位置 3 の要素を増やすのが最適である。最適和は部分列 [3,\,3]*1 の -1 + 5 = 4 となる。
  • k = 2 では、位置 3 と他の1つの位置の要素を増やすのが最適である。最適和は部分列 [3,\,3] の 4 のままである。
  • k = 3 では、全ての要素を増やさなければならない。最適和は部分列 [1,\,3] の (-2 + 5) + (-7 + 5) + (-1 + 5) = 5 となる。

D. Cross Coloring / Раскраска крестиками

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
n \times m のマス目(n 行 m 列)で表すことができる1枚のシートがあります。初期状態では全てのセルは白です。

このシートに対して q 回操作を行いました。そのうちの i 番目の操作は次のように表されます。

  • x_i y_i: 白でない k 色のうち1色を選び、行 x_1 全体と列 y_i 全体をその色で塗る。操作の前に着色されていたかどうかに関係なく、各セルに新しい色が適用される。

q 回の操作を全て適用した後のシートを彩色と呼びます。異なる色に着色されたセルが少なくとも一つ存在したとき、2つの彩色は異なるといいます。

彩色は何通り存在しますか? 数をmodulo 998\,244\,353 で出力して下さい。

入力

1行目には単一の整数 t (1 \leq t \leq 10^4) が与えられる、これはテストケースの個数である。

テストケースの1行目には4個の整数 n,\,m,\,k,\,q (1 \leq n,\,m,\,k,\,q \leq 2 \cdot 10^5) が与えられる、これらはシートの大きさ、白以外の色数、操作回数である。

続く q 行の i 行目には i 番目の操作についての記述が与えられる。2個の整数 x_i,\,y_i (1 \leq x_i \leq n; 1 \leq y_i \leq m) で、それぞれ操作を適応する行と列である。

全てのテストケースでの q の和は 2 \cdot 10^5 を超えない。

出力

各テストケースについて単一の整数を出力せよ、その数とは彩色数のmodulo 998\,244\,353 である。

入出力例

2
1 1 3 2
1 1
1 1
2 2 2 3
2 1
1 1
2 2
3
4

E. Expand the Path / Расширь маршрут

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
大きさ n \times n のグリッドが与えられます。行は上から順に 1 から n まで、列は左から順に 1 から n までの番号が振られています。

ロボットがセル (1,\,1) に配置されています。ロボットは次の2種類の移動を行うことができます。

  • D: 下に1セル移動
  • R: 右に1セル移動

ロボットはグリッドの外に出ることはできません。

一連の動き s が与えられます、これはロボットの初期経路です。この経路でロボットがグリッドの外に進むことはありません。

これに対して、任意回数修正を加えることができます(0個の場合も可)。1回の修正では、一連の中の動きの1つを複製することができます。即ち、DをDDに、RをRRに置き換えます。

そのセルを通り、グリッドの外に進むことのないような修正後の経路が存在するようなセルの個数を数えて下さい。

入力

1行目には単一の整数 t (1 \leq t \leq 10^4) が与えられる、これはテストケースの個数である。

各テストケースの1行目には単一の整数 n (2 \leq n \leq 10^8) が与えられる、これはグリッドの行や列の数である。

各テストケースの2行目には文字DとRのみから成る、空でない文字列s が与えられる、これは初期経路である。この経路でロボットがグリッドの外に進むことはない。

全てのテストケースでの文字列 s の長さの和は 2 \cdot 10^5 を超えない。

出力

各テストケースについて単一の整数を出力せよ、その数とは、そのセルを通り、グリッドの外に進むことのないような修正後の経路が存在するようなセルの個数である。

入出力例

3
4
RD
5
DRDRDRDR
3
D
13
9
3

注記

1つ目のテストケースでは、次のような修正経路を考えれば十分です。

  • RD\rightarrowRRD\rightarrowRRRD\rightarrowRRRDD\rightarrowRRRDDD: この経路ではセル (1,\,1), (1,\,2), (1,\,3), (1,\,4), (2,\,4), (3,\,4), (4,\,4) を訪れる
  • RD\rightarrowRRD\rightarrowRRRD\rightarrowRRDDD: この経路ではセル (1,\,1), (1,\,2), (1,\,3), (2,\,3), (3,\,3), (4,\,3) を訪れる
  • RD\rightarrowRDD\rightarrowRDDD: この経路ではセル (1,\,1), (1,\,2), (2,\,2), (3,\,2), (4,\,2) を訪れる

従って、1回以上の修正後の経路で訪れるセルは (1,\,1), (1,\,2), (1,\,3), (1,\,4), (2,\,2), (2,\,3), (2,\,4), (3,\,2), (3,\,3), (3,\,4), (4,\,1), (4,\,3), (4,\,4) です。

2つ目のテストケースでは、ロボットがグリッドの外に進まない修正経路はありません。そのため、訪れるセルは経路DRDRDRで訪れるもののみです。

3つ目のテストケースでは、1回以上の修正後の経路で訪れるセルは (1,\,1), (2,\,1), (3,\,1) です。

以下は、全てのテストケースでのセルです。
f:id:Flkanjin:20220223142014p:plain

F. Basis / Базис

テストごとの時間制限: 6秒
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力
整数配列 a に対して、その要素数を |a| と定義します。

2つの関数を導入します。

  • F(a,\,k)*2 は整数配列 a と正整数 k を受け取る関数で、この関数の計算結果は a の各要素をその要素のちょうど k 回のコピーで置き換えることによって得られる配列の最初の |a| 個の要素を含む配列である。
    例えば、F([2,\,2,\,1,\,3,\,5,\,6,\,8],\,2) は次のように計算する。まず、配列の各要素をその2回のコピーで置き換え、[2,\,2,\,2,\,2,\,1,\,1,\,3,\,3,\,5,\,5,\,6,\,6,\,8,\,8] を得る。そして、得られた配列の最初の 7 要素を取り出し、関数の計算結果は [2,\,2,\,2,\,2,\,1,\,1,\,3] となる。
  • G(a,\,x,\,y) は整数配列 a と異なる2個の正整数 x,\,y を受け取る関数である。この関数の計算結果は x に等しい全ての要素を y に置き換え、 y に等しい全ての要素を x に置き換えた配列 a である。
    例えば、G([1,\,1,\,2,\,3,\,5],\,3,\,1) = [3,\,3,\,2,\,1,\,5] である。

次のいずれかを満たす場合、配列 a は b の親であるといいます。

  • F(a,\,k) = b であるような正整数 k が存在する
  • G(a,\,x,\,y) = b であるような異なる2個の正整数 x,\,y が存在する

c_0 が a であり c_m が b であり、各 i \in [1,\,m] について c_{i-1} が c_i の親であるような有限配列 c_0,\,c_1,\,\dots,\,c_m (m \geq 0) が存在するとき、配列 a は配列 b の祖先といいます。

さて、問題そのものについてです。

2個の整数 n,\,k が与えられています。次の条件を満たす配列の列 s_1,\,s_2,\,\dots,\,s_m を作ることが目標です。

  • 各配列 s_i はちょうど n 個の要素を含み，全要素は 1 から k までの整数である
  • ちょうど n 個の 1 から k までの整数から成る配列 a それぞれに対して、この列には、 a の祖先であるような少なくとも1つの配列 s_i を含む

このような列に含まれる配列の最小個数を出力して下さい。

入力

唯一の行には2つの整数 n,\,k (1 \leq n,\,k \leq 2 \cdot 10^5) が与えられる。

出力

1つの整数を出力せよ、条件を満たす配列の最小個数である。答えが大きくなる可能性があるため、modulo 998244353 で出力せよ。

入出力例

3 2
2
4 10
12
13 37
27643508
1337 42
211887828
198756 123456
159489391
123456 198756
460526614

注記

1つ目の入出力例を分析しましょう。

1つ目の入出力例で考えられる答えの1つは、列 [[2,\,1,\,2],\,[1,\,2,\,2]] です。1 から 2 までの要素からなる大きさ 3 の配列はすべてこの列内に祖先を持ちます。

  • 配列 [1,\,1,\,1] の場合、祖先は [1,\,2,\,2] である: F([1,\,2,\,2],\,13) = [1,\,1,\,1]
  • 配列 [1,\,1,\,2] の場合、祖先は [1,\,2,\,2] である: F([1,\,2,\,2],\,2) = [1,\,1,\,2]
  • 配列 [1,\,2,\,1] の場合、祖先は [2,\,1,\,2] である: G([2,\,1,\,2],\,2,\,1) = [1,\,2,\,1]
  • 配列 [1,\,2,\,2] の場合、祖先は [1,\,2,\,2] である
  • 配列 [2,\,1,\,1] の場合、祖先は [1,\,2,\,2] である: G([1,\,2,\,2],\,1,\,2) = [2,\,1,\,1]
  • 配列 [2,\,1,\,2] の場合、祖先は [2,\,1,\,2] である
  • 配列 [2,\,2,\,1] の場合、祖先は [2,\,1,\,2] である: F([2,\,1,\,2],\,2) = [2,\,2,\,1]
  • 配列 [2,\,2,\,2] の場合、祖先は [1,\,2,\,2] である: G(F([1,\,2,\,2],\,4),\,1,\,2) = G([1,\,1,\,1],\,1,\,2) = [2,\,2,\,2]

*1:配列の添え字の範囲を表す

*2:ここでの k は入力の k とは別個である

Codeforces Round #772 (Div. 2)のきろく

Codeforces 競技プログラミング Codeforces Div. 2 参戦記

レート冷えてしまった... 問題文和訳はこちら

A. Min Or Sum / Минимальная OR сумма (500点)

どのように操作しても \displaystyle \operatorname*{OR}_{i=1}^{n} a_i は変化せず、和の値はbitORの値以上です。
1 \leq i < n について順に a_{i+1} \leftarrow a_i \operatorname{OR} a_{i+1} という操作を行うことで a_n = \displaystyle \operatorname*{OR}_{i=1}^{n} a_i とすることができ、また、これを用いて 1 \leq < n について a_i = 0 にすることができ、\displaystyle \sum_{i = 1}^{n} = \operatorname*{OR}_{i=1}^{n} a_i を実現することができます。
そのため、答えは \displaystyle \operatorname*{OR}_{i=1}^{n} a_i となります。

B. Avoid Local Maximums / Избегайте локальных максимумов (1000点)

a_i が極大要素であるとき、a_{i+1} を \displaystyle \max\{a_i,\,a_{i+2}\} (i = n-1 の時は a_i のみ)に置換することで最小回数を実現できます。

C. Differential Sorting / Дифференциальная сортировка (1500点)

時間内には通せなかった... 構築系は苦手だなぁ...
末尾の2要素は変えることができないので、a_{n-1} > a_n のときは達成不可能です。
a_n \geq 0 のときは 1 \leq i \leq n-2 の各 i に対して (x,\,y,\,z) = (i,\,n-1,\,n) の操作を行うことで達成することができます。
そうでない場合、初期状態で達成していない限り、a_i > a_{i+1} を満たす最も右の i について a_i \leq a_{i+1} にすることができにないため、達成不可能です。

D. Infinite Set / Бесконечный набор (2250点)

桁DPです。

{\mathrm{dp}}_{i} = (\text{二進数表記で \(i\) 桁であるような \(S\) の要素の個数})
としたとき {\mathrm{dp}}_0 = 0 で i > 1 について {\mathrm{dp}}_i に {\mathrm{dp}}_{i-2} + {\mathrm{dp}}_{i-1} を足すということを順に行うことで答えを求めることができます。
初期値としては a_1,\,a_2,\,\dots,\,a_n についてそれぞれ対応する {\mathrm{dp}}_i に 1 を加算していけばいいですが、a_j から a_k が作れる場合は、余計にカウントし、答えが大きくなってしまいますが、a_k についてはその処理を行うことはせずスキップすることで余計に数えてしまうことをなくすことができます。

E. Cars / Автомобили (2550点): 未提出

Hmm...

F. Closest Pair / Ближайшая пара (3000点): 未提出

分からないです。

結果、感想

f:id:Flkanjin:20220222214006p:plain
微減してしまいました... もっと精進します。

Codeforces Round #772 (Div. 2) 問題文和訳

Codeforces 競技プログラミング Codeforces 和訳 Codeforces Div. 2 和訳

A. Min Or Sum / Минимальная OR сумма (500点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
大きさ n の配列 a が与えられます。
この配列に対して次の操作を行うことができます。

  • 異なる2つの整数 i,\,j (1 \leq i \lt j \leq n) を選び、a_i を x に、a_j を y に置き換える。配列の破壊を行わないために、a_i | a_j = x | y を満たさなければなりません、ここで | はビットOR*1を表す。x と y は非負整数であることに注意せよ。

上記の操作を任意の回数行った後に得られる配列の要素の和の最小値を出力してください。

入力

各テストは複数のテストケースが含まれる。1行目にはテストケースの個数 t (1 \leq t \leq 1000) が与えられる。以下、テストケースの記述が続く。

各テストケースの1行目には整数 n (2 \leq n \leq 100) が与えられる、これは配列の大きさである。

各テストケースの2行目には n 個の整数 a_1,\,a_2,\,\dots,\,a_n (0 \leq a_i \lt 2^{30}) が与えられる。

出力

各テストケースについて、単一の値を出力せよ、その値とは達成できる配列の最小和である。

入出力例

4
3
1 3 2
5
1 2 4 8 16
2
6 6
3
3 5 6
3
31
6
7

注記

1つ目の入力例では、次のような操作で配列 [1,\,0,\,2] を得ることができます。

  1. i = 1, j = 2 と選び、a_1 = 1, a_2 = 2 とする、この操作は 1|3 = 1|2 であるため有効である。配列は [1,\,2,\,2] となる。
  2. i = 2, j = 3 と選び、a_2 = 0, a_3 = 2 とする、この操作は 2|2 = 0|2 であるため有効である。配列は [1,\,0,\,2] となる。

最小和が 1 + 0 + 2 = 3 であることは証明することができます。

2つ目の入力例では、操作は必要ありません。

B. Avoid Local Maximums / Избегайте локальных максимумов (1000点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
大きさ n の配列 a が与えられます。この配列の各要素は 1 から 10^9 までの整数です。

この配列に対して何回か操作を行うことができます。1回の操作では、配列の中の1つの要素を 1 から 10^9 までの任意の整数に置き換えることができます。

結果として得られる配列に極大要素が含まれないようにするため必要な操作の最小回数と、操作後の配列を出力してください。

要素 a_i はその近傍の両方よりも厳密に大きい(即ち、a_i \lt a_{i-1} かつ a_i \lt a_{i+1})時、極大要素であるといいます。a_1 と a_n は近傍要素がそれぞれ1つずつしかないため、極大要素となることはありません。

入力

各テストは複数のテストケースが含まれる。1行目には単一の整数 t (1 \leq t \leq 10000) が与えられる、これはテストケースの個数である。以下、t 個のテストケースが続く。

各テストケースの1行目には単一の整数 n (2 \leq n \leq 2 \cdot 10^5) が与えられる、これは配列の大きさである。

各テストケースの2行目には n 個の整数 a_1,\,a_2,\,\dots,\,a_n (1 \leq a_i \leq 10^9) が与えられる、これらは配列の要素である。

全てのテストケースでの nの和が 2 \cdot 10^5 を超えないことは保証されている。

出力

各テストケースについて、まず、単一の整数 m を単一行にで出力せよ、この数は必要な操作の最小回数である。次に n 個の整数から成る1行を出力せよ、この整数は操作の結果得られる配列である。この配列は、最初の配列とちょうど m 個の要素が異なっていなければならないことに注意せよ。

答えが複数ある場合は、そのうちのいずれかを出力せよ。

入出力例

5
3
2 1 2
4
1 2 3 1
5
1 2 1 2 1
9
1 2 1 3 2 3 1 2 1
9
2 1 3 1 3 1 3 1 3
0
2 1 2
1
1 3 3 1
1
1 2 2 2 1
2
1 2 3 3 2 3 3 2 1
2
2 1 3 3 3 1 1 1 3

注記

1つ目の入力例では、配列内に極大要素がないため、操作を行う必要はありません。

2つ目の入力例では、a_2 を 3 に変えることができ、そうすることで配列は極大要素を持たないようになります。

C. Differential Sorting / Дифференциальная сортировка (1500点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
大きさ n の配列 a が与えられます。

次の操作を n 回まで行うことができます: 3つのインデックス x,\,y,\,z (1 \leq x < y < z \leq n) を選び、a_x を a_y - a_z に置換する。この操作の後、|a_x| は 10^{18} 以下でなければなりません。

結果として得られる配列が非減少になるようにすることが目標です。解が複数存在する場合は、そのいずれをも出力することができます。実現不可能である場合は、そのことを知らせてください。

入力

各テストは複数のテストケースが含まれる。1行目には単一の整数 t (1 \leq t \leq 10000) が与えられる、これはテストケースの個数である。以下、t 個のテストケースが続く。

各テストケースの1行目には単一の整数 n (3 \leq n \leq 2 \cdot 10^5) が与えられる、これは配列の大きさである。

各テストケースの2行目には n 個の整数 a_1,\,a_2,\,\dots,\,a_n (-10^9 \leq a_i \leq 10^9) が与えられる、これらは配列の要素である。

全てのテストケースでの nの和が 2 \cdot 10^5 を超えないことは保証されている。

出力

各テストケースについて、解が存在しない場合、単一行に -1 を出力せよ。そうでない場合、1行目に単一の整数 m (0 \leq m \leq n) を出力せよ、この数は実行した操作の回数である。

その後、続く m 行の i 行目には3個の整数 x,\,y,\,z (1 \leq x < y < z \leq n) を出力せよ、これらは i 回目の操作についての説明である。

解が複数存在する場合は、どれを出力してもよい。このタスクでは、操作回数を最小化する必要はないことに注意せよ。

入出力例

3
5
5 -4 2 -1 2
3
4 3 2
3
-3 -2 -1
2
1 2 3
3 4 5
-1
0

注記

1つ目の入力例では、配列は次のようになります。

1回目の操作の後: [-6,\,-4,\,2,\,-1,\,2]

2回目の操作の後: [-6,\,-4,\,-3,\,-1,\,2]

2つ目の入力例では、どのような操作を行っても配列を昇順にすることは不可能です。

3つ目の入力例では、配列は既に昇順になっているため、操作を行う必要はありません。

D. Infinite Set / Бесконечный набор (2250点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
n 個の相異なる正整数から成る配列 a が与えられます。

以下の条件の少なくとも一つを満たす全ての整数 x を含む無限整数集合 S を考えます。

  1. ある 1 \leq i \leq n について x = a_i
  2. y \in S について x = 2y+1
  3. y \in S について x = 4y

例えば、a = [1,\,2] のとき、S 内の小さい方から 10 個の要素は \{1,\,2,\,3,\,4,\,5,\,7,\,8,\,9,\,11,\,12\} となります。

S の要素のうち 2^p よりも厳密に小さい要素の個数を求めて下さい。答えは大きくなる可能性があるため、modulo 10^9+7 で出力してください。

入力

1行目には2つの整数 n,\,p (1 \leq n,\,p \leq 2 \cdot 10^5) が与えられる。

2行目には n 個の整数 a_1,\,a_2,\,\dots,\,a_n (1 \leq a_i \leq 10^9) が与えられる。

a 内の全ての数が相異なることは保証される。

出力

単一の整数を出力せよ、その数とはS の要素のうち 2^p よりも厳密に小さい要素の個数である。modulo 10^9+7 で出力することに忘れないようにせよ。

入出力例

2 4
6 1
9
4 7
20 39 5 200
14
2 200000
48763 1000000000
448201910

注記

1つ目の入力例では、2^4 よりも小さい要素は \{1,\,3,\,4,\,6,\,7,\,9,\,12,\,13,\,15\} です。

2つ目の入力例では、2^7 よりも小さい要素は \{5,\,11,\,20,\,23,\,39,\,41,\,44,\,47,\,79,\,80,\,83,\,89,\,92,\,95\} です。

E. Cars / Автомобили (2550点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力
座標軸 OX 上に n 台の自動車があります。各自動車は最初は整数の点上に位置し、2台以上の自動車が同一点上に位置することはありません。また、各自動車は左右いずれかを向いており、どの瞬間においてもその方向に任意の一定の正の速度で動くことができます。

より形式的には、i 番目の車を1文字と1つの整数で表すことができます: 方向 ori_i と 位置 x_i です。ori_i=L である場合、x_i は時間に対して一定の割合で減少します。同様に ori_i=R である場合、x_i は時間に対して一定の割合で増加します。

2台の車が速度に関係なく決して同じ地点に着かない場合、無関係であるといいます。つまり、どの瞬間にも同じ座標を共有することはありません。

2台の車が速度に関係なく同じ地点に着く場合、運命的であるといいます。つまり、同じ座標を共有する瞬間があります。

残念なことに、車に関する情報はすべて失われてしまいましたが、m 個の関係は覚えています。関係には2種類あります。

1\ i\ j: i 台目と j 台目の自動車が無関係である。

2\ i\ j: i 台目と j 台目の自動車が運命的である。

この関係を満たす自動車の方向と位置を復元するか、それが不可能であることを報告してください。解が複数存在する場合、そのいずれをも出力してもいいです。

2台の車が同じ座標を共有している場合は交差となりますが、そのままそれぞれの方向への移動が継続されることに注意してください。

入力

1行目には2つの整数 n,\,m \biggl(2 \leq n \leq 2 \cdot 10^5; \displaystyle 1 \leq m \leq \min\left\{2 \cdot 10^5, \frac{n(n-1)}{2}\right\} \biggr) が与えられる、それぞれ自動車の台数と制限の個数である。

次の m 行のそれぞれには3個の整数 type,\,i,\,j (1 \leq type \leq 2; 1 \leq i,\,j \leq n; i \neq j) が与えられる。

type = 1 の場合、i 台目と j 台目の自動車は無関係である。そうでないとき、i 台目と j 台目の自動車は運命的である。

自動車の各ペアについて、その間の関係は最大でも 1 つであることは保証される。

出力

1行目には、関係を満たす車の方向と位置を復元できるかどうか、"YES"または"NO"のいずれかを出力せよ(大文字小文字はいずれの場合でも可)。

答えが"YES"である場合、それぞれの行が1文字と1つの整数を含む n 行出力せよ。1文字と1つの整数とは ori_i,\,x_i (ori_i \in \{L,\,R\}; -10^9 \leq x_i \leq 10^9) であり、i 台目の自動車の情報を表す。

方向が左の場合は ori_i = L で、そうでない場合 ori_i = R とする。

x_i は i 台目の自動車の位置である。x_i は全て異なることに注意せよ。

解が存在する場合、x_i の制約を満たす解が存在することは証明することができる。

入出力例

4 4
1 1 2
1 2 3
2 3 4
2 4 1
YES
R 0
L -3
R 5
L 6
3 3
1 1 2
1 2 3
1 1 3
NO

F. Closest Pair / Ближайшая пара (3000点)

テストごとの時間制限: 3秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
OX 軸上に重み付きの点が n 点あります。i 番目の点の座標と重みはそれぞれ x_i と w_i です。全ての点は、座標は相異なり、正の重みを持ちます。また、任意の 1 \leq i < n について x_i < x_{i+1} が成り立ちます。

i 番目の点と j 番目の点の重み付き距離は |x_i - x_j| \cdot (w_i + w_j) と定義されます、ここで |val| は val の絶対値を表します。

q 個のクエリに答える必要があり、その i 番目のクエリは次のようなものです: 部分列 [l_i,\,r_i] 内の相異なる全ての点の組の間での最小の重み付き距離を求めよ。

入力

1行目には2個の整数 n,\,q (2 \leq n \leq 3 \cdot 10^5; 1 \leq q \leq 3 \cdot 10^5) が与えられる、これらは点とクエリの個数である。

n 行が続き、その i 行目には2個の整数 x_i,\,w_i (-10^9 \leq x_i \leq 10^9; 1 \leq w_i \leq 10^9) が与えられる、これらは i 番目の点の座標と重みである。

点は x の昇順に与えられることは保証されている。

その後、q 行が続き、その i 行目には2個の整数 l_i,\,r_i (-1 \leq l_i < r_i \leq n) が与えられる、これらは i 番目のクエリの部分列である。

出力

各クエリについて1個の整数を出力せよ、その数とは与えられた部分列内の異なる全ての点の組の間での最小の重み付き距離である。

入出力例

5 5
-2 2
0 10
1 1
9 2
12 7
1 3
2 3
1 5
3 5
2 4
9
11
9
24
11

注記

1つ目のクエリについて、最小重み付き距離は点 1 と点 3 の間のもので、|x_1 - x_3| \cdot (w_1 + w_3) = |-2 - 1| \cdot (2 + 1) = 9 となります。

2つ目のクエリについて、最小重み付き距離は点 2 と点 3 の間のもので、|x_2 - x_3| \cdot (w_2 + w_3) = |0 - 1| \cdot (10 + 1) = 11 となります。

4つ目のクエリについて、最小重み付き距離は点 3 と点 4 の間のもので、|x_3 - x_4| \cdot (w_3 + w_4) = |1 - 9| \cdot (1 + 2) = 24 となります。

*1:原文では英語、ロシア語のWikipediaへのリンク

AtCoder Beginner Contest 240のきろく

AtCoder 競技プログラミング AtCoder Beginner Contest 参戦記

AtCoder Beginner Contest 240に参加で、青に復帰!!

A - Edge Checker (100点)

隣同士の点の番号の差は 1 か 9 なので、それをif文で条件分岐します。

B - Count Distinct Integers (200点)

色々解法がありますが、std::setに突っ込んで解きました。

C - Jumping Takahashi (300点)

DPです。

{\mathrm{dp}}_{i,j} = (\text{\(i\) 回のジャンプをした後に座標 \(j\) の位置にいるようにできるか})
としたとき、初期状態
{\mathrm{dp}}_{0,j}=\left\{ \begin{array}{ll} \mathrm{True} & (j = 0)\\ \mathrm{False} & (j \neq 0) \end{array} \right.
で、 0 \lt i \leq N について
{\mathrm{dp}}_{i,j}={\mathrm{dp}}_{i-1,j-a_i} \lor {\mathrm{dp}}_{i-1,j-b_i}
という遷移で答えを求めることができます。実際には貰うDPではなく配るDPで実装しました。
また、公式解説にもあるようにstd::bitsetを用いることで若干の高速化を実現することができます。

D - Strange Balls (400点)

問題文の通りのことをそのまま実装すると O(N^2) となりますが、C++ではそれでもギリギリ通るそうですが、私は想定解の方法で通しました。
同じ整数のボールについて (整数,\,個数) の組で表し、これをスタックで管理することで計算量を O(N) に落とすことができます。
C++ではスタックのためのデータ構造としてstd::stackがありますが、std::vectorやstd::dequeを使うことが殆どです。

E - Ranges on Tree (500点)

与えられた木の葉を v_1,\,v_2 ,\dots,\,v_n とすると、任意の異なる2つの葉 v_i,\,v_j について S_{v_i} \cap S_{v_j} = \emptyset であるため、それに対応する集合 [L_{v_i},\,R_{v_i}], [L_{v_j},\,R_{v_j}] が互いに素でなければならず、\displaystyle\max\left\{\max_i L_i,\,\max_j R_i\right\} \geq n であることが分かります。

一方で、各葉に対応する集合を上手く構築し、その他の頂点についてはその子頂点に対応する集合の和集合にすることで \displaystyle\max\left\{\max_i L_i,\,\max_j R_i\right\} = n を達成することができ、解のうちの1つとなります。それはDFSでの到達順に葉に1から順に番号を付け、その番号を対応する集合の唯一の要素とすることです。これで解を構築することができました。

F - Sum Sum Max (500点)

C で同じ値が続く区間ごとに考えます。
\displaystyle \sum_{i = 1}^{k} y_k = Y とします。

A_{Y + j} = \displaystyle A_{Y} +j \sum_{i = 1}^{k} x_i y_i + y_{k+1} \sum_{i = 1}^{j} i = A_{Y} +j \sum_{i = 1}^{k} x_i y_i + \frac{j(j+1)}{2} x_{k+1}
が成り立ちます。
\displaystyle \sum_{i = 1}^{k} x_i y_i \leq 0 または x_{k+1} \geq 0 のときはその区間について単調であるか、下に凸であるため、最大値をとる可能性があるのは両端のときだけであるが、そうでないときは、上に凸であるため、途中で最大値をとる可能性があります。そのとき最大値をとるのは j =\displaystyle\left\lfloor -\frac{ \sum_{i = 1}^{k} x_i y_i}{x_{k+1}}\right\rfloor のときであるため、それを個別に計算すればいいです。

G - Teleporting Takahashi (600点、実行時間制限: 3 sec): 未提出

ちょっと思いつきませんでした...

Ex - Sequence of Substrings (600点、実行時間制限: 5 sec): 未提出

うむ、分からん

結果、感想

f:id:Flkanjin:20220222164317p:plain
久しぶりの黄パフォで青に復帰することができました。ちゃんとこのままレートを増やしていきたいですね。

デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239）のきろく

AtCoder 競技プログラミング AtCoder Beginner Contest 参戦記

デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239）参加で久しぶりの更新。

A - Horizon (100点)

素直に \sqrt{H(12800000+H)} を出力すればいいですが、int型でルートの中身を計算するとオーバーフローするのでlong long型や浮動小数型を用いましょう。

B - Integer Division (200点)

C++では整数商X / 10は"0方向への丸め"であるため、X < 0 かつ X が 10 で割り切れないときに 1 だけ大きくなってしまうので、 それを条件分岐させればいいです。
また、Pythonでの整数商X // 10は"切り捨て"即ち"負の無限大への丸め"であるため問題文のものに合致するためこちらで実装すれば条件分岐は必要ありません。

C - Knight Fork (300点)

格子点 (x,\,y) から距離が \sqrt{5} の格子点は (x \pm 2,\,y \pm 1), (x \pm 1,\,y \pm 2) (複号任意) の8点であるため、(x_1,\,y_1), (x_2,\,y_2) のそれぞれからの距離が \sqrt{5} である点の集合の両者に共通する要素があるか、がこの問題の答えとなります。

D - Prime Sum Game (400点)

A \leq x \leq B であり、x + C から x + D までの全ての整数が合成数であるような整数 x が存在するとき、そのような x を高橋君が選べばいいので、このとき高橋君の勝ちとなります。そうでないとき、どんな数を高橋君が選んでも青木君は2数の和を素数にできるので、青木君が勝ちます。
予め B + D までの数についてΕρατοσθένηςの篩をしておくといいでしょう。

E - Subtree K-th Max (500点)

全ての頂点についてその部分木についての全ての整数を調べるのは O(N^2) となり、TLEが発生します。しかし、各頂点について大きい方から最大でも \displaystyle\max_i K_i 個の数さえ分かればよく、K_i \leq 20 であるため、DFSで十分高速に求めることができます。ある頂点について、その子頂点についての数列と自分自身の整数を併せて大きい方から最大 \displaystyle\max_i K_i 個をその頂点での数列となります。
クエリ回答では該当する頂点に対応する数列の K_i 項目を出力すればいいです。

F - Construct Highway (500点)

あともう少しで通せたのに...タイプミスほんまにどうしたら直るんでしょうね...

最終的に木にしたいので \displaystyle \sum_{i=1}^{N} D_i = 2N-2 であることが必要です。また、初期状態で、閉路があってはいけません(Union-FIndで検出)。また、すでに次数が D_iよりも大きな頂点が存在してはいけません。
そののち、グラフの連続成分ごとに次数と D_i の差の合計(ここで \delta とする)を出します。元のグラフでの連結成分を頂点に、次数を対応する \delta とする木を構築することができれば、ここで作った木の各辺に対応して元のグラフに辺を追加していくことでこの問題を解くことができます。

後半の木の構築については \delta が一番大きな連結成分と一番小さい連結成分を結んで併合するということを繰り返します。このとき、併合でできた連結成分の \delta が 0 になったり、連結成分が1個だけになったりしたのが最後以外の瞬間であった場合、木を構築することができず、元の問題も解なしになります。そうでない場合、最後まで操作を行うことで木になります。

G - Builder Takahashi (600点): 未提出

最小カットを勉強したらいけそう

Ex - Dice Product 2 (600点): 未提出

やっぱり確率とか期待値とかは苦手だなぁ...

結果、感想

f:id:Flkanjin:20220221200509p:plain
レートが上がったのはいいのですが、F問題を通せたら青に復帰できたのかなと思うともっと早く組めてたらなぁと...