【AtCoder】【C#】AtCoder Beginner Contest 179 - E - Sequence Sum

概要・Index

ABC179 - E問題で、数列の順関係の処理を実装する問題があったのですが、時間内に実装しきれなかったので反省します。

まず、考えなければいけないことは下記です。

1. 循環しているかどうかの確認
2. どこから循環しているのか
3. どれだけの長さ循環しているのか

特に、2, 3は重要です。このあたりをどう実装していくのかを考えていきたいと思います。

問題へのリンク

atcoder.jp

実装について

ポイント

まず、式のとおりに数列をすべて生成してもいいのですが、今回はN=10¹⁰です。そのまま実装するとTLEになってしまいます。なので、N個の数列を作らずに実装する方法を考える必要があることがわかります。

次に、各項は mod M の値となります。つまり、各項の取りうる値の最大値はM-1であることがわかります。

1. 循環しているかどうかの確認

循環しているかどうかを確認します。あくまで自分のやり方であって、他にやり方はあると思います。要素数M個の数列を作成し、各要素の出現回数を確認します。こうすることで、ある要素だけが繰り返し出現していることがわかります。

var count = new long[M];
var a_ = X;
array[0] = a_;
for (int i = 1; i < M; i++)
{
    a_ = (a_ * a_) % M;
    count[a_]++;
}

2. どこから循環しているのか

今回は、循環している部分数列のいて重複すうる要素がないという前提があります。(問題がそうなっているというだけ)つまり、数列の各値がすでに出現しているかどうかを確認して、すでに出現していたらその一つ前が循環の終わりです。今回は出現回数ではなく各値が何番目にでてきているのか確認する方法としています。この方があとで3を確認する時に楽だからです。

配列aが今回与えられた数列です。最初に数列を-1で初期化します。その後、各要素をが取り出し、何番目に配置されているのかlenを使い管理していきます。x_length[a[i]]が-1じゃない時、つまりすでに過去に出現していた場合は、そこが循環のスタート地点です。

var x_length = new long[M].Select(x => x = -1).ToArray();
var len = 0;
for (int i = 0; x_length[a[i]] == -1; i++)
{
    x_length[a[i]] = len;
    len++;
}

3. どれだけの長さ循環しているのか

では、循環している数列がどれぐらいの長さかというと下記で調べられます。

lenは数列のスタート地点から循環のスタート地点までの長さです。そこから、数列のスタート地点から循環の開始までの長さを引くと循環した数列の長さになります。

var cycle_length = len - x_length[a[len + 1]];

ここまでできれば準備が整ったので、問題を解くためのコードを書きます。

回答

残りの処理は下記リンクを参考にしてください。ACした回答のリンクを貼っておきます。 github.com

感想

Eでは循環はわかったのだが、実装までできなかったどんな情報が必要で、どう求めるのかふわっとしたまま実装すると爆死してしまうのでこういうときはちゃんと整理して実装したほうが良いなと思う。(多分100回ぐらい同じことを反省している。。)