Time Limit: 2 sec / Memory Limit: 2048 MiB
配点 : 100 点
くろうさ「今年は 3 択クイズ！」
しろうさ「好きなサイズでお絵かきできる！！」
しろうさ「……正解いくつあるの？」
くろうさ「1 個以上」
問題文
k = 2, 3, 4 のうち 1 つを選び，以下の問に答えよ．
横の長さと縦の長さの比が 1 : \left(1 + \sqrt[k]{2}\right) または \left(1 + \sqrt[k]{2}\right) : 1 であるような長方形を有限個，隙間や重なりなく並べて，正方形を作れ．より詳しい制限は「出力」のセクションを参照せよ．
入力
入力は空である．
出力
以下の形式で出力せよ．
k r n a_1 b_1 c_1 d_1 a_2 b_2 c_2 d_2 \vdots a_n b_n c_n d_n
- k はあなたが選んだ 2, 3, 4 のいずれかの値である．
- 実数 r の形式は後述される．作った正方形が直交座標平面上の (0, 0), (r, 0), (r, r), (0, r) を 4 頂点とすることを表す．
- n は長方形の個数を表す．1 \le n \le 10^5 を満たさなければならない．
- 実数 a_i, b_i, c_i, d_i (1 \le i \le n) の形式は後述される．i 個目の長方形が (a_i, c_i), (b_i, c_i), (b_i, d_i), (a_i, d_i) を 4 頂点とすることを表す．
- r および a_i, b_i, c_i, d_i (1 \le i \le n) のそれぞれについて，k 個の整数 p_0, p_1, \ldots, p_{k-1} を空白区切りで出力せよ．これは値が \sum_{j=0}^{k-1} p_j \left(\sqrt[k]{2}\right)^j であることを表す．-10^9 \le p_j \le 10^9 を満たさなければならない．
- r > 0 を満たさなければならない．
- 各 1 \le i \le n に対し，0 \le a_i < b_i \le r かつ 0 \le c_i < d_i \le r を満たさなければならない．
- 各 1 \le i \le n に対し，\dfrac{d_i-c_i}{b_i-a_i} = 1 + \sqrt[k]{2} または \dfrac{b_i-a_i}{d_i-c_i} = 1 + \sqrt[k]{2} を満たさなければならない．
- 正方形の内部および境界のすべての点は n 個の長方形のいずれかの内部および境界に含まれていなければならず，n 個の長方形のどの 2 つの内部も正の面積の共通部分を持ってはならない．
入力例 1
出力例 1
4 2 1 1 2 3 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 2 0 0 0 2 1 2 1 1 0 0 0 1 1 1 0 0 0 1 0 0 -1 1 2 3 0 0 0 7 -1 -1 2
これは最後の条件以外を満たす出力である (よって，不正解と判定される)．この例では長方形は以下の図のように配置されている (座標は左下隅が (0, 0)，右下隅が (r, 0) である)．
出力例
Time Limit: 2 sec / Memory Limit: 2048 MiB
配点 : 100 点
ハムスター「3 次元のランダム回転を説明するために問題文が長くなってしまいました．2 次元なら説明が簡単なのに……．直感的なランダム回転なのでどうか恐れずにお解きください」
問題文
整数 A,B,C,D,E,F,G,H,I が与えられる．3 次元直交座標空間中の平行六面体 (の内部・境界の点集合) P は以下の 8 点を頂点とする：
- (0, 0, 0)
- (A, B, C)
- (D, E, F)
- (A+D, B+E, C+F)
- (G, H, I)
- (A+G, B+H, C+I)
- (D+G, E+H, F+I)
- (A+D+G, B+E+H, C+F+I)
P を一様ランダムに回転させたときの高さの期待値を求めよ．
一様ランダムに回転させるとは，以下の手順による：
- 単位球面上の点 u を通常の面積に従って一様に選ぶ．
- v = (1,0,0) \times u とおく (クロス積)．v = (0,0,0) となる確率は 0 なので，以下そのような場合を無視する．
- 原点と v を結ぶ直線を回転軸として，点 (1,0,0) を u へ移動させる回転を行う．
- 原点と u を結ぶ直線を回転軸として，[0, 2\pi) から一様に選んだ角度ぶん回転させる．
点集合 Q の高さとは，Z = \{z \mid \exists x, \exists y,\, (x,y,z) \in Q\} とおいたときの \max(Z) - \min(Z) と定義する．
制約
- -10^3 \le A,B,C,D,E,F,G,H,I \le 10^3．
- \det \begin{bmatrix} A&B&C \\ D&E&F \\ G&H&I \end{bmatrix} \ne 0．
入力
入力は以下の形式で標準入力から与えられる．
A B C D E F G H I
出力
高さの期待値を小数として出力せよ．正しい値に対する絶対誤差または相対誤差が 10^{−9} 以下であれば許容される．
入力例 1
1 0 0 0 1 0 0 0 1
出力例 1
1.500000000000000000
各辺の長さが 1 の立方体を一様ランダムに回転させると，高さの期待値は 1.5 となる．
Time Limit: 4 sec / Memory Limit: 2048 MiB
配点 : 100 点
かに (N-1)「かに (N-2)「……「かに 1「かに 0「a_0」」」……」」
問題文
N を正整数とする．(0, 1, \ldots, 2N) の並べ替え (a_0, a_1, \ldots, a_{2N}) であって，すべての i = 0, 1, \ldots, N-1 に対し a_{2i+1} < a_{2i+2} を満たすもの全体の集合を A とする．
a = (a_0, a_1, \ldots, a_{2N}) \in A に対し，f(a) を以下のように定める：
- b_0 = a_0 とおく．
- i = 0, 1, \ldots, N-1 に対し，b_{i+1} = \min\{\max\{b_i, a_{2i+1}\}, a_{2i+2}\} とおく．
- f(a) = b_N と定める．
N および，Q 個の整数 Z_1, Z_2, \ldots, Z_Q が与えられる．各 j = 1, 2, \ldots, Q に対し，f(a) = Z_j となる a \in A の個数を 998244353 で割った余りを求めよ．
制約
- 1 \le N \le 10^7．
- 1 \le Q \le 250\,000．
- 0 \le Z_1 < Z_2 < \cdots < Z_Q \le 2N．
入力
入力は以下の形式で標準入力から与えられる．
N Q Z_1 Z_2 \cdots Z_Q
出力
j = 1, 2, \ldots, Q の順に，f(a) = Z_j となる a \in A の個数を 998244353 で割った余りを，空白区切りで出力せよ．
入力例 1
2 5 0 1 2 3 4
出力例 1
0 3 24 3 0
- a = (2, 3, 4, 0, 1), (3, 2, 4, 0, 1), (4, 2, 3, 0, 1) のとき f(a) = 1 である．
- a = (0, 1, 2, 3, 4), (1, 0, 2, 3, 4), (2, 0, 1, 3, 4) のとき f(a) = 3 である．
- その他の a \in A に対しては f(a) = 2 である．
入力例 2
3 7 0 1 2 3 4 5 6
出力例 2
0 30 96 378 96 30 0
入力例 3
4 9 0 1 2 3 4 5 6 7 8
出力例 3
0 630 1800 3870 10080 3870 1800 630 0
入力例 4
7 6 1 2 3 5 8 13
出力例 4
97297200 239500800 441579600 78828847 496821247 97297200
Time Limit: 2 sec / Memory Limit: 2048 MiB
配点 : 100 点
この問題の存在自体が，Codeforces Round 884 のとある面白い問題に関する何らかのネタバレになってしまうかもしれません．申し訳ありません．
問題文
正整数 M が与えられる．以下の条件をすべて満たす辺重み付き無向木が存在するか判定し，存在する場合は 1 つ作れ．
- 頂点数 n は 2 \le n \le 10^3 を満たす．
- 頂点集合は \{1, 2, \ldots, n\} である．
- 各辺の重みは 1 以上 M 未満の整数である．
- 各 u = 1, 2, \ldots, n-1 に対し，頂点 u と頂点 u+1 の距離 (それらを結ぶ唯一の単純パスに含まれる辺の重みの和) は M の倍数である．
制約
- 2 \le M \le 10^9．
部分点
- M \le 10^2 を満たすデータセットに正解した場合は，32 点が与えられる．
- 追加制約のないデータセットに正解した場合は，上記とは別に 68 点が与えられる．
入力
入力は以下の形式で標準入力から与えられる．
M
出力
条件を満たす辺重み付き無向木が存在する場合，そのようなもののうち 1 つを以下の形式で出力せよ：
n
a_1 b_1 c_1
a_2 b_2 c_2
\vdots
a_{n-1} b_{n-1} c_{n-1}
n は頂点数である (2 \le n \le 10^3)．i 番目 (1 \le i \le n-1) の辺は頂点 a_i と頂点 b_i を結び (1 \le a_i, b_i \le n)，重みは c_i である (1 \le c_i < M)．
条件を満たす辺重み付き無向木が存在しない場合，代わりに -1 と出力せよ．
入力例 1
2
出力例 1
-1
Time Limit: 4 sec / Memory Limit: 2048 MiB
配点 : 100 点
うなぎ「\pi が登場する問題も恒例になってきました．本問では e は 2.718\cdots ではないです」
問題文
\gcd(B, C) = \gcd(C, A) = \gcd(A, B) = 1 を満たす正整数 A, B, C が与えられる．
正整数 n が良い正整数であるとは，ある正整数 x, y, z が存在して n = x^{BC} y^{CA} z^{AB} となることと定める．良い正整数は無限個存在することが証明できる．すべての良い正整数を昇順に並べたものを N_1 < N_2 < \cdots とする．このとき，S = \displaystyle\sum_{k\ge1} \dfrac{1}{N_k^2} を以下の形式で求めよ．
この無限和は収束し，円周率 \pi と整数 p, q, e (q > 0,\, \gcd(p, q) = 1) を用いて S = \dfrac{p}{q} \pi^e と一意に書けることが証明できる．p - q r が 998244353 で割り切れ 0 \le r < 998244353 である整数 r (この問題の制約によって一意に定まることが証明できる) と，e を出力せよ．
制約
- 1 \le A, B, C \le 250．
- \gcd(B, C) = \gcd(C, A) = \gcd(A, B) = 1．
部分点
- A, B, C \le 10 を満たすデータセットに正解した場合は，32 点が与えられる．
- 追加制約のないデータセットに正解した場合は，上記とは別に 68 点が与えられる．
入力
入力は以下の形式で標準入力から与えられる．
A B C
出力
r, e を空白区切りで出力せよ．
入力例 1
1 1 1
出力例 1
166374059 2
この例では，すべての正整数が良い正整数となる．N_k = k であり，S = \dfrac{1}{6} \pi^2 である．
入力例 2
3 1 4
出力例 2
504856097 -10
(N_1, N_2, \ldots) = (1, 8, 16, 27, 64, 81, 125, 128, 216, 256, 343, 432, 512, 625, 648, 729, 1000, \ldots) である．
Time Limit: 2 sec / Memory Limit: 2048 MiB
配点 : 100 点
くろうさ「間違い探しもあるよっ！」
問題文
文字列 t が文字列 s の border であるとは，t が s の prefix かつ suffix であることとする．長さ n の文字列 s と整数 1 \le k \le n に対し，f(s, k) を，s の長さ k の prefix の border であって，長さが k 未満のもののうち最長のものの長さとする (空文字列は任意の文字列の border であるから，これは well-defined である)．また，f(s, 0) = -1 と定める．
しろうさは，長さ n の文字列 s が与えられたとき f(s, 0), f(s, 1), \ldots, f(s, n) を計算するアルゴリズムを実装しようとしたが，間違えてしまった．以下の C++ コード片で表される関数 Xmas に s を引数として与えたときに計算される整数列 g を (g(s, 0), g(s, 1), \ldots, g(s, n)) とする．
#include <string>
#include <vector>
std::vector<int> Xmas(std::string s) {
int n = s.size();
std::vector<int> g(n + 1);
int j = g[0] = -1;
for (int i = 0; i < n; ++i) {
for (; j >= 0 && s[j] == s[i]; j = g[j]) {}
g[i + 1] = ++j;
}
return g;
}
正整数 A, B が与えられる．A 個の文字 a と B 個の文字 b からなる長さ A + B の文字列 s に対する，
\displaystyle\sum_{k=0}^{A+B} \bigl\lvert f(s, k) - g(s, k) \bigr\rvert の最小値，および最小値を達成する s を 1 つ求めよ．
制約
- 1 \le A, B \le 10^5．
入力
入力は以下の形式で標準入力から与えられる．
A B
出力
1 行目に，\displaystyle\sum_{k=0}^{A+B} \bigl\lvert f(s, k) - g(s, k) \bigr\rvert の最小値を出力せよ．
2 行目に，最小値を達成する s のうち 1 つを出力せよ．
入力例 1
2 1
出力例 1
2 aba
f(\mathtt{aba}, 0) = -1,\, f(\mathtt{aba}, 1) = 0,\, f(\mathtt{aba}, 2) = 0,\, f(\mathtt{aba}, 3) = 1 である．
g(\mathtt{aba}, 0) = -1,\, g(\mathtt{aba}, 1) = 0,\, g(\mathtt{aba}, 2) = 1,\, g(\mathtt{aba}, 3) = 2 である．
Time Limit: 2 sec / Memory Limit: 2048 MiB
配点 : 100 点
カッコウ「対称群のかけ算表が与えられるので順列に対応させてください」
カッコウ「添え字が小さくて読み書きしにくいので括弧を使わせてください」
問題文
N を正整数とする．(1, 2, \ldots, N) の順列全体を \mathfrak{S}_N と書く．f \in \mathfrak{S}_N は列 (f(1), f(2), \ldots, f(N)) と同一視する．f, g \in \mathfrak{S}_N に対し，f \circ g \in \mathfrak{S}_N を，k = 1, 2, \ldots, N に対し (f \circ g)(k) = f(g(k)) として定める．また，\mathfrak{S}_N のすべての元を辞書順に並べたものを P(1) < P(2) < \cdots < P(N!) とする．
(N!)^2 個の整数 A(i, j) (1 \le i, j \le N!) が与えられる．(1, 2, \ldots, N!) の順列 q = (q(1), q(2), \ldots, q(N!)) であって，すべての 1 \le i, j \le N! に対し P(q(i)) \circ P(q(j)) = P(q(A(i, j))) を満たすものをすべて求め，辞書順に出力せよ．
なお，条件を満たす q が存在することが制約によって保証されている．
制約
- 1 \le N \le 6．
- 1 \le A(i, j) \le N! (1 \le i, j \le N!)．
- 問題文の条件を満たす q が存在する．
部分点
- N = 1, 2, 3, 4, 5, 6 を満たすデータセットに正解した場合は，それぞれ 1, 2, 4, 8, 16, 69 点が与えられる．
入力
入力は以下の形式で標準入力から与えられる．
N A(1, 1) A(1, 2) \cdots A(1, N!) A(2, 1) A(2, 2) \cdots A(2, N!) \vdots A(N!, 1) A(N!, 2) \cdots A(N!, N!)
出力
1 行目に，条件を満たす q の個数を出力せよ．
以降，条件を満たす q を辞書順に 1 行ずつ，それぞれ q(1), q(2), \ldots, q(N!) をこの順に空白区切りで出力せよ．
入力例 1
3 6 4 5 2 3 1 5 6 4 3 1 2 4 5 6 1 2 3 3 1 2 5 6 4 2 3 1 6 4 5 1 2 3 4 5 6
出力例 1
6 2 3 6 5 4 1 2 6 3 4 5 1 3 2 6 4 5 1 3 6 2 5 4 1 6 2 3 5 4 1 6 3 2 4 5 1
\mathfrak{S}_3 の元は以下の 6 個である：
- P(1) = (1, 2, 3)
- P(2) = (1, 3, 2)
- P(3) = (2, 1, 3)
- P(4) = (2, 3, 1)
- P(5) = (3, 1, 2)
- P(6) = (3, 2, 1)
例えば q = (3, 2, 6, 4, 5, 1) のとき，
- P(q(1)) = (2, 1, 3)
- P(q(2)) = (1, 3, 2)
- P(q(3)) = (3, 2, 1)
- P(q(4)) = (2, 3, 1)
- P(q(5)) = (3, 1, 2)
- P(q(6)) = (1, 2, 3)
となる． P(q(2)) \circ P(q(3)) = P(q(4)) = P(q(A(2, 3))) などが成り立つことが確認できる．
Time Limit: 4 sec / Memory Limit: 2048 MiB
配点 : 100 点
We did not prove that our solutions work for (1 - \varepsilon) of all possible cases within the constraints for reasonably small \varepsilon. Our sincerest apologies. We solemnly affirm that the actual tests have been generated randomly as described in the problem statement, without any intention to favor our solutions. We wish you a Merry Christmas so that you can safely ignore rare cases which might cause trouble in your solution.
問題文
正整数 N および 16 個の整数 W_{i,j} (0 \le i,j \le 3) が与えられる．ここで，W_{0,0}=0 が保証されている．
うさぎが今平面上の座標 (0,0) に立っており，これから以下の操作を好きな回数行う．
- 現在立っている座標を (x,y) とする．整数 i,j (0 \le i,j \le 3) を選び，座標 (x+i,y+j) にジャンプして移動する．このとき，x+i \geq y+j を満たす必要がある．この操作の重みは W_{i,j} である．
操作列の重みを，その中で行った操作の重みの総積と定義する．
各 k=1,2,\ldots,N に対し次の問題を解け．
- うさぎが最終的に座標 (k,k) に至るすべての操作列の重みの和を 998244353 で割った余りを求めよ．
なお，この問題のテストケースについて以下の情報が開示される．
- サンプルを除くすべてのテストケースについて，W_{i,j} の値は制約の範囲内で一様ランダムに選択されている．
- サンプルを除くテストケースの総数は 10 である．
制約
- 2 \le N \le 250\,000．
- 0 \le W_{i,j} < 998244353 (0 \le i,j \le 3)．
- W_{0,0}=0．
入力
入力は以下の形式で標準入力から与えられる．
N
W_{0,0} W_{0,1} W_{0,2} W_{0,3}
W_{1,0} W_{1,1} W_{1,2} W_{1,3}
W_{2,0} W_{2,1} W_{2,2} W_{2,3}
W_{3,0} W_{3,1} W_{3,2} W_{3,3}
出力
各 k=1,2,\ldots,N に対する答えをこの順に空白区切りで出力せよ．
入力例 1
10 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0
出力例 1
1 2 5 14 42 132 429 1430 4862 16796
入力例 2
20 0 130171465 825060067 310308502 32807742 472394518 556273189 402133431 18860036 731819479 614014131 516327409 540765157 764797868 805340356 885719657
出力例 2
220800069 663178740 402492745 787371697 340681055 764687638 248275291 239071271 579317784 142439206 202142764 449124008 17082226 208225793 292943419 63532736 780653882 855023292 155627784 988995756