差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2019:0504_agc033 [2019/05/10] – ikatakos | programming_algorithm:contest_history:atcoder:2019:0504_agc033 [2019/05/10] (現在) – [問題] ikatakos | ||
|---|---|---|---|
| 行 116: | 行 116: | ||
| * $N$ 個の点で等分された円周 | * $N$ 個の点で等分された円周 | ||
| * 長さ $M$ の、' | * 長さ $M$ の、' | ||
| - | * 隣り合う点と点に挟まれた円弧を「1区間」とし、各区間を赤か青で塗り分ける | + | * 隣り合う点と点に挟まれた円弧を「1区間」とし、各区間を赤か青で塗る |
| * $2^N$ 通りの塗り方の内、以下の条件を満たすものの個数を求めよ | * $2^N$ 通りの塗り方の内、以下の条件を満たすものの個数を求めよ | ||
| * 円周上の $N$ 個の点を1つ選び、そこから出発する | * 円周上の $N$ 個の点を1つ選び、そこから出発する | ||
| * 円周上で隣り合う点まで移動することを $M$ 回繰り返す。点では方向転換が可能 | * 円周上で隣り合う点まで移動することを $M$ 回繰り返す。点では方向転換が可能 | ||
| - | | + | * この時、どの点から出発しても、移動方向を上手く選ぶと $i$ 回目の移動で通る区間の色を $S_i$ が ' |
| - | | + | |
| * $2 \le N \le 2 \times 10^5$ | * $2 \le N \le 2 \times 10^5$ | ||
| * $1 \le M \le 2 \times 10^5$ | * $1 \le M \le 2 \times 10^5$ | ||
| 行 134: | 行 133: | ||
| ===説明のための特殊化=== | ===説明のための特殊化=== | ||
| - | ' | + | ' |
| ===制約=== | ===制約=== | ||
| 行 149: | 行 148: | ||
| <WRAP center round box> | <WRAP center round box> | ||
| ここで、$S$ が全て' | ここで、$S$ が全て' | ||
| - | この場合の数え上げは、フィボナッチ数列のようにしてできる。 | + | この場合の数え上げは、フィボナッチ数列のようにしてできる。直線上で考え、先頭と末尾がともに青にならないように注意する。 |
| 長さ | 長さ | ||
| 行 164: | 行 163: | ||
| $S$ に' | $S$ に' | ||
| - | （' | ||
| すると、連続する赤の個数にも制約が生じる。結論から言うと、奇数個でなければいけない。 | すると、連続する赤の個数にも制約が生じる。結論から言うと、奇数個でなければいけない。 | ||
| 行 184: | 行 182: | ||
| * 奇数個だった場合、奇数番号の点から出発するケース | * 奇数個だった場合、奇数番号の点から出発するケース | ||
| - | では、移動後に存在できるのが偶数番号の点であり、どうやっても1や3といった赤と青の境界に存在できない。 | + | では、移動後に存在できるのが偶数番号の点となり、どうやっても奇数番号の赤と青の境界に存在できない。 |
| $K$ が奇数個なら左右端で偶奇を選べるので、どの点から出発しても青に移行できる。 | $K$ が奇数個なら左右端で偶奇を選べるので、どの点から出発しても青に移行できる。 | ||
| 行 211: | 行 209: | ||
| ^連続できる赤|1|3|3|5|5|7|7|...|k/ | ^連続できる赤|1|3|3|5|5|7|7|...|k/ | ||
| - | また、2番目の条件「...→青→奇数個の赤→青→...」は、先ほどの偶奇を考えると、赤を端から端まで貫通する必要がある。 | + | また、2番目の条件「...→青→奇数個の赤→青→...」の移動は、先ほどの偶奇を考えると、赤を端から端まで貫通する必要がある。 |
| ' | ' | ||
| 行 219: | 行 217: | ||
| →→, | →→, | ||
| ←←' | ←←' | ||
| - | | + | |
| じゃあ、そういう、赤が長く連続する箇所を避けるように選択して移動できないかというと、無理。 | じゃあ、そういう、赤が長く連続する箇所を避けるように選択して移動できないかというと、無理。 | ||
| - | 実はあんまり移動の自由度がなくて、' | + | 実はあんまり移動の自由度がなくて、' |
| 出発点を決定した時点で、「$i$ 回目の移動後には、この連続する赤/ | 出発点を決定した時点で、「$i$ 回目の移動後には、この連続する赤/ | ||
| 行 236: | 行 234: | ||
| | | ||
| - | 赤が連続する区間は、どこかからの出発点で必ず通られる。 | + | 全ての赤が連続する区間は、どこかからの出発点で必ず通られる。 |
| よって、円周上で赤が連続する箇所は全て、$S$ 上で' | よって、円周上で赤が連続する箇所は全て、$S$ 上で' | ||
| 行 288: | 行 286: | ||
| $dp[N]$ まで埋めたら、回転のバリエーションを考える。本問題では、回転して同じになるものは区別する。 | $dp[N]$ まで埋めたら、回転のバリエーションを考える。本問題では、回転して同じになるものは区別する。 | ||
| - | 単純に直線を円周に当てはめる位置を $N$ 通りずらすので、$dp[N]$ を $N$ 倍すればよい、なんてことにはならず、 | + | 単純に直線を円周に当てはめる位置を $N$ 通りずらすので、$dp[N]$ を $N$ 倍すればよい...なんてことにはならず、 |
| 例えば「赤赤赤青赤赤赤青」などは半回転した結果が全く同じになるので、重複してしまう。 | 例えば「赤赤赤青赤赤赤青」などは半回転した結果が全く同じになるので、重複してしまう。 | ||
