ABC107記録 - 文学徒が競プロをするブログ

いつもはこんなに難しくない(INF回言ってる)

お疲れ様でした。

A問題: Train

System.out.println(n-i+1);

これを書けば終わります。テストに少し時間を使いました。Sample Case Tester が使用できないの、非常に苦しいですね。

B問題: Grid Compression

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

public class Main {

  public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	int n = scan.nextInt();
	int m = scan.nextInt(); scan.nextLine();
	boolean[] g = new boolean[n];
	boolean[] r = new boolean[m];
	Arrays.fill(g, false);
	Arrays.fill(r, false);

        //入力
	char[][] a = new char[n][m];
	for (int i = 0; i < n; i++) {
		String A = scan.nextLine();
		for (int j = 0; j < m; j++) {
			a[i][j] = A.charAt(j);
		}
	}

        //白の行をfalseにする
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (a[i][j] == '#') {
				g[i] = true;
			}
		}
	}

        //白の列をfalseにする
	for (int j = 0; j < m; j++) {
		for (int i = 0; i < n; i++) {
			if (a[i][j] == '#') {
				r[j] = true;
			}
		}
	}

        //白の行、列に来たら出力を飛ばす
	for (int i = 0; i < n; i++) {
		if (!g[i]) continue;
		for (int j = 0; j < m; j++) {
			if (!r[j]) continue;
			System.out.print(a[i][j]);
		}
		System.out.println("");
	}
    }
}

実装が明らかにつらい。これをコンテストのプレッシャーの中で解けたのは成長かなと思います(終わった後Twitter見たら皆苦しんでて少し安心した)。B問題をいくらか埋めた知見によれば、" . " と " # " を使用した文字列操作は大体しんどいです(e.g. ABC054B, ABC075B)。
七転八倒の末に練成されたコードのため、非常に汚くなっています。申し訳ありません。

さて何をしているのかというと、行に" # "があるかを判定するboolean配列g と、列に" # "があるかを判定するboolean配列r を用意し、それぞれの行と列に" # "が含まれているかどうかをチェックしています。そして出力の際にそれらを参照し、falseだった場合はcontinueを用いて描画を飛ばすように実装しました。

この実装は完全に思い付きだったので、動いた時の安堵感は確実に今年一番だったと思います。入力の時に処理を色々飛ばしてみたりと試行錯誤甚だしく、1完爆死が脳裏にチラついて変な汗がダラダラ出ていました。

ちなみに今更類題を思い出したのですが、ABC036のB問題が近い処理を行っています。たまたま今日解いたのに何故今まで忘れていたのか……！

そしてここで45分を溶かしたために、C問題の時間が足りないという悲劇が起きました。

C問題

Dがアなので実質最終問題。
私の思考の変遷をざっくり説明すると、

①絶対値順で昇順ソートして貪欲はどうか→サンプルからもわかる通り、自明にダメ。

②これ全探索だと思うんだけど、ひょっとしてnPkですか？？？？→　そ　ん　な　わ　け　あ　る　か

③連続している時が最小なので、配列の要素が正負にまたがっていなければ答えはO(1)で出る

④配列の要素が正負にまたがっている場合、正の数の方へ行った場合と負の数の方へ行った場合をそれぞれ探索し、小さい方を選ぶ

⑤④以外の領域も探索する必要がありますねこいつァ……

時　間　切　れ

死にたい。

死んだ目でTLを観察してみると、「連続するK個の要素を探索すれば良い」という文字列が流れていて、それはそうという気持ちになります。
サクッと書いてみると、以下のようになりました。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	int n = scan.nextInt();
	int k = scan.nextInt();
	int[] x = new int[n];
	for (int i = 0; i < n; i++) {
		x[i] = scan.nextInt();
	}
	int min = Integer.MAX_VALUE/10;
	
	if (x[0] >= 0) {
		System.out.println(x[k-1]);
		return;
	}
	if (x[n-1] < 0) {
		System.out.println(Math.abs(x[n-k]));
		return;
	}
	
	for (int i = 0; i <= n-k; i++) {
		if (x[i+k-1] < 0) {
			int ans = Math.abs(x[i]);
			if (ans < min) min = ans;
		}
		else if (x[i] < 0 && x[i+k-1] >= 0) {
			int ans1 = Math.abs(x[i])*2 + x[i+k-1];
			int ans2 = x[i+k-1]*2 + Math.abs(x[i]);
			int ans = Math.min(ans1, ans2);
			if (ans < min) min = ans;
		}
		else if (0 <= x[i]) {
			int ans = x[i+k-1];
			if (ans < min) min = ans;
		}
	}
	System.out.println(min);
    }
}

サンプルも全ACなので、これで通るやろと胸を張って提出。

f:id:sarashina-nikki65:20180826014632p:plain

親の顔より見た光景

つらくなったので解説を見ます。

• l → r の順に訪れる場合: |xl| + |xr − xl|
• r → l の順に訪れる場合: |xr| + |xr − xl|
連続する K 本のろうそくを選ぶ方法を全探索し，この値の最小値を求めれば，それが答えです．

それは、そう！

ということで実装しました。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	int n = scan.nextInt();
	int k = scan.nextInt();
	int[] x = new int[n];
	for (int i = 0; i < n; i++) {
		x[i] = scan.nextInt();
	}
	int min = Integer.MAX_VALUE/10;

	if (x[0] >= 0) {
		System.out.println(x[k-1]);
		return;
	}
	if (x[n-1] < 0) {
		System.out.println(Math.abs(x[n-k]));
		return;
	}

	for (int i = 0; i <= n-k; i++) {
		int ans1 = Math.abs(x[i]) + Math.abs(x[i+k-1]-x[i]);
		int ans2 = Math.abs(x[i+k-1]) + Math.abs(x[i+k-1]-x[i]);
		int ans = Math.min(ans1, ans2);
		if (ans < min) min = ans;
	}
	System.out.println(min);
    }
}