古代すぬけ国のピラミッド調査が出来ない！プロコンやってみた2日目

プロコンを初めて2回目のコンテストが終了しました。
感想としては、「ピラミッドは俺が破壊したのですべての答えは0 0 0、いいね？」
ABはスムーズに解けたのですが、Cで壁にぶち当たり、Dは問題文を読むことすらできませんでした・・・。
というわけで、今回はABCを自分なりにかみ砕いた内容を書いていきます。

A. Programming Education

ifして書くだけですね。
一応1歳の時は入力が減ることに注意。
(Javaでsplitして配列に入れて処理・・・みたいなことをすると実行時エラー出るかもなので)
自分のコードを晒すとこんな感じでした。

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		if (a == 1) {
			System.out.println("Hello World");
		} else {
			int b = sc.nextInt();
			int c = sc.nextInt();
			System.out.println(b + c);
		}
	}
}

しかし2020年の1,2歳はやばいですね。自分2歳の時に足し算という概念がなかったような。

B. Time Limit Exceeded

時間内に帰れるかつコストが最小のものを選ぶというもの。
forでぐるぐる回すのが王道だと思います。もっと変態コードがありそうな予感はしていますが・・・。

import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int T = sc.nextInt();
		// 1 ≤ ci ≤ 1000 より
		int minCost = 1001;
		for(int i=0;i<N;i++){
		int c = sc.nextInt();
		int t = sc.nextInt();
			if(t<=T && c < minCost){
				minCost = c;
			}
		}
		if(minCost == 1001){
			System.out.println("TLE");
		}else{
			System.out.println(minCost);
		}
	}
}

forで受け取った経路分ループして、
時間が制限より少なく、かつコストが初期値or前回代入した経路のコストより低ければ代入するというもの。
コストの初期値が1001なのは問題文の制約にコスト(Ci)が1以上1000以下と書かれているためです。

この問題は比較的実際の業務でも使いどころがありそうな感じがします。
メモリ少なくて実行の早い実装を見つけて勉強するのもありかも。

C. Pyramid

高橋君のピラミッドは僕がぶち壊したので答えは全て0 0 0、いいね？#AtCorder#プロコン

— あおいそら (@bluesky177896) 2018年10月6日

ということで、難しくて提出すらできなかった問題。
解説にも以下のようにある通り、全探索(可能性のある全てを検証すること)して答えを出すのが良いっぽいので、
深さ優先とかは考えなくてよさげ。

※制約の部分はちゃんと見た方がよさそうで、
会社の先輩の話によると10の〇乗と書いてある場合はTLE(処理時間制限切れのこと)を警戒すればよいとのこと。
他の場合も警戒した方が良いパターンはあるが、100とか1000でビビる必要は無さそう。

で、どうやって高さとか中心座標求めるん？？って話なのだが、解説だと理系じゃない理系には理解できなかった。

コードを頑張って解読した感じだと、どうやらここを上手く使わないといけない模様。
中心座標以外の高さは0か、「H−|X−CX|−|Y−CY|」になるため、
これで各種標準入力で貰った、「座標リスト×X軸101個分×Y軸101個分」の全探索をする、というイメージっぽい。

また、単純にmax(H−|X−CX|−|Y−CY|,0)これを基に答えを出すと複数個答えが出てしまうので、
標準入力としてもらった座標を基に検算を行う必要がある、ということ・・・。
解説や他人のコードを基に出したのが以下のコード。コメント増し増しです。

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 座標数
		int N = sc.nextInt();

		//x
		int[] x = new int[N];
		//y
		int[] y = new int[N];
		//z(高さ)
		int[] h = new int[N];
		//各座標を配列に順に詰める
		for (int i = 0; i < N; i++) {
			x[i] = sc.nextInt();
			y[i] = sc.nextInt();
			h[i] = sc.nextInt();
		}
		//x,yは1以上100以下の整数より100*100のループ
		for (int i = 0; i <= 100; i++) {
			for (int j = 0; j <= 100; j++) {
				int H = 0;
				Boolean B = true;
				for (int k = 0; k < N; k++) {
					//配列のk番目の高さが0でない場合、z(高さ)を計算
					if (h[k] != 0) {
						H = h[k] + Math.abs(x[k] - i) + Math.abs(y[k] - j);
					}
				}
				for (int k = 0; k < N; k++) {
					//高さが標準入力にある座標を基に検算しておかしかったらループ継続
					if (h[k] != Math.max(H - Math.abs(x[k] - i) - Math.abs(y[k] - j), 0)) {
						B = false;
					}
				}
				if (B) {
					System.out.println(i + " " + j + " " + H);
					break;
				}
			}
		}
	}
}

ちなみに、出来ない問題を見た時の対処法は、「解説を読む」→「他人のコードを読む」が一番だと思います。
ただ、他人のコードを読むときの注意として、ランクがあまり高くない人のコードはあまり良くないロジックの可能性があります。
なので、順位表の上位の人から見ていくのが良いかと思います。(逆に変態すぎて読めないこともあるので注意）
あと、言語的にC++がどうしても多いので、かなり独特な仕様の言語を利用している場合も注意。(awkやsedユーザーがc++見ても参考にならない気がする？)

まとめ

というわけで、二回目ですが初回と同じくBまでしか取れませんでした・・・。
今回は数学回というやつだったようで、苦手な人はとことん苦手とは聞きましたが、
もっとRateをあげようと思ったらこちらもクリアしていく必要があるので頑張らないとと思います。

考えていたらブログ更新も停滞してしまったので色々反省の多い回でした。