差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2019:0112_aising2019 [2019/01/13] – ikatakos | programming_algorithm:contest_history:atcoder:2019:0112_aising2019 [2019/01/13] – ikatakos | ||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ======AISing Programming Contest 2019 参加記録====== | + | ======AISing Programming Contest 2019 C, |
| [[https:// | [[https:// | ||
| - | |||
| ===== C - Alternating Path ===== | ===== C - Alternating Path ===== | ||
| 行 26: | 行 25: | ||
| その中で条件を満たす（黒マス、白マス）の組の個数は、「黒マスの個数×白マスの個数」となる。 | その中で条件を満たす（黒マス、白マス）の組の個数は、「黒マスの個数×白マスの個数」となる。 | ||
| + | |||
| + | 左上から順に1マスずつ見ていき、まだ未探索のマスがあれば、そこから探索を開始する。黒・白マスの数を数えながら行けるところまで行き、それ以上どこにも行けなくなったら黒の数×白の数を答えに加算する。 | ||
| 一度探索したマスはそれ以降調べる必要は無い。 | 一度探索したマスはそれ以降調べる必要は無い。 | ||
| 行 88: | 行 89: | ||
| * 互いに異なる整数 $A_1 \lt A_2 \lt ... \lt A_N$ が書かれた $N$ 枚のカードが場にある | * 互いに異なる整数 $A_1 \lt A_2 \lt ... \lt A_N$ が書かれた $N$ 枚のカードが場にある | ||
| - | * 先手と後手の2人がゲームをする | + | * 先手と後手の2人が順にカードを取っていく |
| - | * 開始前に後手は、ある整数 $x$ を決める | + | * 開始前に、ある整数 $x$ を決める |
| * 先手は、その時に場にある最も大きいカードを取る | * 先手は、その時に場にある最も大きいカードを取る | ||
| * 後手は、その時に場にある最も $x$ に近いカードを取る。同率の場合は小さい方を取る | * 後手は、その時に場にある最も $x$ に近いカードを取る。同率の場合は小さい方を取る | ||
| 行 156: | 行 157: | ||
| ==実装== | ==実装== | ||
| - | 変数$tmp$を、現在の境界での先手の合計とし、$x=1$の様に完全に2分された時のスコアで初期化する。 | + | 変数$tmp$を、現在の境界での先手の合計とし、$x=1$の様に完全に2分された時の先手の合計点で初期化する。 |
| クエリをソートしておく。その際、出力には元の順序が必要になるので、入力順は保持しておく。 | クエリをソートしておく。その際、出力には元の順序が必要になるので、入力順は保持しておく。 | ||
| 行 165: | 行 166: | ||
| ソートしたクエリ配列で、境界以下の$X_i$を持つクエリまでポインタを進め（逆順ソート+pop()で実装）、それらのクエリの答えを$tmp$で確定する。その後、入れ替わるカードの値に基づいて $tmp$ を更新する。$tmp = tmp + A_l - A_r$ | ソートしたクエリ配列で、境界以下の$X_i$を持つクエリまでポインタを進め（逆順ソート+pop()で実装）、それらのクエリの答えを$tmp$で確定する。その後、入れ替わるカードの値に基づいて $tmp$ を更新する。$tmp = tmp + A_l - A_r$ | ||
| + | |||
| + | $l$ を2、$r$ を1加算し、$l=r$ になる直前まで繰り返す。 | ||
| 最後まで残ったクエリは、$x=21$の様に完全に交互になる。 | 最後まで残ったクエリは、$x=21$の様に完全に交互になる。 | ||
