AtCoder Beginner Contest 261のきろく
久しぶりの参加録。AtCoder Beginner Contest 261に参加。調子が戻ってきたかな?
- A - Intersection (100点)
- B - Tournament Result (200点)
- C - NewFolder(1) (300点)
- D - Flipping and Bonus (400点)
- E - Many Operations (500点)
- F - Sorting Color Balls (500点、実行時間制限: 3 sec)
- G - Replace (600点): 未提出
- Ex - Game on Graph (600点): 未提出
- 結果、感想
A - Intersection (100点)
区間 が共通部分を持つとき、その共通部分の左端は で右端は となります。共通部分を持たないときはその左端と右端が入れ替わる、即ち、 となります。そのため出力すべき答えは となります。
C - NewFolder(1) (300点)
各文字列 に対して毎回 から まで一致するかを調べると文字列の長さを として となってTLEします。
map
やunordered_map
を用いることで や で計算可能で、 より十分高速です。
D - Flipping and Bonus (400点)
DはDPのD。
とします。今回は貰うDPでの記述が難しいので配るDPで書きます。初期値をとし、 に対して について のとき遷移を行います。ここでの は連続ボーナスで、とします。
出力する答えは です。
また、上の のところを など十分に小さい値にすれば場合分けが不要になります。
E - Many Operations (500点)
毎回愚直に操作 を行っていると操作回数が全体で となるので計算量 でTLEとなります。
各操作はbit演算であるため、bit毎に独立であり、2進数表記で下位から 桁目が であったときに操作 を施した結果 は初期値を として として計算可能です。よって 回目では操作前の値 に対して が答えとなり、 を に置き換えて 回目の操作につなげます。
また、 は に、 は に操作 を行ったときの値であるため、bit毎に考えずに と計算することができます。
計算量は としてbit毎に求めるのが 、後者が となります。
F - Sorting Color Balls (500点、実行時間制限: 3 sec)
初期状態で で であるような の組はソートの途中で入れ替えなければならず、その他の の組は入れ替える必要がありません。同色の球は入れ替えてもコストがかからないため、求める答えは となります。
転倒数は であるため、セグ木やBITなどで計算することができます。しかし、各色についてもセグ木やBITを作ると全体で 個の要素となるので時間計算量、空間計算量ともにオーバーします。
各色についてのセグ木やBITについては を座圧してやることで必要な要素数を全体で にしてやることができ、空間計算量 、時間計算量 でACすることができます。
G - Replace (600点): 未提出
赤diff... うん、分からん。
Ex - Game on Graph (600点): 未提出
やっぱりゲーム問題は難しい。
結果、感想
6完でレート1700目前!!
ただ、F問題で解法が思いついてから、正しいかどうか迷って実装着手まで時間がかかっていて、そうでなければ黄Perf行けてたかもしれないと思うと、もうちょっと精進しなければなと思いました。
CodeTON Round 1 (Div. 1 + Div. 2, Rated, Prizes!) 問題文和訳
- A. Good Pairs / Хорошие пары (500点)
- B. Subtract Operation / Операция вычитания (1000点)
- C. Make Equal With Mod / Сделай равным по модулю (1500点)
- D. K-good / K-хорошие (2000点)
- E. Equal Tree Sums / Одинаковые суммы деревьев (2500点)
- F. Parametric MST / Параметрическое MST (3000点)
- G. Cycle Palindrome / Циклические палиндромы (3250点)
- H. Equal LCM Subsets / Одинаковые НОК подмножеств (3750点)
- I. Neighbour Ordering / Упорядочивание соседей (4500点)
A. Good Pairs / Хорошие пары (500点)
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
良い組を求めて下さい。 と は等しくてもよいことに注意してください。
入力
入力は複数のテストケースから成る。1行目には単一の整数 が与えられる、これはテストケースの個数である。以下、テストケースの記述が続く。
各テストケースの1行目には1個の整数 が与えられる、これは配列の長さである。
各テストケースの2行目には 個の整数 が与えられる、 は配列内の 番目の要素である。
全てのテストケースでの の和は 以下である。
出力
各テストケースについて、良い組を構成する2個の添え字 をスペース区切りで単一の行に出力せよ。 の場合も許容される。このようなペアは常に存在することは証明できる。良い組が複数存在する場合、そのいずれかを出力せよ。
入出力例
3 3 5 2 7 5 1 4 2 2 3 1 2
2 3 1 2 1 1
注記
1つ目のテストケースでは、 の場合、全ての について等式が成立します。
B. Subtract Operation / Операция вычитания (1000点)
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
整数 が与えられた時、その操作を施した後の、リスト内の唯一の要素が と等しくなるような 回の操作列が存在するかどうかを判定してください。
入力
入力は複数のテストケースから成る。1行目には単一の整数 が与えられる、これはテストケースの個数である。以下、テストケースの記述が続く。
各テストケースの1行目には2個の整数 が与えられる、それぞれリスト内の整数の個数と目標値である。
各テストケースの2行目には 個の整数 が与えられる。
全てのテストケースでの の和が を超えないことは保証されている。
出力
各テストケースについて、 回の操作で にすることができるのであればYES
と出力せよ。そうでなければNO
と出力せよ。
各文字はどのレターケースで出力してもよい(例えば、文字列"YES
", "Yes
", "yes
", "yEs
"は肯定とみなされる)。
入出力例
4 4 5 4 2 2 7 5 4 1 9 1 3 4 2 17 17 0 2 17 18 18
YES NO YES NO
注記
1つ目の入力例では、リストは で、目標 です。この目標を達成する方法の1つは次の通りです。まず、3番目の要素を選び、リストは となります。次に、1番目の要素を選び、リストは となります。最後に、1番目の要素を選び、リストは となります。
C. Make Equal With Mod / Сделай равным по модулю (1500点)
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
この操作を0回以上行うことで配列の全要素を等しくすることが可能かどうか判定してください。
入力
入力は複数のテストケースから成る。1行目には単一の整数 が与えられる、これはテストケースの個数である。以下、テストケースの記述が続く。
各テストケースの1行目には1個の整数 が与えられる、配列の長さである。
各テストケースの2行目には 個の整数 が与えられる、 は配列内の 番目の要素である。
全てのテストケースでの の和は 以下である。
出力
各テストケースについて、操作後のリスト内の全要素を等しくすることができるのであればYES
と出力せよ。そうでなければNO
と出力せよ。
各文字はどのレターケースで出力してもよい(例えば、文字列"YES
", "Yes
", "yes
", "yEs
"は肯定とみなされる)。
入出力例
4 4 2 5 6 8 3 1 1 1 5 4 1 7 0 8 4 5 9 17 5
YES YES NO YES
注記
1つ目のテストケースでは、 で操作を行うことで、配列 を得、 で操作を行うことで、配列 を得ます。
2つ目のテストケースでは、全数は既に等しいです。
4つ目のテストケースでは、 で操作を行うことで、配列 を得ます。
D. K-good / K-хорошие (2000点)
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
正整数 が与えられたとき、 が -goodであるような を求めて下さい、もしくは、そのような が存在しないことを判別してください。
入力
入力は複数のテストケースから成る。1行目には単一の整数 が与えられる、これはテストケースの個数である。
各テストケースは1行から成り、1個の整数 が与えられる。
出力
各テストケースについて、1行に が -good となるような の値を出力せよ、あるいは、どのような に対しても が -goodでない場合は と出力せよ。有効な の値が複数存在する場合は、そのいずれをも出力してももよい。
入出力例
5 2 4 6 15 20
-1 -1 3 3 5
注記
は次のように で割った時の余りが異なる 数の和として表せるため -goodです: 。
であり、 は で割った時、異なる余りを与えるため、 は -goodです。
であり、 は で割った時、異なる余りを与えるため、 は -goodです。
E. Equal Tree Sums / Одинаковые суммы деревьев (2500点)
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
次の条件を満たすように、各頂点に非零整数の重みを割り当てる必要があります: 木の任意の頂点を削除した時、残りの連結成分の各頂点の重みの和が等しい。
入力
入力は複数のテストケースから成る。1行目には単一の整数 が与えられる、これはテストケースの個数である。以下、テストケースの記述が続く。
各テストケースの1行目には1個の整数 が与えられる、木の頂点数である。
続く 行の各行には2個の整数 が与えられる、頂点 と の間に辺があることを表す。与えられる辺が木を構成することは保証されている。
全てのテストケースでの の和は 以下である。
出力
各テストケースについて、1行に 個の空白区切りの整数 を出力せよ、ここでの は 頂点 に割り当てられた重みである。重みは かつ を満たさなければならない。
これらの制約を満たす解が必ず存在することは証明できる。解が複数存在する場合は、そのいずれかを出力せよ。
入出力例
2 5 1 2 1 3 3 4 3 5 3 1 2 1 3
-3 5 1 2 2 1 1 1
注記
1つ目のテストケースでは、頂点 を削除した時の残りの連結成分の和は全て であり、頂点 を削除した時の残りの連結成分の和は全て となります。他の頂点を削除した場合は、残りの連結成分は1個であるため、連結成分の和は全て等しくなります。
F. Parametric MST / Параметрическое MST (3000点)
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
を の最小全域木*1のコストとします。 が上に有界であるかどうかを判別し、そうである場合、その最大値を出力して下さい。
入力
入力は複数のテストケースから成る。1行目には単一の整数 が与えられる、これはテストケースの個数である。以下、テストケースの記述が続く。
各テストケースの1行目には1個の整数 が与えられる、これはグラフの頂点数である。
各テストケースの2行目には 個の整数 が与えられる。
全てのテストケースでの の和は 以下である。
出力
各テストケースについて単一行に の最大値(整数であることは証明できる)を、もしくは が上に有界でない場合はINF
を出力せよ。
入出力例
5 2 1 0 2 -1 1 3 1 -1 -2 3 3 -1 -2 4 1 2 3 -4
INF -1 INF -6 -18
G. Cycle Palindrome / Циклические палиндромы (3250点)
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
の順列とは から への全単射函数のことです。 が相異なる数であるとき、順列 は周期順列であるといいます。ここで は を表します。
入力
入力は複数のテストケースから成る。1行目には単一の整数 が与えられる、これはテストケースの個数である。以下、テストケースの記述が続く。
各テストケースの1行目には1個の整数 が与えられる、これは列の大きさである。
各テストケースの2行目には 個の整数 が与えられる。
全てのテストケースでの の和は 以下である。
出力
各テストケースについて、周期順列が存在する場合、YES
と出力せよ、そうでなければNO
と出力せよ。
答えがYES
である場合、追加の1行に順列である 個の整数 を出力せよ。順列が複数存在するならば、いずれを出力してもよい。
入出力例
3 4 1 2 2 1 3 1 2 1 7 1 3 3 3 1 2 2
YES 3 1 4 2 NO YES 5 3 7 2 6 4 1
H. Equal LCM Subsets / Одинаковые НОК подмножеств (3750点)
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力
入力
入力は複数のテストケースから成る。1行目には1個の整数 が与えられる、これはテストケースの個数である。
各テストケースについて、2個の整数 から成る1行が与えられる、それぞれ集合 と の大きさである。
次の行には 個の相異なる整数 が与えられる、これらは の要素である。
次の行には 個の相異なる整数 が与えられる、これらは の要素である。
全てのテストケースでの の和と の和は 以下である。
出力
各テストケースについて、最小公倍数が等しい2つの部分集合が存在しない場合、1行にNO
で出力せよ。
そうでない場合、1行にYES
と出力し、続く行に2個の整数 を出力せよ、これらはそれぞれ部分集合 の大きさである。
次の行には の要素である 個の整数 を出力し、その次の行には の要素である 個の整数 を出力せよ。あり得る部分集合の組が複数存在する場合、いずれを出力してもよい。
入出力例
4 3 4 5 6 7 2 8 9 10 4 4 5 6 7 8 2 3 4 9 1 3 1 1 2 3 5 6 3 4 9 7 8 2 15 11 14 20 12
NO YES 1 2 6 2 3 YES 1 1 1 1 YES 3 2 3 7 4 12 14
I. Neighbour Ordering / Упорядочивание соседей (4500点)
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
グラフの各単純サイクル について、以下のいずれかを満たすとき、 隣人順序は良いといいます。
与えられた について、そのグラフに良い隣接順序が存在するかどうかを判別し、存在する場合はそれを構築して下さい。
入力
入力は複数のテストケースから成る。1行目には1個の整数 が与えられる、これはテストケースの個数である。以下、テストケースの記述が続く。
各テストケースの1行目には2個の整数 が与えられる、グラフの頂点数と辺の本数である。
続く 行の各行には2個の整数 が与えられる、これは頂点 間をつなぐ辺があることを表す。グラフには自己辺も同一頂点間の多重辺も存在しないことは保証されている。
全てのテストケースでの の和と の和は 以下である。
出力
各テストケースについて、1行に、良い隣接順序が存在する場合はYES
と、そうでなければNO
と出力せよ。各文字はどのレターケース(大文字/小文字)で出力してもよい。
答えがYES
である場合、さらに、良い隣接順序について記述した 行を出力せよ。 行目には、頂点 [tex;i] の隣接頂点を順番に出力せよ。
良い隣接順序が複数存在する場合は、そのいずれかを出力せよ。
入出力例
3 5 6 0 1 0 2 1 2 2 3 3 4 4 1 2 1 0 1 6 10 0 1 2 0 0 3 0 4 1 2 1 4 2 3 2 5 3 5 4 5
YES 1 2 4 2 0 0 1 3 2 4 3 1 YES 1 0 NO
Educational Codeforces Round 124 問題文和訳
- A. Playoff / Плей-офф
- B. Prove Him Wrong / Докажи, что он не прав
- C. Fault-tolerant Network / Отказоустойчивая сеть
- D. Nearest Excluded Points / Ближайшие точки
- E. Sum of Matchings / Сумма паросочетаний
- F. Tower Defense
A. Playoff / Плей-офф
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力
トーナメントは ラウンドで行われます。各ラウンドでは、各選手が、ちょうど1つの組に属するように組み分けを行います。それぞれの組で選手が競い合い、どちらかが勝ちます。勝者は次のラウンドに進み、敗者はトーナメントから脱落します。
組み分けは次のように行われます。
- 第1回戦では、選手 と選手 、選手 と選手 、選手 と選手 、…というように戦います。
- 第2回戦では、 の試合の勝者と の試合の勝者、 の試合の勝者と の試合の勝者、…というように戦います。
- その後のラウンドも同じルールで行われます。
選手 と が戦ったとき、勝者は次のように決まります。
- が奇数の場合、番号が小さい選手が勝つ(つまり、 なら が勝ち、そうでないなら が勝つ)
- が偶数の場合、番号が大きい選手が勝つ
次図は、 の時のトーナメントの様子です。
ここでの課題は、「整数 が与えらえれたとき、優勝する選手の番号を判別すること」です。
入力
1行目には単一の整数 が与えられる、これはテストケースの個数である。
各テストケースは1行から成り、1個の整数 が与えられる。
出力
各テストケースについて、1個の整数を出力せよ、その数とはトーナメントの勝者の番号である。
入出力例
2 3 1
7 1
注記
の場合は、問題文中の図に示されています。
の場合、選手 と の試合1回だけが行われます。 は奇数であるため、番号の小さい方の選手が勝ちます。よって、選手 が勝者となります。
B. Prove Him Wrong / Докажи, что он не прав
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
- 2つのインデックス
- とする*1
この操作でしばらく遊んでいたら、彼は次のような結論に達しました。
- である 個の整数のどのような配列 に対しても、操作後に の総和が減少するようなインデックスの組 が見つけることができる*2
この文は疑わしいと思っているため、与えられた について反例を見つけたいと思っています。反例を見つけ、彼が間違っていると証明できるでしょうか?
言い換えると、どのようなインデックスの組 に対しても操作後に総和が減少しない(増加、または変化なし)ような 個の整数 からなる配列 を見つけてください。
入力
1行目には単一の整数 が与えられる、これはテストケースの個数である。その後、 個のテストケースが続く。
各テストケースの1行目にして唯一の行には、単一の整数 が与えられる、これは配列 の長さである。
出力
各テストケースについて、反例である大きさ の配列 が存在しない場合、NO
と出力せよ。
そうでない場合、YES
と出力し、その後、配列 自身 を続けて出力せよ。反例が複数存在する場合、そのうちにいずれかを出力せよ。
入出力例
3 2 512 3
YES 1 337 NO YES 31 4 159
注記
1つ目のテストケースでは、有効なインデックスの組は のみです。
インデックス (または )に対して操作を行うと、、つまり、配列 を得ます。どちらの場合も操作が増加するため、この配列 は反例となります。
C. Fault-tolerant Network / Отказоустойчивая сеть
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
初期状態では、各列の隣接するコンピュータの組(全ての について組 )はワイヤーでつながれていて、2列が2つの独立したコンピュータネットワークを形成しています。
ここでの課題は、「1つ以上の異なる列のコンピュータの組を繋ぐことで1つの共通ネットワークに結合する」ことです。1列目の 台目のコンピュータと2列目の 台目のコンピュータを繋ぐには のコストがかかります。
1台のコンピュータを他の複数のコンピュータと接続することはできますが、少なくとも基本的な障害耐性(フォールトトレランス)を確保する必要があります、即ち、1台のコンピュータが故障しても、ネットワークがつながったままになるようにコンピュータを接続する必要があります。言い換えれば、1台のコンピュータが故障しても(それがどのコンピュータであっても)、ネットワークが2つ以上に分かれないようにするということです。
障害耐性ネットワークを構築するために必要は最小コストはいくつでしょう?
入力
1行目には単一の整数 が与えられる、これはテストケースの個数である。その後、 個のテストケースが続く。
各テストケースの1行目には、単一の整数 が与えられる、これは各列のコンピュータの台数である。
各テストケースの2行目には、 個の整数 が与えられる、これらは1列目のコンピュータの等級である。
各テストケースの3行目には、 個の整数 が与えられる、これらは2列目のコンピュータの等級である。
全てのテストケースでの の和が を超えないことは保証されている。
出力
各テストケースについて単一の整数を出力せよ、その数とは障害耐性ネットワークを構築するために必要は最小コストである。
入出力例
2 3 1 10 1 20 4 25 4 1 1 1 1 1000000000 1000000000 1000000000 1000000000
31 1999999998
注記
1つ目のテストケースでは、4組のコンピュータを接続するのが最適です。
- 1列目のコンピュータ と2列目のコンピュータ : コスト
- 1列目のコンピュータ と2列目のコンピュータ : コスト
- 1列目のコンピュータ と2列目のコンピュータ : コスト
- 1列目のコンピュータ と2列目のコンピュータ : コスト
合計で、 です。
2つ目のテストケースでは、1列目の と2列目の 、1列目の と2列目の を接続するのが最適です。
D. Nearest Excluded Points / Ближайшие точки
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
各点 について、与えられた 点に含まれない、(マンハッタン距離で)最も近い整数座標の点を求めて下さい。そのような点が複数存在する場合、どれを選んでもいいです。
2点 間のマンハッタン距離は です。
入力
1行目には単一の整数 が与えられる、これはテストケースの個数である。その後、 個のテストケースが続く。
続く 行は点についての説明である。その 行目には2個の整数 が与えられる、これは 番目の点の座標である。
入力内の全ての点が相異なることは保証されている。
出力
行出力せよ。 行目には与えられた 点に含まれない、 番目の点から(マンハッタン距離で)最も近い整数座標の点を出力せよ。
出力する座標は範囲 内でなければならない。どのような最適解もこれらの制約を満たすことは証明することができる。
答えが複数存在する場合、どれを出力してもよい。
入出力例
6 2 2 1 2 2 1 3 2 2 3 5 5
1 1 1 1 2 0 3 1 2 4 5 4
8 4 4 2 4 2 2 2 3 1 4 4 2 1 3 3 3
4 3 2 5 2 1 2 5 1 5 4 1 1 2 3 2
E. Sum of Matchings / Сумма паросочетаний
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力
2部グラフが与えられます。第1部の頂点には から までの、第2部の頂点委は から までの番号が振られています。各頂点の次数は です。
かつ を満たす整数4つ組 について、区間 または区間 に含まれる与えられたグラフの全ての頂点と、端点がこれらの区間どちらかに属する与えられたグラフの辺から成るグラフを と定義します。即ち、元のグラフから を得るには、 かつ を満たす全ての頂点 と、これらの頂点にくっついている全ての辺を削除しなければなりません。
かつ を満たす全ての整数の組 に対する *3 の和を計算してください。
入力
1行目には単一の整数 が与えられる、これは各部の頂点数である。
行が続き、各行はグラフの辺を表す。 行目には2個の整数 が与えられる、これらは 本目の辺の端点である。
与えられるグラフには多重辺はなく、各頂点はちょうど2本の接続辺を持つ。
出力
各テストケースについて単一の整数を出力せよ、その数とは、 かつ を満たす全ての整数の組 に対する の和である。
入出力例
5 4 6 4 9 2 6 3 9 1 8 5 10 2 7 3 7 1 10 5 8
314
F. Tower Defense
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力
番目の地点の塔のマナ容量は でマナ再生率は です。初期状態 秒時点では、各塔のマナは最大値です。ある秒数立った時点で 番目の塔のマナ量が である場合、その 秒後には マナになります。
つのレベルにはモンスターが 体登場します。 体目のモンスターは 秒後に体力 で地点 にスポーンします。各モンスターは、座標が増加する方向に毎秒 ポイントずつ移動します。
モンスターが塔を通過するとき、塔はモンスターに ダメージを与えます、ここでの はモンスターの現在体力で、 はタワーの現在マナ量です。この値をモンスターの体力とタワーのマナ量から差し引きます。
残念なことに、塔を全て通過してしまうモンスターがいることもあります。Монокарпは、全ての塔を通過した後のモンスターの体力の総和を知りたいと思っています。
入力
1行目には単一の整数 が与えられる、これは塔の個数である。
続く 行の 行目には、2個の整数 が与えられる、これらは 番目の塔のマナ容量とマナ再生率である。
次の行には単一の整数 が与えられる、これはモンスターの数である。
続く 行の 行目には、2個の整数 が与えられる、これらは 体目のモンスターのスポーン位置と体力である。
モンスターはスポーン時間の昇順に並んでいるため、全ての について が成立する。
出力
単一の整数を出力せよ、その数とは全ての塔を通過した後のモンスターの体力の総和である。
入出力例
3 5 1 7 4 4 2 4 0 14 1 10 3 16 10 16
4
5 2 1 4 1 5 4 7 5 8 3 9 1 21 2 18 3 14 4 24 5 8 6 25 7 19 8 24 9 24
40
Codeforces Round #776 (Div. 3) 問題文和訳
- A. Deletions of Two Adjacent Letters / Удаления двух соседних букв
- B. DIV + MOD
- C. Weight of the System of Nested Segments / Вес системы вложенных отрезков
- D. Twist the Permutation / Петя и циклические сдвиги
- E. Rescheduling the Exam / Перенос экзамена
- F. Vitaly and Advanced Useless Algorithms / Виталий и Advanced Useless Algorithms
- G. Counting Shortcuts / Подсчёт коротких путей
A. Deletions of Two Adjacent Letters / Удаления двух соседних букв
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
文字列の長さが よりも大きい限り、次の操作を行うことができます: 文字列 内の任意の隣接する2文字を選び、それを文字列から削除するという操作です。例えば、文字列"lemma
"に操作を一度行うと、次の4つの文字列のいずれかを得ることができます: "mma
", "lma
", "lea
", "lem
"。具体的には、1回の操作で、文字列の長さは だけ短くなります。
形式的にが、文字列 を という形で表されるとします。1回の操作で、任意のインデックス を選び、 に置き換えます。
与えられた文字列 と文字 について、最終的に等式 が成立するような一連の操作が可能であるか判別して下さい。即ち、文字 から成る長さ の文字列で処理が終了するような一連の操作は存在するでしょうか?
入力
入力データの1行目には1個の整数 が与えられる、これは入力のテストケース数である。
個のテストケースの説明が続く。各テストケースは2行で表される。
- から までの奇数長で、ラテンアルファベットの小文字で構成される文字列
- ラテンアルファベットの小文字1文字 から成る文字列
出力
各テストケースについて、別々の行に次を出力せよ。
- 文字列 を が真となるように変換できる場合、
YES
- そうでない場合、
NO
YES
とNO
はどのレターケースで出力してもよい(例えば、文字列yEs
, yes
, Yes
, YES
は肯定とみなされる)。
入出力例
5 abcde c abcde b x y aaaaaaaaaaaaaaa a contest t
YES NO NO YES YES
注記
1つ目のテストケースでは、 "abcde
"です。 "c
"にしなければなりません。1回目の操作では、最初の2文字を消し、 "cde
"となります。2回目の操作で最後の2文字を消し、期待される値 "c
"を得ます。
3つ目のテストケースでは、 "x
"で、 "y
"にしなければなりません。明らかに、これを実現することはできません。
B. DIV + MOD
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
- ; ここでは は の切り捨てを、 は を で割った余りを表す。
例えば、 とすると、 という値になります。
数 は固定で、Владにとって既知です。 が から までの両端を含む 任意の整数を取りえる場合、 の最大値をВладが求められるよう手助けをしてください。
入出力例
5 1 4 3 5 8 4 6 10 6 1 1000000000 1000000000 10 12 8
2 4 5 999999999 5
注記
1つ目のテストケースでは
答えとしては、自明として、 と が適切です。
C. Weight of the System of Nested Segments / Вес системы вложенных отрезков
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
各組 について条件 を満たすとき、 個の区間の列 は入れ子区間と呼ばれます。言い換えると、2番目の区間は1番目の区間の厳密な内側にあり、 3番目の区間は2番目の区間の厳密な内側にある、という具合に成り立っているというものです。
与えられた数 について、次を満たす入れ子区間を求めて下さい。
例えば、 とします。与えられた点が、図中に示され、重みは赤で、座標は青で書かれています。次のような3つの入れ子区間のシステムを構築します。
入力
入力データの1行目には1個の整数 が与えられる、これは入力のテストケース数である。
各テストケースの前には空行が書かれている。
各テストケースの1行目には2つの正整数 が与えられる。
続く 行には整数の組 が与えられる、これらはそれぞれ番号 の点の座標と重みを表す。全ての は相異なる。
全てのテストケースでの の和が を超えないことは保証されている。
出力
各テストケースについて、 行出力せよ。その1行目には構築したシステムの重みを出力し、続く 行にはちょうど2個の整数を出力せよ、2つの整数とは 個目の区間 の端点のインデックスである。区間の端点を出力する順番は重要ではなく、先に左端点のインデックスを出力し、次に右端点の番号を出力してもよく、その逆でもよい。
入出力例
3 3 8 0 10 -2 1 4 10 11 20 7 -1 9 1 2 3 5 -2 3 6 -1 2 1 3 3 -1 2 4 4 0 8 2 2 5 5 -1 3 -2 1 0 -2 0 -5 -3
12 2 6 5 1 7 8 10 1 6 5 2 3 4 -6 5 1 4 2
注記
1つ目のテストケースでは、問題文の例と一致します。構築されたシステムの重みが最小であることは証明できます。
2つ目のテストケースでは、 個の点しかないため、それぞれを用いて 個の区間を構成する必要があります。
D. Twist the Permutation / Петя и циклические сдвиги
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
彼は 回の操作を順次に行いました。そして最後に、彼は新しい状態の配列 を受け取りました。
回目の操作では、Петяは配列の最初の 個の要素を選び、それらを右にに似の回数循環シフトさせました( 以上のインデックスの要素はそのままです)。1回の右への循環シフトは、配列 を配列 にするような変換です。
例えば、 で (つまり、3回目の操作)の場合、この操作の結果として、彼は次の3つの配列のいずれかを得ることができます。
- ( 回の循環シフト、もしくは で割り切れる回数)
- ( 回の循環シフト、もしくは で割ると 余る回数)
- ( 回の循環シフト、もしくは で割ると 余る回数)
また、別の例を見てみましょう。、即ち 初期状態で とします。考えられるシナリオの1つは次の通りです。
- : Петяが何回循環シフトを行っても配列 は変化しない
- : Петяが 回循環シフトを行うとすると、配列は となる
- : Петяが 回循環シフトを行うとすると、配列は となる
- : Петяが 回循環シフトを行うとすると、配列は となる
- : Петяが 回循環シフトを行うとすると、配列は変化しない
- : Петяが 回循環シフトを行うとすると、配列は となる
回の操作を行った後の配列 の最終状態が与えられます。この結果になるような操作方法が存在するか判別してください。答えが存在する場合、 回の操作のそれぞれで行った循環シフトの回数を出力して下さい。
入力
入力データの1行目には1個の整数 が与えられる、これは入力のテストケース数である。
テストケースについての記述が続く。
各テストケースの1行目には1個の整数 が与えられる、これは配列 の長さである。
次の行には配列 の最終状態である 個の整数 が与えられる。全ての は相異なる。
全てのテストケースでの の和が を超えないことは保証されている。
出力
各テストケースについて、答えを個別の行に出力せよ。
与えられた最終の値 が各操作での任意の数の巡回シフトによって得ることが場合は を出力せよ。そうでない場合、 個の非負整数 を出力せよ、ここでの は、 番目の操作の間に配列の最初の 個の要素が右に 回巡回シフトされたことを意味する。
複数の答えが存在する場合、シフトの総数が最小となる(つまり の値の合計が最小の)ものを出力せよ。そのような答えが複数存在する場合は、そのうちのいずれかを出力せよ。
入出力例
3 6 3 2 5 6 1 4 3 3 1 2 8
0 1 1 2 0 4 0 0 1 0 1 2 0 2 5 6 2
E. Rescheduling the Exam / Перенос экзамена
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
試験期間のスケジュールについて、Дмитрийは特別な値 について考えています、この値は全ての試験の前の休息時間の最小値です。例えば、上の図について、 です。スケジュールにおいて、彼は正確に 個の数、試験 と の間の休息日数(試験機関の開始を と見做す*4 )を数えます。そして、この 個の数の中で最小値である を求めます。
Дмитрийは試験期間のスケジュールを改善できると考えています。彼は、1つの試験の日程を変更する(任意の1つの を変更する)よう求めることができます。 が全て異なるままで、 の値ができるだけ大きくなるように、彼が日付を変更するのを手助けしてください。
例えば、上のスケジュールについて、2回目の試験を試験期間の一番最後に動かすのがДмитрийにとって最も有利です。新しいスケジュールは次のようになります。
(状況を改善するために試験を移動させる方法がない場合、)Дмитрийは提供されたスケジュールを変更しないままにしておくこともできます。
入力
入力データの1行目には1個の整数 が与えられる、これは入力のテストケース数である。テストケースについての記述が続く。
各テストケースの前には空行が書かれている。
各テストケースの1行目には2個の整数 が与えられる、これらはそれぞれ、試験の個数と期間の長さである。
各テストケースの2行目には 個の整数 が与えられる、この 番目の数が 番目の試験の日付を表す。
全てのテストケースでの の和が を超えないことは保証されている。
出力
各テストケースについて、Дмитрийが1つの試験を任意の日に移動させることができる場合の の最大値を出力せよ。 の値は全て異なるままでなければならない。
入出力例
9 3 12 3 5 9 2 5 1 5 2 100 1 2 5 15 3 6 9 12 15 3 1000000000 1 400000000 500000000 2 10 3 4 2 2 1 2 4 15 6 11 12 13 2 20 17 20
2 1 1 2 99999999 3 0 1 9
注記
1つ目の入出力例は、問題文中に書かれています。
2つ目の入出力例での最適なスケジュール変更は次の通りです。
3つ目の入出力例では、 日目の試験を 日目から 日目の間の任意の日に移動させる必要があります。
4つ目の入出力例では、いかなるスケジュールの変更でも が小さくなるため、スケジュールをそのままにしておくべきです。
5つ目の入出力例では、 日目の試験を 日目から 日目の間の任意の日に移動させる必要があります。
6つ目の入出力例での最適なスケジュール変更は次の通りです。
7つ目の入出力例では、どの日も試験日であり、スケジュールを変更することは不可能です。
F. Vitaly and Advanced Useless Algorithms / Виталий и Advanced Useless Algorithms
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
Виталийは何事も誠実に行うため、各タスクを 以上完了させたいと思っています。初期状態では、彼の各タスクの完了率は です。
Виталийには複数のトレーニングオプションがあり、各オプションは1度までしか使用できません。 番目のオプションは3つの整数 によって特徴づけられます。Виталийが 番目のオプションを利用した場合、(現時点から) 時間後に彼は、タスク の進捗を 進めることになります。
例えば、Виталийに3つのタスクがあるとします。配列 が であるとします。Виталийには次の つのオプションがあるとします: 。
このとき、次のように準備を行うと、Виталийは時間内に全てを完了させることができます。
- Виталийが 番目のオプションを選ぶ。 時間後に、 番目のタスクを にする。 番目のタスクの締切まであと 時間である。
- Виталийが 番目のオプションを選ぶ。 時間後に、 番目のタスクを完了させる。 番目のタスクの締切まであと 時間、 番目のタスクの締切まであと 時間である。
- Виталийが 番目のオプションを選ぶ。 時間後に、 番目のタスクを で完了させ、締め切りちょうどに 番目のタスクが完了したことになる。
- Виталийが 番目のオプションを選ぶ。 時間後に、 番目のタスクを完了させ、締め切りちょうどに 番目のタスクが完了したことになる。*6
このようにして、 つのオプションを行うことで、Виталийは時間内にコースを完全に完了させることができます。
Виталийは正しい順番でタスクを完了させることができるように、オプションを出力し、Виталийを助けてください。各オプションは一度までしか使用できないことに注意してください。答えが複数存在する場合、そのいずれをを出力してもいいです。
入力
入力データの1行目には1個の整数 が与えられる、これは入力のテストケース数である。
テストケースについての記述が続く。
各テストケースの記述の1行目には2個の整数 が与えられる、これらはそれぞれ、タスクとトレーニングオプションの個数である。
次の行には 個の整数 が与えられる、タスク の締め切りを表す。配列の値は非減少、即ち となっている。
続く 行には、3つ組の整数 が与えられる、もしВиталийがこのオプションを選択すれば、 時間後にタスク の進捗を 進める。オプションには入力データの順に から までの番号が振られている。
全てのテストケースでの の和が を超えないことは保証されている。
出力
各テストケースについて、1行目に、数 を出力せよ、これは、オプションのうち 個を用いて、Виталийが各タスクを 以上で完了できることを表す。同じオプションは繰り返してはいけない。Виталийが全てのタスクを時間内に完了できない場合は、 を出力せよ。
もし答えが存在する場合、続く行に から までの異なる整数 個を、望む順序での選択肢の番号を、出力せよ。複数の答えが存在する場合、そのいずれを出力してもよい。
入出力例
5 3 5 5 7 8 1 1 30 2 3 50 2 3 100 1 1 80 3 3 100 1 5 51 1 36 91 1 8 40 1 42 83 1 3 45 1 13 40 2 9 9 20 2 8 64 2 7 64 1 20 56 2 8 76 2 20 48 1 2 89 1 3 38 2 18 66 1 7 51 3 2 7 18 33 1 5 80 3 4 37 2 5 569452312 703565975 1 928391659 66 1 915310 82 2 87017081 92 1 415310 54 2 567745964 82
4 1 4 3 5 3 2 4 5 4 6 7 1 2 -1 4 2 4 3 5
3 3 9 20 31 40 1 9 64 3 17 100 3 9 59 3 18 57 3 20 49 2 20 82 2 14 95 1 8 75 2 16 67 2 6 20 36 2 2 66 2 20 93 1 3 46 1 10 64 2 8 49 2 18 40 1 1 1000000000 1 1000000000 100
-1 4 3 4 1 5 1 1
G. Counting Shortcuts / Подсчёт коротких путей
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力
頂点 から への経路のうち、 から までの最短経路と長さの差が 以下である経路の数を求めて下さい。このとき、同じ頂点や辺を2回以上通るもの(単純でないパス)であっても、条件を満たす形を全てを考慮する必要があります。
例えば、 として、上図のようなグラフであるとします。 から への最短経路の長さは です。長さが最大で である経路を全て考えます。
- : 経路長は
- : 経路長は
- : 経路長は
- : 経路長は
合致する経路は全部で4本あります。
入力
入力データの1行目には1個の整数 が与えられる、これは入力のテストケース数である。テストケースについての記述が続く。
各テストケースの前には空行が書かれている。
各テストケースの1行目には2個の整数 が与えられる、これらはグラフの頂点数と辺の本数である。
2行目には2個の整数 が与えられる、これらは経路の始点と終点の番号である。
続く 行には辺の記述が与えられ、その 行目には2個の整数 が与えられる、これらは 本目の辺が結ぶ頂点の番号である。グラフは連結であり、自己辺や多重辺が含まないことは保証されている。
入力データ内の全てのテストケースでの の和が を超えないことは保証されている。同様に、入力データ内の全てのテストケースでの の和が を超えないことは保証されている。
出力
各テストケースについて、単一の数を出力せよ、その数とは から までの最短経路と長さの差が 以下である経路の個数である。
この数は大きくなるかもしれないため、modulo で出力せよ。
入出力例
4 4 4 1 4 1 2 3 4 2 3 2 4 6 8 6 1 1 4 1 6 1 5 1 2 5 6 4 6 6 3 2 6 5 6 1 3 3 5 5 4 3 1 4 2 2 1 1 4 8 18 5 1 2 1 3 1 4 2 5 2 6 5 7 3 8 4 6 4 8 7 1 4 4 7 1 6 6 7 3 8 8 5 4 5 4 3 8 2
2 4 1 11
*1:露[vɫat](ヴラド、Vlad); Vladはルーマニア語などではスラブ系の男性名 Vladimirなどの短縮形・愛称の一つであるが、ここではロシア人名とした
*2:露[ˈpʲetʲə](ピェチャ、Petya, Pjetja): ロシア男性名 Пётр(Петр、Petr、ピョートル)の指小形、愛称、英Peteに相当、Пётрは英独Peter等と同じく聖ペテロに由来
*3:露[ˈdmʲitrʲɪj](ドミトリー、Dmitri, Dmitry, Dmitrij) ロシア男性名、英Demetriusに相当、Пётрは英独Peter等と同じく古典ギリシャ男性名Δημήτριος(Dēmḗtrios)に由来
*4:この部分は意訳、恐らく誤記あり
*5:露[vʲɪˈtalʲɪj](ヴィタリー、Vitali, Vitaly, Vitalij) ロシア男性名、ラテン男性名Vītālisに由来
*6:この部分も意訳
AtCoder Beginner Contest 242のきろく
AtCoder Beginner Contest 242に参加。
- A - T-shirt (100点)
- B - Minimize Ordering (200点)
- C - 1111gal password (300点)
- D - ABC Transform (400点)
- E - (∀x∀) (500点)
- F - Black and White Rooks (500点)
- G - Range Pairing Query (600点、実行時間制限: 5 sec)
- Ex - Random Painting (600点、実行時間制限: 3 sec): 未提出
- 結果、感想
A - T-shirt (100点)
の時は必ずTシャツは貰えるので、答えの確率は 、 の時は、Tシャツをもらえることが無いので です。
その他のときは 人の中から一様に 人を選ぶとき、自分が選ばれるときの確率ですので が答えとなります。
B - Minimize Ordering (200点)
内の文字を昇順に並び替えればいいので、sort
関数で並び替えてやればいいです。
C - 1111gal password (300点)
桁DPです。
とします。このとき、初期条件をとして、遷移条件によって まで でDPの値を求めたときの、 が答えとなります。D - ABC Transform (400点)
この問題では文字列を0-based indexで考えます。
A
→B
→C
→A
という循環を考えます。
から が作られるとき、 の 文字目から の 文字目と 文字目が作られます。このとき、 文字目は循環において つ進んだ文字、 文字目は循環において つ進んだ文字となります。
このことから次のことが分かります。
- の 文字目は大本を辿ると の 文字目に由来する。
→ クエリ""について 、 として、 の 文字目を求める問題として読み替えることができます。 - 元の 文字目から 回操作後の 文字目に遷移するまで、 の遷移を 回、 の遷移を 回行う。ここでの は二進数表記での である桁の数を表す函数
→ 循環上では だけ進んだ文字になります。
よってこの二つの観察から答えを導くことができました。
E - (∀x∀) (500点)
回文であるので先頭 文字の決め方について考えます。
まず、 の先頭 文字よりも辞書順で小さい 文字の文字列の数を求めます。
先頭 文字が等しいものは 個あります。ここでの は文字 のアルファベット順の順番から を引いたものです。よって を から までを足し合わせたものがここでの値です。
次に、 と先頭 文字が等しい 文字の回文が よりも辞書順で小さいかどうかを調べます。これで を定義します。この段落での最初の文での条件を満たせるなら 、そうでなければ を返します。
これらよりこの問題の答えは となります。
F - Black and White Rooks (500点)
包除原理が思いつかなかった... 通したら追記します。 upsolveしたので追記します。
白と黒の飛車/Rookが同一列、同一行内に存在するとき、その行または列内で、互いに利いている白と黒のペアが存在します。その為、各行、列は駒なし/白/黒のいずれかです。よって、各行、列の状態について、各色が選ばれた行、列の全てに駒が存在し、かつ選ばれた行、列以外に駒が存在しないような配列の方法数が分かればいい、ということまではコンテスト中には分かっていました。
選ばれた行、列のみ注目します。「いずれの行、列にも駒が存在する」ということはde Morganの法則から包除原理で計算することができます。このことから最終的な答えは です。括弧の中をメモ化しておくことで計算量 で答えることができました。
G - Range Pairing Query (600点、実行時間制限: 5 sec)
Mo’s Algorithm(莫のアルゴリズム、平方根分割)だと気づくのが遅く実装できませんでした... 通したら追記します。 upsolveしたので追記します。
各クエリに対する答えは です。区間を から や に更新するとき、追加または削除された色の人数の偶奇によって、答えが 増減したり、変わらなかったりします(具体的には人数増加して偶数になったら 、人数減少して奇数になったら 、その他は不変)。そのため、各色の人数と答えを変数で管理することで区間の の更新は で行うことができるため、Mo’s Algorithmを適用することができます。
Mo’s Algorithmはクエリを先読みし、ある特定の順番でクエリを処理することでクエリの更新回数を減らすというアルゴリズムです。全体区間をある大きさのブロックに分割し、各区間を左端がどのブロックに属すかで、ソートします。同一ブロック内の区間たちについては右端でソートします(こちらはブロックではなくもとの値でソート)。このときのブロックの大きさは大体 ぐらいにすることが多く、そのとき計算量は となります。
Ex - Random Painting (600点、実行時間制限: 3 sec): 未提出
難しそう...
Codeforces Round #774 (Div. 2)のきろく
Highest更新!! 問題文和訳はこちら
- A. Square Counting / Сколько квадратов? (750点)
- B. Quality vs Quantity / Качество против количества (1000点)
- C. Factorials and Powers of Two / Факториалы и степени двойки (1250点)
- D. Weight the Tree / Взвесьте дерево (2000点)
- E. Power Board / Степенная таблица (2500点)
- F. Playing Around the Table / Игра вокруг стола (3000点): 未提出
- 結果、感想
A. Square Counting / Сколько квадратов? (750点)
の個数が である時、 から までの整数を作ることができます。 であるため、各 について作ることができる整数は互いに異なります。したがって、答えは となります。
B. Quality vs Quantity / Качество против количества (1000点)
赤の要素の和を大きく、青の要素の和を小さくしたいので、赤は大きい方から、青は小さい方から要素をとればいいことが分かります。
予め、大きい方に並べたときの累積和を計算しておくと、青の要素が 個であるとき、sumの条件を満たす赤の要素の最低個数を二分探索(std::upper_bound
等)で調べることができ、その値を としたとき、 かつ を満たすような が存在するとき、その数列では条件を満たす彩色方法が存在します。
また、赤の要素数を としたとき、青が 個の要素で条件を満たせないとき、要素数を増やしても、条件は満たされないため、 の条件で、大きい方からの 個の和と小さい方からの 個の和の大小を比べることでも判別することができます。
C. Factorials and Powers of Two / Факториалы и степени двойки (1250点)
二進数表記で である桁に対応して足し合わせることで、2の累乗の和として数を表現することができます。
そのため、用いる階乗の集合を定めた時、2の累乗の集合は簡単に求まります。そのため、用いる階乗の集合を全探索すれば良いことが分かります。使える階乗は最大でも までであり、 と は2の累乗でもあるため、 から までの 通りです。そのため、それぞれ使う/使わないのbit全探索で間に合うことが分かります。
D. Weight the Tree / Взвесьте дерево (2000点)
この問題はコンテスト中には通せませんでした... 気付けてもよかったのに...
の場合は、自明でしょう。
の場合を除いて、隣接する頂点の両方を良い頂点にすることはできません。また、木全体の重みの和を小さく抑えたいので良い頂点の重さはその頂点の次数、そうでない頂点の重さは になります。
頂点 を根として次のような木DPを考えることができます。 は、 を根とした部分木で を良い頂点として( ? 選ぶ : 選ばない)ときの最適な(良い頂点の数, 重みの和)の組とします。但し、 のとき、 の重みには元の木での の親頂点を考慮します。このときの遷移式は
よって、 のそれぞれからDFSによって木DPを行い、 が答えとなります。
各頂点の重みは経路復元によって求めますが、DFSの際、各 においての最適条件で、どの子頂点が良い頂点であるかを記憶しておくことで簡単に求めることができます。
E. Power Board / Степенная таблица (2500点)
ボード上の数の集合を とします。
行目は のみが含まれます。
行目以降について考えます。非累乗数 について の累乗である の要素の集合は となり、その大きさは と等しいです。これらは各 について互いに素(共通部分を持たない)であるため、上記の集合の要素数が分かればいいです。これは を予め求めておくことで、高速で計算することができます。
累乗数についてはそれより小さい非累乗数のいずれかの累乗であるため、こちらについて考える必要はありません。
F. Playing Around the Table / Игра вокруг стола (3000点): 未提出
分かりません...
結果、感想
今回E問題を通してレートを大幅に上げることができました。ただ、D問題が通せなかったのは要反省ですね。
Codeforces Round #774 (Div. 2) 問題文和訳
- A. Square Counting / Сколько квадратов? (750点)
- B. Quality vs Quantity / Качество против количества (1000点)
- C. Factorials and Powers of Two / Факториалы и степени двойки (1250点)
- D. Weight the Tree / Взвесьте дерево (2000点)
- E. Power Board / Степенная таблица (2500点)
- F. Playing Around the Table / Игра вокруг стола (3000点)
A. Square Counting / Сколько квадратов? (750点)
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
Luisは数列を失くしてしまいましたが、 と の値は覚えています。数列の要素のうち、 に等しいものの個数を求めることができますか?
与えられた制約のもとでは答えが一意であることは証明できます。
入力
各テストは複数のテストケースが含まれる。1行目にはテストケースの個数 が与えられる。以下、テストケースの記述が続く。
各テストケースの唯一の行には2個の整数 が与えられる。 の値は、上記の制約を満足する数列の和として有効なものであることが保証されている。
出力
各テストケースについて、単一の整数を出力せよ、その数とは数列内の に等しい項の個数である。
入出力例
4 7 0 1 1 2 12 3 12
0 1 3 1
注記
1つ目のテストケースでは、 であるため、全ての数が であり、 となる数は存在しません。
2つ目のテストケースでは、 です。可能な数列は2つあります: 。どちらの場合でも、数 は一度だけ現れます。
3つ目のテストケースでは、 で、このケースでの の可能な最大値です。そのため、数 は数列内に 回現れます。
B. Quality vs Quantity / Качество против количества (1000点)
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
色 について、 は数列内のその色で塗られた要素数、 は数列内のその色で塗られた要素の和を表します。
例えば、与えられた数列が で、次のように彩色します: ( は赤に、 と は青に塗られ、 と は無彩色)。この時、 となります。
かつ となるように数列を塗り分けることができるか判別してください。
入力
各テストは複数のテストケースが含まれる。1行目にはテストケースの個数 が与えられる。以下、テストケースの記述が続く。
各テストケースの1行目には1個の整数 が与えられる、これは与えられる数列の長さである。
各テストケースの2行目には 個の整数 が与えられる、これは与えられる数列である。
全てのテストケースでの の和が を超えないことは保証されている。
出力
各テストケースについて、与えられた数列を上記の要件を満たすように塗ることが可能であればYES
と出力せよ、そうでなければNO
と出力せよ。
YES
とNO
はどのレターケースで出力してもよい(例えば、文字列yEs
, yes
, Yes
, YES
は肯定とみなされる)。
入出力例
4 3 1 2 3 5 2 8 6 3 1 4 3 5 4 2 5 1000000000 1000000000 1000000000 1000000000 1000000000
NO YES NO NO
注記
1つ目の入力例では、条件を満たす数列の彩色方法はありません。例えば、次のように彩色したとします: ( は赤、 と は青)。この時、 ですが、 です。そのため、これは条件を満たす数列の彩色方法ではありません。
2つ目の入力例では、問題文で記述されているように塗ることができます。 であることが確認できます。
3つ目の入力例では、条件を満たす数列の彩色方法はありません。例えば、次のように彩色したとします: ( と は赤、 と は青)。この時、 ですが、] です。そのため、これは条件を満たす数列の彩色方法ではありません。
4つ目の入力例では、sumとcountの制約を満たす数列の塗り分けは不可能であることを証明することができます。
C. Factorials and Powers of Two / Факториалы и степени двойки (1250点)
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
正整数 が与えられます。 が 個の相異なる強力な数の和として表現できるような最小の数 を求めて下さい、もしくは、そのような が存在しないことを判別してください。
入力
各テストは複数のテストケースが含まれる。1行目にはテストケースの個数 が与えられる。以下、テストケースの記述が続く。
各テストケースはただ1つの行から成り、1個の整数 が与えられる。
出力
各テストケースについて、別々の行に答えを出力せよ。
が相異なる強力な数の和として表現できない場合は、 を出力せよ。
そうでない場合、単一の正整数を出力せよ、その数とは、 の可能な最小値である。
入出力例
4 7 11 240 17179869184
2 3 4 1
注記
1つ目のテストケースでは、 は と表現することができ、 と は強力な数です。 は強力な数ではないので、このケースでの の可能な最小値は であることが分かります。
2つ目のテストケースでは、 を3個の強力な数の和として表現できる方法として が考えられます。 を2個以下の強力な数の和として表現することができないことを証明することができます。
3つ目のテストケースでは、 は と表現することができます。強力な数は相異ならなければならないので は有効な表現でないことに注意して下さい。
4つ目のテストケースでは、 であるため、 は強力な数であり、このケースの最小の は です。
D. Weight the Tree / Взвесьте дерево (2000点)
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
各 について、 番目の頂点の重みを とします。その重みが全ての隣接頂点の重みの和と等しい時、その頂点は良いと言います。
初期状態では、全ての頂点の重みは未定義です。木内の良い頂点の数が最大になるように、各頂点に正整数の重みを割り当てて下さい。複数の方法がある場合は、木の全頂点の重みの和を最小にする方法を求めて下さい。
入力
1行目には1つの整数 が与えられる、この数は木の頂点数です。
その後、 行が続く。各行には、頂点 と の間の辺を表す2個の整数 が与えられる。辺が木を形成することは保証されている。
出力
1行目には、2個の整数を出力せよ、その数とは良い頂点の最大数とその最大値に対する重みの和の可能な最小値である。
2行目には、 個の整数 を出力せよ、これらは各頂点に割り当てられた重みである。これらの制約を満たす最適解が存在することは証明することができる。
複数の最適解が存在する場合は、いずれを出力してもよい。
入出力例
4 1 2 2 3 2 4
3 4 1 1 1 1
3 1 2 1 3
2 3 1 1 1
2 1 2
2 2 1 1
9 3 4 7 6 2 1 8 3 5 6 1 8 8 6 9 6
6 11 1 1 1 1 1 1 1 3 1
注記
1つ目のテストケースでの木はこちらです。
2つ目のテストケースでの木はこちらです。
E. Power Board / Степенная таблица (2500点)
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力
行と 列の交点にあるセルには ( の 乗)が書かれています。例えば、 であるとき、このボードは次のようになります。
入力
唯一の行には2個の整数 が与えられる、これらはボードの行と列の数である。
出力
1個の整数を出力せよ、その数とはボード上の相異なる整数の数である。
入出力例
3 3
7
2 4
5
4 2
6
注記
問題文には、1つ目のテストケースでのボードが示されています。このケースでは の 個の相異なる整数が書かれています。
2つ目のテストケースでは、ボードは次のようになります。
3つ目のテストケースでは、ボードは次のようになります。
F. Playing Around the Table / Игра вокруг стола (3000点)
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
から までの整数が1つ書かれているカードが 枚あります。 から までの各整数について、ちょうど 枚のカードにこの数が書かれています。
始めに、各プレイヤーがちょうど 枚のカードを持っているように、カードがプレイヤーに分配されます。1ステップで各プレイヤーは自分のカードを1枚選び、右側のプレイヤーに渡します。全プレイヤーが同時にこのステップを実行します。
プレイヤー が持っている全てのカードに整数 が書かれている場合、そのプレイヤーはsolidであるといいます。プレイヤーの目的は、全員がsolidであるカード配置にすることです。 回以内の操作で実現できる方法を求めて下さい。操作数を最小化する必要はありません。
入力
1行目には1個の整数 が与えられる。
それから 行が続く。その 行目には 個の整数 が与えられる、これらは 番目のプレイヤーの初期カードである。
から までの各整数 について、数 が書かれたカードがちょうど 枚あることは保証されている。
出力
1行目には、1個の整数 を出力せよ、これは操作数である。
その後、 行を続けよ。その 行目には 個の整数 を出力せよ。ここで、 は 番目のプレイヤーが右隣のプレイヤーに渡したカードに書かれている数字である。
与えられた制約の中で、必ず答えが存在することを示すことはできる。複数の解がある場合は、いずれかを出力せよ。
入出力例
2 2 1 1 2
1 2 1
3 1 1 1 2 2 2 3 3 3
6 1 2 3 3 1 2 2 3 1 1 2 3 3 1 2 2 3 1
注記
1つ目のテストケースでは、1番目のプレイヤーが数 のカードを、2番目のプレイヤーが数 のカードをパスすると、1番目のプレイヤーは数 のカードを2枚、2番目のプレイヤーは数 のカードを2枚持っていることになります。そして、この操作を行った後、両プレイヤーはsolidとなります。
2つ目のテストケースでは、 回の操作で十分です。操作回数を最小化する必要はないことに注意してください。
*1:西[lwis]、ルイス: 高地ゲルマン語のHlūtwīg(名高い戦い)に由来する名前、Lewis(英)、Louis(仏)、Luigi(伊)、Ludwig(独)等と同語源