差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン
前のリビジョン
次のリビジョン両方とも次のリビジョン
programming_algorithm:contest_history:atcoder:2019:0112_aising2019 [2019/01/12] ikatakosprogramming_algorithm:contest_history:atcoder:2019:0112_aising2019 [2019/01/13] ikatakos
行 1: 行 1:
-======AISing Programming Contest 2019 参加記録======+======AISing Programming Contest 2019 C,D問題メモ======
  
 [[https://beta.atcoder.jp/contests/aising2019|AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019]] [[https://beta.atcoder.jp/contests/aising2019|AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019]]
- 
  
 ===== C - Alternating Path ===== ===== C - Alternating Path =====
行 13: 行 12:
   * 各マスは白か黒に塗られていて、各マスの色は入力として与えられる   * 各マスは白か黒に塗られていて、各マスの色は入力として与えられる
   * 白と黒を交互に踏んで上下左右に移動したい   * 白と黒を交互に踏んで上下左右に移動したい
-  * そのよう移動で行き来できる(黒マス, 白マス)の組の個数を答えよ+  * そのよう移動できる(黒マス, 白マス)の組の個数を答えよ
   * $1 \le H,W \le 400$   * $1 \le H,W \le 400$
  
行 25: 行 24:
   □□■□    □□■□   □□■□    □□■□
  
-その中で(黒マス、白マス)の組の個数は、「黒マスの個数×白マスの個数」となる。+その中で条件を満たす(黒マス、白マス)の組の個数は、「黒マスの個数×白マスの個数」となる。 
 + 
 +左上から順に1マスずつ見ていき、まだ未探索のマスがあれば、そこから探索を開始する。黒・白マスの数を数えながら行けるところまで行き、それ以上どこにも行けなくなったら黒の数×白の数を答えに加算する。
  
 一度探索したマスはそれ以降調べる必要は無い。 一度探索したマスはそれ以降調べる必要は無い。
行 34: 行 35:
   □□■□    □□■□   □□■□    □□■□
  
-経路探索でよく使う「このマスは訪れたか?」のフラグ配列を、全探索で共有すればよい。これによって、十分間に合うようになる。+経路探索で使う「このマスは訪れたか?」のフラグ配列を、全探索で共有すればよい。これによって、十分間に合うようになる。
  
 <sxh python> <sxh python>
行 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$ に近いカードを取る。同率の場合は小さい方を取る
行 152: 行 153:
 上の例を見ても分かるが、$A_i$ が小さい方から半分までのカードの中では、先手は、取るとしても大きい方から数えて奇数枚目のカードしか取らない(5,9を取り、3や7や11を取ることは無い)。取り方のルールから考えると、先手が半分以下のカードを取る時は、それより大きいカードが全て取られ、それ以下のカードが全て残っている状態だから。 上の例を見ても分かるが、$A_i$ が小さい方から半分までのカードの中では、先手は、取るとしても大きい方から数えて奇数枚目のカードしか取らない(5,9を取り、3や7や11を取ることは無い)。取り方のルールから考えると、先手が半分以下のカードを取る時は、それより大きいカードが全て取られ、それ以下のカードが全て残っている状態だから。
  
-なので、次に先手と後手で取るカードが入れ替わるのは、9と15である。その後、13と17、17と19と続く。要は$i$が、小さい方は1個飛ばし、大きい方は1つずつ進む+なので、次に先手と後手で取るカードが入れ替わるのは、9と15である。その後、13と17、17と19と続く。要は入れ替わるカードの $i$ が、数字の小さい方は2つずつ、大きい方は1つずつ大きくなる
  
 ==実装== ==実装==
  
-変数$tmp$を、現在の先手の合計とし、$x=1$の様に完全に2分された時のスコアで初期化する。+変数$tmp$を、現在の境界での先手の合計とし、$x=1$の様に完全に2分された時の先手の合計点で初期化する。 
 + 
 +クエリをソートしておく。その際、出力には元の順序が必要になるので、入力順は保持しておく。 
 + 
 +最初に入れ替わるカードを特定する。後手→先手になるカードのindexを$l$とすると、$N$ が奇数なら$l=0$、偶数なら$l=1$。先手→後手になるカードのindexを$r$とすると、$r=\frac{N}{2}$。 
 + 
 +境界を小さい方から1つ確定する。$\frac{A_l+A_r}{2}$ となる。$x$がこの値以下だと、先手の合計点は現在の$tmp$となる。
  
-クエリをソートする。+ソートしたクエリ配列で、境界以下の$X_i$持つクエリまでポインタを進め(逆順ソート+pop()で実装)、それらのクエリの答えを$tmp$で確定する。その後、入れ替わるカードの値に基づいて $tmp$ を更新する。$tmp = tmp + A_l - A_r$
  
-境界小さい方から1つずつ確定する毎に境界以下の$X_i$を持つクエリまでポインタを進め(逆順ソート+pop()で実装)それらのクエリの答えを$tmp$で確定る。その後、$tmp$を更新する+$l$ 2、$r$ を1加算し、$l=rになる直前ま繰り返す。
  
 最後まで残ったクエリは、$x=21$の様に完全に交互になる。 最後まで残ったクエリは、$x=21$の様に完全に交互になる。
programming_algorithm/contest_history/atcoder/2019/0112_aising2019.txt · 最終更新: 2019/02/05 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0