AtCoder Beginner Contest 092

A - Traveling Budget

ans = Math.min(a,b) + Math.min(c,d);

B - Chocolate

import static java.lang.System.*;
import java.util.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int n = sc.nextInt();
		int day = sc.nextInt();
		int x = sc.nextInt();
		
		int total = 0;
		for (int i=0; i<n; i++) {
			int a = sc.nextInt();
			if (day%a==0) {
				total += day/a;
			}
			else {
				total += day/a + 1;
			}
		}
		
		out.println(total+x);
	}
}

AをそれぞれDで割っていって、割り切れるならtotalにA/Dを足し、割り切れないならtotalに(A/D)+1を足します。N個のAを処理し終わったあと、totalにXを足したものが答えです。

C - Traveling Plan

import static java.lang.System.*;
import java.util.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int n = sc.nextInt();
		int[] ar = new int[n+2];
		ar[0] = 0;
		ar[n+1] = 0;
		
		int total = 0;
		for (int i=1; i<n+1; i++) {
			ar[i] = sc.nextInt();
			total += Math.abs(ar[i-1]-ar[i]);
		}
		total += Math.abs(ar[n]-ar[n+1]);
		
		for (int i=1; i<n+1; i++) {
			int a = Math.abs(ar[i-1]-ar[i+1]);
			int b = Math.abs(ar[i]-ar[i-1])+Math.abs(ar[i]-ar[i+1]);
			out.println(total+(a-b));
		}	
	}
}

長さN+2の配列arを用意して、ar[1]~ar[N]に入力を詰め込んだあと、ar[0]とar[N+1]に0を入れます。その後、ループでar[0]からar[N]まで回しながら、ar[i]とar[i+1]の絶対値を計算し、totalに加算していきます（この処理は入力を受け取るのを同時にできますね、いま気づきました）。

その後、ar[1]からar[N]まで順番に見ていって、
ar[i]に立ち寄らない場合（|ar[i-1]+ar[i+1|）から立ち寄る場合（|ar[i-1]-ar[i]| + |ar[i+1]-ar[i]|）を引いたものを、すべての地点に立ち寄る場合（total）に足し、出力すればよいです。

D - Grid Components

import static java.lang.System.*;
import java.util.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		//100*100の二次元配列を用意し、上半分を白、下半分を黒で塗りつぶす。
		char[][] map = new char[100][100];
		for (int i=0; i<100; i++) {
			for (int j=0; j<100; j++) {
				if (i<50) map[i][j] = '.';
				else map[i][j] = '#';
			}
		}
		
		//初期状態がすでにA=1,B=1なので、入力から1を引いてやり、余計なループを回さないようにする
		int a = sc.nextInt() - 1;
		int b = sc.nextInt() - 1;
		
		//下半分の黒の海のなかに、孤立した白い点を置いていくイメージ
		loop : for (int i=99; i>=0; i-=2) {
			for (int j=0; j<100; j+=2) {
				if (a==0) break loop;
				map[i][j] = '.';
				a--;
				if (a==0) break loop;
			}
		}
		
		//上半分の白の海のなかに、孤立した黒い点を置いていくイメージ
		loop : for (int i=0; i<100; i+=2) {
			for (int j=0; j<100; j+=2) {
				if (b==0) break loop;
				map[i][j] = '#';
				b--;
				if (b==0) break loop;
			}
		}
		
		//出力
		out.println(100+" "+100);
		for (int i=0; i<100; i++) {
			for (int j=0; j<100; j++) {
				out.print(map[i][j]);
			}
			out.println();
		}
	}
}

500点問題ですし、見た瞬間はキツそうだなと思いましたが、考え始めて5分くらいで上記の解法が思い浮かびました。

コード中のコメントにもある通り、グリッドの大きさは指定されていないので、最初から最大のもの（100*100）を使います。
最初に、上半分を白、下半分を黒で塗ります。
この時点で、白の連結成分が1、黒の連結成分が1です。

指定された白の連結成分がa、黒がbのとき、
まず下半分の黒エリアの左下から、合計a-1マス、1マスおきに白く塗っていきます。

こんな感じです。端までいったら、白マスが隣り合わないよう、次は2つ上のマスから始めます。
上半分も黒で同じようにb-1マス塗ります。
この塗りかただと、上半分の白エリアに到達するまでに、大体1000マスくらい塗れます。
制約は白黒ともに500なので、この塗りかたでOKです。
もし1000とか1500だった場合は、白黒交互に市松模様っぽく塗れば大丈夫だと思います。

まとめ

今週の順位はなんと21位。そして全完。それもこれも、D問題が特殊だったからの一言に尽きます。
グラフやら数学やらが出題されていたら確実に死んでいただろうし……。
高校数学を復習したい、アルゴリズムを勉強したい……と以前に書いた気がしますが、最近は忙しすぎて、どちらもまともにできていません。これからさらに忙しくなるので、競プロの本格的な勉強は（キリもいいので）この辺でしばらく休止しようかと思います（そもそも始めてすらいない）。