AGC023 A, B - Hewlaの競プロ記

AtCoder Grand Contest 023です。僕の考えたことをゆっくり書いてます。

A - Zero-Sum Ranges

数列から二つ数字を選んだときにその間に並んでいる数字の和が0になる選び方はいくつありますかって感じの問題です。僕の解法を書いていきます。

愚直に実装すると、

始点のループ
- 終点のループ
  - 始点から終点までの和を計算するループ

となります。 $O(N^3)$ ですかね。わからない。まあとりあえず間に合わなさそうです。

こういう感じのやつって、何となく累積和を取りたい気持ちになります。整数の配列sumを用意したとき、sum[i]はa_iまでの和を表す、みたいな感じのが累積和です。問題文はa_0がないので、sum[0]は0としておきます。

じゃあこの累積和を使って何ができるでしょうか。
a_iからa_jまでの和はsum[j] - sum[i-1]であることから、a_iからa_jまでの和が0のとき、sum[i-1] == sum[j]です。
つぎに、これを満たすようなi, jの和を数えればよいです。
累積和をとった時にこのように部分列の和が計算できるのはよく使う気がします。

例えば入力例1では、sumの中身は

  a:    1  3 -4  2  2 -2
sum: 0  1  4  0  2  4  2

という感じになります。
sumには3組同じ数字のペアができていて、この数は答えと一致しています。

しかし、いくつペアがあるかを

int ans = 0;
for(int i = 0; i <= n-1; i++){
    for(int j = i+1; j <= n; j++){
        if(sum[i] == sum[j]){
            ans++;
        }
    }
}

という感じでループして調べようとすると、これは $O(N^2)$ となって間に合いません。

同じ数字のペアがいくつあるかを調べたいので、同じ数を集めてやることができれば数えやすくて幸せになれそうです。ソートをします。
mapとかを使ってやるのも手です。
入力例1では、

sum: 0  0  1  2  2  4  4

となります。これだと、連続する2数を調べて等しければans++とすればいいような気になりますが、それは正しくありません。たとえば3つの数が連続している時、組み合わせの数は3つあります。
同じ数字がm個連続しているとき、そのm個からできうるペアの数は
$_m C _2 = \frac{1}{2}m(m-1)$
となります。連続している数からこれを計算し、答えとする変数にたしてゆけばよいです。

以下僕の汚いコードです。
入力を0-indexedで受け取ったので些かややこしいです。
和はintの範囲を超える可能性があるので気をつけました。

▶A問題のコード

const long LINF = 1123456789012345678;

long n;
long a[200005];
long sum[200005];

int main(){
	scanf("%ld", &n);
	for(int i = 0; i < n; i++){
		scanf("%ld", &a[i]);
	}
	sum[0] = a[0];
	for(int i = 1; i < n; i++){
		sum[i] = sum[i-1] + a[i];
	}
	sum[n] = 0;
	std::sort(sum, sum+n+1);
	sum[n+1] = LINF;
	long ans = 0;
	long cnt = 1;
	for(int i = 1; i <= n+1; i++){
		if(sum[i] == sum[i-1]){
			cnt++;
		}else{
			ans += cnt * (cnt - 1) / 2;
			cnt = 1;
		}
	}
	printf("%ld\n", ans);
	return 0;
}

B - Find Symmetries

日本語が難しかったです。結構誤読しました。
正方形のマス目にアルファベットが書いてあります。
f:id:hewla:20180428234640p:plain
この図はそのマス目を表しています。マス目のうち１つを選んで、それが点(0, 0)に来るように平行移動します。その結果できたアルファベットの並び方が上図の赤い線を軸として対称になるようなマス目の選び方は何通りあるかという問題です。

愚直に実装した場合どうなるでしょうか。平行移動をする基準の点を探すのに $O(N^2)$ 、平行移動したときにそれが対称になっているかどうかを確かめるのに $O(N^2)$ ですので、合わせて $O(N^4)$ です。 $300^4 = 81\times10^8$ なので間に合わなさそうです。

ここで一つ閃きですが、(a, b)の移動がよい盤面を作るのならば、(a+x, b+x)の移動もよい盤面をつくるという事実があります。
ちょっと説明をします。
今、うまく対称になっている盤面があるとします。
マス目(1, 1)を選んで(0, 0)に移動させたとき、これも対称になります。それぞれのアルファベットの軸に対する位置関係は変わらず、軸に対して平行に移動するからです。
そうすると、(0, 3)が適しているならば、(1, 4)も適しているはずで、以降同様に緑色の線の上のN個のマス目は全て適しているということができます。
f:id:hewla:20180429000128p:plain

それなら、(0, 0)から(0, n-1)まで一番上の列について調べ、適しているならば答えにNを足せばよさそうです。
点の選び方が $O(N^2)$ から $O(N)$ に変わったので、あわせて $O(N^3)$ 、これで間に合います。

以下コードです。割と綺麗に書けたつもりです。関数に飛ばすの好き

▶B問題のコード

int n;
char s[305][305];
int ans = 0;

bool check(int j){
	for(int k = 0; k < n; k++){
		for(int l = j; l < n+j; l++){
			if(s[k][l%n] != s[l-j][(k+j)%n]){
				return false;
			}
		}
	}
	return true;
}

int main(){
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		scanf("%s", s[i]);
	}
	for(int j = 0; j < n; j++){
		if(check(j)){
			ans += n;
		}
	}
	printf("%d\n", ans);
	return 0;
}

感想

なんだか今日はうまくいきました。
perf:2129, レート+97で1515, Highestです！幸せ
f:id:hewla:20180429000743p:plain
ちなみにC問題はわかる気がしなかったので撤退しました。

説明下手くそで恐縮ですがやってればそのうちだんだん上手になると思います。思いたいだけです。
コンテストのたびに書いたり書かなかったりしますが、よろしくお願いします。