AtCoder振り返り：167(A～D)

結果を振り返ります。

試験結果

AB2問の2完です。
久々の2完、、、Cがかなり難しいと思ってしまい解けませんでした。
逆に3問目は簡単だったので比較的簡単にACできました。（時間切れでしたが）

意固地になって3問目を解こうとしたのが良くなかったですね。
あきらめて問題を飛ばすことも大事です。。。

成績

以下の通りレートが下がりました。当然ですね。

茶色がまた遠のく。。。
ただパフォーマンスが思ったより低くなかったので一発ACが良かったんだと思います。

問題

問1 Registration

atcoder.jp

文字列の比較処理です。
入力例2がなんでだめなのか10分くらい分からなくて時間が掛かってしまいました。
「"snekee" は "snuke" の末尾に英小文字を文字追加して得られる文字列ではありません。」
がなぜかどっちも同じに見えてしまった。だけ
atcoder.jp

■回答コード

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		try (Scanner scn = new Scanner(System.in)) {
			String S = scn.next();
			String T = scn.next();
 
			if(S.equals(T.substring(0, S.length()))) {
				System.out.println("Yes");
			} else {
				System.out.println("No");
			}
 
		}
	}
}

問2 Easy Linear Programming

atcoder.jp

引数Aの数が+1, 引数Bは何もしない、引数Cの数だけ-1する処理です。
この問題ですが正直なところCの数は気にしなくていいです。
C = K - A - B なので、KからAとBの引数引いて余った数を引けばOKです。

■回答コード

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		try (Scanner scn = new Scanner(System.in)) {
			int A = scn.nextInt();
			int B = scn.nextInt();
			int C = scn.nextInt();
			int K = scn.nextInt();
 
			int result = 0;
			boolean flg = false;
 
			if(K <= A) {
				result = K;
				flg = true;
			} else {
				result = A;
				K -= A;
			}
 
			if(!flg) {
				if(K <= B) {
					flg = true;
				} else {
					K -= B;
					result = result - K;
				}
			}
			System.out.println(result);
		}
	}
}

問3 Skill up

atcoder.jp

解けなかった問題です。

まず問題としてはN個の参考書からM個のアルゴリズムを学ぶとき、
縦列で合算した値がX値を超える組み合わせの中で最小の価格を求めるという問題です。

これ計算量大変じゃないか？と思ったのですが1 ≦ N, M ≦ 12 なのでその点は心配なさそうでした。
解説でも「決まった解法はなく全探索をするしかない」と仰っており、2^12なので最大4096回の処理にしかならないそうです。

また全探索に当たって、各購入する本は買う/買わない(0/1)で管理できます。
そして3冊の本を購入する組み合わせを見た時

000 (ABCすべての本を購入しない)
001(Aの本のみ購入)
010(Bの本のみ購入)
011(ABの本を購入)
100(Cの本のみ購入)
101(ACの本を購入)
110(ABの本を購入)
111(ABCの本を購入)

上記のようにビット符号で購入した・しなかったの考慮して計算を組むと以下の通りとなりました
※ビット符号が再起処理になっていますが絶対もっと簡単な方法があると思います。

■回答コード

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try (Scanner scn = new Scanner(System.in)) {
			int N = scn.nextInt();
			int M = scn.nextInt();
			int X = scn.nextInt();

			int[][] algorism = new int[12][13];
			int[] bitflg = new int[12];
			List<Integer> list = new ArrayList<Integer>();

			//initialize
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < M+1; j++) {
					algorism[i][j] = scn.nextInt();
				}
			}

			int result = 99999999;
			int cost = 0;
			int roop = (int) Math.pow(2, N);
			//2^N回（最大4096回)繰り返す
			for(int i = 0; i < roop; i++) {
				int[] realize = new int[M];
				for(int j = 0; j < N; j++) {
					if(bitflg[j] == 1) {
						cost += algorism[j][0];
						for(int k = 0; k < M; k++) {
							realize[k] += algorism[j][k+1];
						}
					}
				}
				boolean flg = true;
				for(int k = 0; k < M; k++) {
					if(realize[k] < X) flg = false;
				}
				if(flg) {
					result = (int) Math.min(cost, result);
				}
				cost = 0;
				bitCalc(bitflg, 0, N);
			}
			if(result == 99999999) {
				System.out.println(-1);
			} else {
				System.out.println(result);
			}
		}
	}

	//ビット計算
	public static void bitCalc(int[] bitflg, int idx, int idxMax) {
		if(idx == idxMax) return;
		if(bitflg[idx] == 0) {
			bitflg[idx] = 1;
		} else {
			bitflg[idx] = 0;
			bitCalc(bitflg, idx+1, idxMax);
		}
	}
}

問4 Teleporter

atcoder.jp

これは解けました。

1 ≦ N ≦ 2×10⁵ の数だけある街の中で、
1 ≦ K ≦ 10^18 回次から次へ町を移動したとき最終的にたどり着く場所は何処なのか。という問題です。
各町に設置された番号は次の街を示す（＝ポインタ）問題ですが、
10^18回単純にループ処理をするとTLEとなります。

ただ、膨大なテレポート回数に対して Nは20万しかなく最終的に循環参照が発生します。
つまり、循環の開始から終了までの回数を K回から割ってやれば不要なループ処理が省略できます。
後は割ったあまりをテレポートした結果を出力すれば求まります。

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		try (Scanner scn = new Scanner(System.in)) {
			int N = scn.nextInt();
			long K = scn.nextLong();
			int[] A =  new int[N];
			int[] flg = new int[N];
 
			for(int i = 0; i < N; i++) {
				A[i] = scn.nextInt();
			}
 
			int cnt = 0;
			int next = 1;
			int prev = -1;
			for(int i = 0; i < K; i++) {
				flg[next-1]++;
				prev = next;
				next = A[next-1];
				cnt++;
				if(flg[next-1] == 2) {
					break;
				}
			}
 
			if(cnt == K) {
				System.out.println(next);
				System.exit(0);
			}
			//循環成立
			long tmp = 0;
			for(int i = 0; i < N; i++) {
				if (flg[i] == 2) tmp++;
			}
 
			long tmpK = (K - (long) cnt) % tmp;
 
			for(int i = 0; i < tmpK; i++) {
				flg[next-1]++;
				prev = next;
				next = A[next-1];
			}
			System.out.println(next);
		}
	}
}

解説
今回AtCoderの方は別件で忙しいとのことでPDFはなくyoutubeでの配信のみです。
www.youtube.com