差分
このページの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 | ||
|---|---|---|---|
| 行 134: | 行 134: | ||
| ===説明のための特殊化=== | ===説明のための特殊化=== | ||
| - | ' | + | ' |
| ===制約=== | ===制約=== | ||
| 行 149: | 行 149: | ||
| <WRAP center round box> | <WRAP center round box> | ||
| ここで、$S$ が全て' | ここで、$S$ が全て' | ||
| - | この場合の数え上げは、フィボナッチ数列のようにしてできる。 | + | この場合の数え上げは、フィボナッチ数列のようにしてできる。直線上で考え、先頭と末尾がともに青にならないように注意する。 |
| 長さ | 長さ | ||
| 行 184: | 行 184: | ||
| * 奇数個だった場合、奇数番号の点から出発するケース | * 奇数個だった場合、奇数番号の点から出発するケース | ||
| - | では、移動後に存在できるのが偶数番号の点であり、どうやっても1や3といった赤と青の境界に存在できない。 | + | では、移動後に存在できるのが偶数番号の点となり、どうやっても奇数番号の赤と青の境界に存在できない。 |
| $K$ が奇数個なら左右端で偶奇を選べるので、どの点から出発しても青に移行できる。 | $K$ が奇数個なら左右端で偶奇を選べるので、どの点から出発しても青に移行できる。 | ||
| 行 211: | 行 211: | ||
| ^連続できる赤|1|3|3|5|5|7|7|...|k/ | ^連続できる赤|1|3|3|5|5|7|7|...|k/ | ||
| - | また、2番目の条件「...→青→奇数個の赤→青→...」は、先ほどの偶奇を考えると、赤を端から端まで貫通する必要がある。 | + | また、2番目の条件「...→青→奇数個の赤→青→...」の移動は、先ほどの偶奇を考えると、赤を端から端まで貫通する必要がある。 |
| ' | ' | ||
| 行 219: | 行 219: | ||
| →→, | →→, | ||
| ←←' | ←←' | ||
| - | | + | |
| じゃあ、そういう、赤が長く連続する箇所を避けるように選択して移動できないかというと、無理。 | じゃあ、そういう、赤が長く連続する箇所を避けるように選択して移動できないかというと、無理。 | ||
| - | 実はあんまり移動の自由度がなくて、' | + | 実はあんまり移動の自由度がなくて、' |
| 出発点を決定した時点で、「$i$ 回目の移動後には、この連続する赤/ | 出発点を決定した時点で、「$i$ 回目の移動後には、この連続する赤/ | ||
| 行 236: | 行 236: | ||
| | | ||
| - | 赤が連続する区間は、どこかからの出発点で必ず通られる。 | + | 全ての赤が連続する区間は、どこかからの出発点で必ず通られる。 |
| よって、円周上で赤が連続する箇所は全て、$S$ 上で' | よって、円周上で赤が連続する箇所は全て、$S$ 上で' | ||
| 行 288: | 行 288: | ||
| $dp[N]$ まで埋めたら、回転のバリエーションを考える。本問題では、回転して同じになるものは区別する。 | $dp[N]$ まで埋めたら、回転のバリエーションを考える。本問題では、回転して同じになるものは区別する。 | ||
| - | 単純に直線を円周に当てはめる位置を $N$ 通りずらすので、$dp[N]$ を $N$ 倍すればよい、なんてことにはならず、 | + | 単純に直線を円周に当てはめる位置を $N$ 通りずらすので、$dp[N]$ を $N$ 倍すればよい...なんてことにはならず、 |
| 例えば「赤赤赤青赤赤赤青」などは半回転した結果が全く同じになるので、重複してしまう。 | 例えば「赤赤赤青赤赤赤青」などは半回転した結果が全く同じになるので、重複してしまう。 | ||
