AtCoder Beginner Contest 103 を受けた結果 - ブログ名どうしようかな

競プロを始めて一ヶ月が経ち、今回で5回目の参加です。
10回受けると実力に近いレートになるらしいので、ようやく折り返し地点ですね。

結果から言うと、今回もB問題までしか解くことができませんでしたが、
今回のC問題はちょっと考えれば解ける問題だったのでかなり悔しかったです…！

A - Task Scheduling Problem

はじめは問題文と出力例を見ても、問題の意味が全く頭に入ってきませんでした。
10分くらい文章と睨めっこしたのち、やっと問題の意味を理解してコーディングに入れました。

要するに、A地点、B地点、C地点が一直線上にあるので、
最短距離ですべて通ってくださいという問題です。

例えば、AからあえてBをスルーしてCに向かい、CからBへと逆戻りするより、
順番にA→B、B→C（もしくはC→B、B→A）と移動する方が無駄がありません。

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int[] task = new int[3];
		task[0] = sc.nextInt();
		task[1] = sc.nextInt();
		task[2] = sc.nextInt();
		Arrays.sort(task);
		int cost = 0;
		for (int i = 1; i < 3; i++) {
			cost += task[i] - task[i - 1];
		}
		System.out.println(cost);

	}

}

ちなみに僕は、A→Bの距離とB→Cの距離の和を求めましたが、
解説では、それなら最初からA→Cの距離を求めるだけでいいよと教えてくれています。

B - String Rotation

文字列の並びを回転操作して、もう一方の文字列と同じにできるかという問題です。

以前違う記事でも書きましたが、僕は数学が全くできないので、
競プロの勉強の一貫として、高校数学の勉強もしています。

先週まで「場合の数」を勉強していたのですが、
今回の問題はまさに円順列の考え方だったので、A問題よりもスムーズに解くことができました。
~~「あ！ここチャート式でやった問題だ！」~~

N文字からなる円順列は、回転することで同じになる文字列がN個できます。
なのでN回（文字数）だけ回転操作を行えばよいです。

回転操作は、
①末尾の1文字を先頭に持ってくる。
②末尾の1文字を削除する。
で行うことができます。

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		StringBuilder S = new StringBuilder(sc.next());
		String T = sc.next();
		String ans = "No";
		for (int i = 0; i < S.length(); i++) {
			S.insert(0, S.substring(S.length() - 1));
			S.delete(S.length() - 1, S.length());
			if (S.toString().equals(T)) {
				ans = "Yes";
				break;
			}
		}
		System.out.println(ans);

	}

}

C - Modulo Summation

ある数を数列の各項で割ったとき、余りの合計は最大でいくつか、という問題です。

割り切れる数、つまり倍数だと余りは0になってしまいます。
なので、ある数というのは各項の最小公倍数より1小さい数のことです。

手順としては、
①最小公倍数を求める。
②「最小公倍数- 1」を数列の各項で割る。
③数列の「各項 - 1」の合計が求められる。

が考えられるので、必死こいて時間いっぱい、手順①の最小公倍数を探し、
結局見つけられないままコンテストは終了してしまいました。

なお、勘の良い人はみなさんお気づきでしょうが、この問題は①②の手順は飛ばして良いのです。
つまり、最初から③の処理を実行するのが正解です。

明後日の方向へ向かっていた

各項の最小公倍数の導き方がどうしても分からない僕は、
「そうだ！手当たり次第、1から順に試していこう！！」
と思ってしまいました。

「最小公倍数 - 1」が分からなくても、
1から順に試していけば、合計の最大値が一番大きかったときが、
それだったんだろうという考えです。

しかし、数列の数Nは全部で3,000個、各項の最大値は100,000、
つまり、計算量は、(3*10^3) * 10^5 = 3 * 10^8
実行に3秒掛かるので、制限時間2秒に間に合いません。

「なるほど！計算を工夫して2秒以内にしろということか！」
（違います）

まず、この方法だと、最小公倍数が「1から100,000」の範囲しか対応できません。
ですが、このときの僕は問題の意図を全力で勘違いしていたので、全く気づいていませんでした。

それで思いついたのが、
数列の各項を割る処理を中心から左右に向かって行う作戦です。

もし6つの要素の配列があったとき、
1番目の要素から6番目の要素まで順番に割っていくと、その操作は6回ですが、
中心にある3番目と4番目の要素からスタートして、
3番目は先頭へ下り、同時に4番目は末尾へ上がれば、その操作は半分の3回で済みます。

これにより、3000だったNを1500に減らすことができ、
(1.5 * 10^3) * 10^5 = 1,5 * 10^8
となり、約1,5秒で実行できるので、制限時間2秒以内を満たすことができます。

実装したけど提出するに満たなかったコード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) {

		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));) {
			int N = Integer.parseInt(br.readLine());
			String[] line = br.readLine().split(" ");
			int[] a = Arrays.stream(line).mapToInt(Integer::parseInt).toArray();
			long maxSum = 0;
			int left;
			int right;
			for (int i = 1; i <= 100000; i++) {
				long curSum = 0;
				if (N % 2 == 0) {// 偶数の場合
					left = N / 2 - 1;
					right = N / 2;
				} else { // 奇数の場合
					int center = N / 2;
					curSum += i % a[center];
					left = N / 2 - 1;
					right = N / 2 + 1;
				}
				for (; left >= 0 && right <= a.length - 1; left--, right++) {
					curSum += i % a[left];
					curSum += i % a[right];
				}
				maxSum = Math.max(maxSum, curSum);

			}
			System.out.println(maxSum);

		} catch (IOException e) {
			e.printStackTrace();
		}

	}

}

先述したとおり、最小公倍数が100,000以下のときしか対応していないので、
入力例3で出力例と違う答えになり、提出していません。

D - Islands War

D - Islands War
たどり着けませんでした。

最後に

相変わらず、C問題の壁を突破することができません。

ただ、今回は計算量を意識して工夫を凝らしてみたりなんかして、
（全くトンチンカンなことだったけれど）
これまでの5回の中では一番、手応えというか、試合になってるように感じられました。

あと、競プロを始めて一ヶ月経ったので、なにか総括的な記事を近いうちに書きたいと思います。

アディオス！