こんにちは、Habr！ MIPT IT教育開発センターは、国際学生スポーツプログラミングチャンピオンシップであるMosCode Festivalにあなたを招待します。 これは、ACM ICPC最終レベルのタスクを他国の参加者と一緒に練習する良い機会です。 このコンテストは、3月31日（個人ツアー）と4月1日（チームツアー）にSkolkovoテクノロジーパークで開催されます。 オンライン選択は、2月11日の次の日曜日、モスクワ時間の11:00に行われます。 登録について考えている間に、詳細をお知らせし、昨年の2つのタスクを分析で共有します。
MosCode Festival、以前はモスクワ・スポーツ・プログラミング・カップ・オブ・スポーツとして知られていた I.N. Vekuaは、オリンピアードプログラミングの世界で重要なイベントです。 昨年、オーストラリア、日本、スペインのチームが初めて参加したなど、19か国から200人がこのフェスティバルに参加しました。 今年は40か国から360人の学生が期待されています。 現在、カナダ、インド、イギリス、中国、ブラジルのチームが参加を申請しています。
ウォームアップ。
「点と長方形のあるもの」タスク
「フィールドで遊ぶ」タスク
「点と長方形のあるもの」タスク
入力ファイル名 ：標準入力
出力ファイル名 ：標準出力
制限時間： 3秒
メモリ制限 ：256メガバイト
平面上に、整数座標を持つn個の異なる点のセットが与えられます。 角度が整数座標を持つ点にあり、境界内および境界にある整数座標を持つすべての点がこのセットに属する場合、矩形をgoodと呼びます。 さらに、このような長方形は縮退することもあります（面積がゼロ）。 各ポイントについて、それが属する適切な長方形の数を見つける必要があります。
入力形式
最初の行には、数n（1≤n≤10 ^ 5）-ポイント数が含まれます。 次の行には、ポイントの座標が含まれています（−10 ^ 5⩽xi、yi⩽10 ^ 5）
出力形式
n行を印刷します。 i番目の行には、i番目のポイントを含む適切な長方形の数が含まれている必要があります。
例
| 標準入力 | 標準出力 |
|---|---|
| 4
-1 -1 -1 -2 -2 -1 -2 -2 | 4
4 4 4 |
| 8
1 1 1 2 1 3 2 1 2 3 3 1 3 2 3 3 | 5
4 5 4 4 5 4 5 |
「点と長方形のあるもの」問題の分析
Oの素朴な解決策（n ^ 3）長方形の2つの反対側のコーナーをソートし、それが適切であることを確認します。 良ければ、各ポイントについて、それがこの長方形に属しているかどうかをチェックします。 属している場合は、ポイントの答えを1つ増やします。
解決策はO（n ^ 2）です。簡単に言うと、セット内のポイントから任意の水平セグメントを反復処理し、その辺の長さに等しい辺を持つ長方形の数をカウントします。
まず、O（nlogn）の場合、上部、下部、および右側の隣接点から直接ではなく、各ポイントについて計算します。 次に、線についてtoright [i] = 1 + i番目の点の右側の行の点の数を考慮します。
セグメントlenの長さをソートします。 各ポイントのラインアップ[i]とダウン[i]をカウントします。toright[i] <len up [i] = 1 + toright [i]> = lenで上から行のポイント数、それ以外の場合はdown [i]以下の点についても同様です。 次に、i番目の点から始まる長さlenの水平セグメントは、辺lenを持つ上[i] *下[i]の長方形にあります。 セグメント上のすべてのポイントの回答を再計算する方法は？ （y、x）でソートされたポイントを保存し、接頭辞の合計を使用して行に追加します。
Oのソリューション（n√n）以前のソリューションを変更します。 水平方向だけでなく、垂直方向のセグメントも整理します。 ただし、同時に、長さが長方形の大きい辺と一致するセグメントを考慮しないでください。 したがって、√nを超える長さのセグメントを整理する必要はなく、さらに、正方形を2回カウントする必要もありません。 これは、最初に水平セグメントで開始し、正方形をカウントしてから、垂直で開始し、正方形をカウントしないことで実行できます。
これにより、長方形の数の式が複雑になります。 辺が固定セグメント以上の長方形の数を数える必要があります。 したがって、ここでいくつかの数字をアップ、ダウン、カットし、整数のペア（i、j）の数をカウントする必要があります。ここで、1⩽i⩽アップ、1⩽j⩽ダウン、i + j>カット
cutを切り上げる場合、すべてのi =切り取り、..、切り上げに対して、任意のjが適切です。 （up-cut + 1）・答えに追加し、upを割り当てます：= cut-1そして、up <cut ∑up i = 1∑down 1（1、i + j> cut）= ∑up i = 1 max（0、down−（cut − i））= ∑up i = max（1、cut − down）（down − cut + i）
l =最大（1、カット-ダウン）、r =アップを示します。 l⩽rの場合、（r-l + 1）・（down-cut）+（r・（r + 1）/ 2-（l-1）・l / 2）を回答に追加する
解決策はO（n ^ 2）です。簡単に言うと、セット内のポイントから任意の水平セグメントを反復処理し、その辺の長さに等しい辺を持つ長方形の数をカウントします。
まず、O（nlogn）の場合、上部、下部、および右側の隣接点から直接ではなく、各ポイントについて計算します。 次に、線についてtoright [i] = 1 + i番目の点の右側の行の点の数を考慮します。
セグメントlenの長さをソートします。 各ポイントのラインアップ[i]とダウン[i]をカウントします。toright[i] <len up [i] = 1 + toright [i]> = lenで上から行のポイント数、それ以外の場合はdown [i]以下の点についても同様です。 次に、i番目の点から始まる長さlenの水平セグメントは、辺lenを持つ上[i] *下[i]の長方形にあります。 セグメント上のすべてのポイントの回答を再計算する方法は？ （y、x）でソートされたポイントを保存し、接頭辞の合計を使用して行に追加します。
Oのソリューション（n√n）以前のソリューションを変更します。 水平方向だけでなく、垂直方向のセグメントも整理します。 ただし、同時に、長さが長方形の大きい辺と一致するセグメントを考慮しないでください。 したがって、√nを超える長さのセグメントを整理する必要はなく、さらに、正方形を2回カウントする必要もありません。 これは、最初に水平セグメントで開始し、正方形をカウントしてから、垂直で開始し、正方形をカウントしないことで実行できます。
これにより、長方形の数の式が複雑になります。 辺が固定セグメント以上の長方形の数を数える必要があります。 したがって、ここでいくつかの数字をアップ、ダウン、カットし、整数のペア（i、j）の数をカウントする必要があります。ここで、1⩽i⩽アップ、1⩽j⩽ダウン、i + j>カット
cutを切り上げる場合、すべてのi =切り取り、..、切り上げに対して、任意のjが適切です。 （up-cut + 1）・答えに追加し、upを割り当てます：= cut-1そして、up <cut ∑up i = 1∑down 1（1、i + j> cut）= ∑up i = 1 max（0、down−（cut − i））= ∑up i = max（1、cut − down）（down − cut + i）
l =最大（1、カット-ダウン）、r =アップを示します。 l⩽rの場合、（r-l + 1）・（down-cut）+（r・（r + 1）/ 2-（l-1）・l / 2）を回答に追加する
「フィールドで遊ぶ」タスク
入力ファイル名 ：標準入力
出力ファイル名 ：標準出力
制限時間 ：1秒
メモリ制限 ：64 MB
イノセントは、次の面白いゲームをプレイすることにしました。Nx Mセル（高さ-Nセル、幅-Mセル）のフィールドがあるとします。 セル（x、y）をx番目の行とy番目の列のセルとします（行には上から下に番号が付けられ、列は左から右に番号が付けられます）。 最初は、セル（1、1）にSストーン（S> = 4）があり、これらのストーンをセル（N、M）に移動する必要があります。 ゲームは複数の動きに分けられ、各動きはフィールドの各セルから石の一部を上/右/下/左に移動し、一部をこのセルに残します、部分はゼロにすることができます（単一の石を含まないでください） ）、また、部品内の石の数の合計は、ケージ内の石の初期数と等しくなければなりません。また、石はフィールドの境界を越えることはできません。 イノセントがすべてのセルに同時に動きを適用することは注目に値します。
正式な規則 ：i行j列の移動の前に[i] [j]の石があり、このセルの移動石の規則が4つの数字で与えられているとします：b [i] [j] [0 ]、b [i] [j] [1]、b [i] [j] [2]、b [i] [j] [3]-セル（i、j）からセル（i -1、j）、（i、j + 1）、（i-1、j）、（i、j-1）それぞれ（b [i] [j] [0] + b [i] [j] [ 1] + b [i] [j] [2] + b [i] [j] [3] <= a [i] [j]）。 i行目に移動した後、j列目には[i] [j]の石があるとします
[i] [j] = a [i] [j]-（b [i] [j] [0] + b [i] [j] [1] + b [i] [j] [2] + b [i] [j] [3]）+ b [i + 1] [j] [0] + b [i] [j-1] [1] + b [i + 1] [j] [2] + b [i] [j + 1] [3]。 iについて、b [i] [j] [k] = 0であり、jはそれぞれ限界（1..N）および（1..M）を超えていると考えます。 ゲームは、このターンでb [N] [M]がSと等しくなり、この動きの後、動きが起こらないように、H以下の数の動きが存在する場合に勝ったと見なされます。
*移動には1番目からH番目までの番号が付けられます。
しかし、イノセントはすぐに、このゲームは彼にとって単純すぎることに気付きました。 そして、彼はゲームを複雑にするいくつかの制限を思いつきました。 まず、個々のセルごとにルールを設定する代わりに、セル内の可能な石の数ごとにルールを設定します。つまり、z（セル内の石の数）ごとに、4からなるルールを作成します。数字：d [z] [0]、d [z] [1]、d [z] [2]、d [z] [3]。 そして、各ターンで、石はすべてのi、j、kについて「公式ルールb [i] [j] [k] = d [a [i] [j]] [k]に従って移動します。 また、b [i] [j] [k] = 0、d [a [i] [j]] [k]に関係なく、データi、j、kの場合、b [i] [j]が行くセル[k]野外の石。
すぐにイノセントはゲームに飽き飽きし、そのような制限もあったので、彼はそのような戦略を考案することでこのゲームに対処したかった（つまり、d [z] [0]、d [z] [1]、d [z] [2] ]、d [z] [3]各z）、すべての可能なフィールド（つまり、すべてのN、M：1 <= N <= MAXN、1 <= M <= MAXM）でゲームに勝ちます。可能なすべての初期石量（つまり、すべてのS：4 <= S <= MAXS）。
入力形式
何も入力されていません。
出力形式
MAXS行を印刷します。i行目は、スペースで区切られた4つの数字で構成されます。d[i]] [0]、d [i] [1]、d [i] [2]、d [i] [3] 。 これらの行は、次のようなすべての初期データでゲームに勝つ戦略を説明する必要があります。
1 <= N <= MAXN
1 <= M <= MAXM
MAXN = MAXM = 50
4 <= S <= MAXS
MAXS = 100 H = 300
発言
可能な戦略の例：
すべてのiについて：d [i] [0] = 0、d [i] [1] = i、d [i] [2] = 0、d [i] [3] = 0、この戦略はすべての石の動きを設定します1セル右にあると、この戦略がすべての単一行フィールドで勝ち、他のすべてのフィールドで負けていることを理解するのは簡単です。
「フィールドでのゲーム」タスクの分析
この問題には、問題を解決するための2つの異なるアプローチがあります。
1.純粋に数学的なアプローチ-すべての条件を満足させる何らかの種類の戦略を考えています。 これらの戦略は非常にたくさんありますが、それらのほとんどには、個別に処理する必要がある多くの極端なケースがあります。 戦略の1つの例と、その発明に至った理由を以下に示します。
2.いくつかのカットオフを含む戦略の列挙と、ソリューションの正確性をチェックするテスターを作成します。 この場合、ソリューションは非常に高速であり、正しい戦略が保証されます。
コード ：
勝利戦略の例：
コード ：説明：zを特定のセルの石の数にします。 いくつかの考慮事項を考慮してください。
1. z⩾4の場合、石はこのセルから右および下にのみ移動できます。そうでない場合、S = zで、すべてのS石が右下のセルに残ることはありません。
2. z⩾4の場合、石のゼロ以外の部分は右に移動し、ゼロ以外の部分は下に移動する必要があります。そうでない場合、S = zで1からなるテーブルで負ける1行目、または1列目。
3.最初に左上のセルにある石の数が⩾4である場合、値1、2、3はいくつかの基本的な部分と見なすことができ、それを使用して大きな部分を分割します。
これらの考慮事項といくつかの仮定に基づいて、次の戦略を立てることができます。 石の主要部分（Tと呼びましょう）は下がり、各ターンでいくつかの基本的な部分をそれ自体から分離します。 1と2は完全に右に移動し、3は完全に下に移動します。戦略の考え方は、パーツ1と2をTから分離することであり、3をセルから下る右境界でのみ収集する必要があります。 。 z石で構成されるTを次のように分割します。
•主要部分は3石なしでダウンします。つまり、z-3石です。
•2つの石が右側に移動します。
•このセルには1つの石が残っています。
その後、ユニットとデュースは右側の境界線の3番目に集まるまで右側に移動します。 ただし、この戦略には欠陥があります。つまり、小さなzでは機能しません。 たとえば、このような戦略による6番目は2、1、3に分割され、3番目は下の境界線のままですが、4〜6の石の数を慎重に検討する必要があります。残りはベースパーツとパーツに分かれます⩾4。
その結果、次の戦略が得られます。
1.純粋に数学的なアプローチ-すべての条件を満足させる何らかの種類の戦略を考えています。 これらの戦略は非常にたくさんありますが、それらのほとんどには、個別に処理する必要がある多くの極端なケースがあります。 戦略の1つの例と、その発明に至った理由を以下に示します。
2.いくつかのカットオフを含む戦略の列挙と、ソリューションの正確性をチェックするテスターを作成します。 この場合、ソリューションは非常に高速であり、正しい戦略が保証されます。
コード ：
勝利戦略の例：
コード ：説明：zを特定のセルの石の数にします。 いくつかの考慮事項を考慮してください。
1. z⩾4の場合、石はこのセルから右および下にのみ移動できます。そうでない場合、S = zで、すべてのS石が右下のセルに残ることはありません。
2. z⩾4の場合、石のゼロ以外の部分は右に移動し、ゼロ以外の部分は下に移動する必要があります。そうでない場合、S = zで1からなるテーブルで負ける1行目、または1列目。
3.最初に左上のセルにある石の数が⩾4である場合、値1、2、3はいくつかの基本的な部分と見なすことができ、それを使用して大きな部分を分割します。
これらの考慮事項といくつかの仮定に基づいて、次の戦略を立てることができます。 石の主要部分（Tと呼びましょう）は下がり、各ターンでいくつかの基本的な部分をそれ自体から分離します。 1と2は完全に右に移動し、3は完全に下に移動します。戦略の考え方は、パーツ1と2をTから分離することであり、3をセルから下る右境界でのみ収集する必要があります。 。 z石で構成されるTを次のように分割します。
•主要部分は3石なしでダウンします。つまり、z-3石です。
•2つの石が右側に移動します。
•このセルには1つの石が残っています。
その後、ユニットとデュースは右側の境界線の3番目に集まるまで右側に移動します。 ただし、この戦略には欠陥があります。つまり、小さなzでは機能しません。 たとえば、このような戦略による6番目は2、1、3に分割され、3番目は下の境界線のままですが、4〜6の石の数を慎重に検討する必要があります。残りはベースパーツとパーツに分かれます⩾4。
その結果、次の戦略が得られます。
| 数量 | 右へ | ダウン |
|---|---|---|
| 1
2 3 4 5 6 z⩾7 | 1
2 0 2 1 2 2 | 0
0 3 1 2 2 z − 3 |