AtCoder振り返り168(A～D)

2020年5月17日開催のAtCoder参加結果を振り返ります。

結果

結果はA, B, Cの3問正解の3完です。
3問目までは25分程度で解けましたし一発ACでしたがD問で阻まれてしまいました。
D問は問題内容を間違って理解しており解けませんでした。（後述）

成績

成績は若干上昇しています。
あと1回挑戦すれば茶色コーダにはなれるでしょうか？

順位は以下の通り
うーんこんなものですかね。

問題

問1 ∴ (Therefore)

引数Nの1の位がいずれかによって出力を分ける問題

• パターン1：2,4,5,7,9　のとき ：hon
• パターン2：0,1,6,8のとき ：pon
• パターン3：それ以外の時 ：bon

もっと簡単にできたと思うのですが、愚直に実装しました。
解説ではswitch分で簡潔に記載していますね。

回答コード

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		try (Scanner scn = new Scanner(System.in)) {
			String N = scn.next();
			String c = N.substring(N.length()-1);
 
			if(c.equals("2")
			|| c.equals("4")
			|| c.equals("5")
			|| c.equals("7")
			|| c.equals("9")
			) {
				System.out.println("hon");
			} else if(c.equals("0")
					|| c.equals("1")
					|| c.equals("6")
					|| c.equals("8"))
			{
					System.out.println("pon");
			} else {
				System.out.println("bon");
			}
		}
	}
}

問2 ... (Triple Dots)

以下の2パターンの実装を行います。

• パターン1：引数SがKを超える場合：K文字出力 + "..."
• パターン2：それ以外の場合：そのまま引数Sを出力

文字列操作さえできれば特に難しくはないと思います。

回答コード

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

問3

時計の長針と短針の先端を結ぶ直線の長さを求める問題です。

引数として渡される情報は以下の通りです。
引数Ａ：短針（時針）の長さ
引数Ｂ：長針（分針）の長さ
引数Ｈ：時
引数Ｍ：分

三角形が仮に直角三角形だった場合、
短針の長さ　×　短針の長さ　＋　長身の長さ　×　長身の長さ　＝　√直線の長さ　となります。
これが三平方の定理です。

しかし、時刻によっては三角形は直角になりません。（というかほとんどの場合直角三角形にはなりません。）
そうすると三平方の定理では求められません。これを求める方法として「余弦定理」を使います。
余弦定理を使うためには角度の計算が必要ですが、時・分の長さから求められます。

短針（時針）の1分で進む角度：0.5℃
長針（分針）の1分で進む角度：6℃

コードに落とし込むと以下の通りとなりました。

回答コード

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 H = scn.nextInt();
			int M = scn.nextInt();
 
			double longAngle = M * 6;
			double shortAngle = H * (360/12) + M * 0.5;
 
			double angle = 0;
 
			if(longAngle < shortAngle) {
				longAngle = 360 + longAngle;
				angle = longAngle - shortAngle;
			} else {
				angle = longAngle - shortAngle;
			}
 
			//余弦定理
			System.out.println(Math.sqrt(Math.pow(A, 2) + Math.pow(B, 2) -2*A*B*Math.cos(Math.toRadians(angle))));
		}
	}
}

問4 .. (Double Dots)

ある部屋から最短で部屋1にたどり着くために、
各部屋に道しるべ（進むべき部屋の番号）を求めるという問題です。

解説にある通り、部屋1の深さを０として考えた場合以下の重要な事実が成り立つとのこと
「深さ d + 1 の部屋には，深さ d の部屋が少なくとも 1 つ繋がっている．」

以下のようにMap機能を利用したうえで、
各部屋ごとに幅優先探索で深さを調べていけばいずれ分かります。

import java.util.*;
 
public class Main { 
    public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		Map<Integer, List<Integer>> map = new HashMap<>();
 
		for(int i=0; i<m; i++){
			int a = sc.nextInt();
			int b = sc.nextInt();
			List<Integer> value = map.get(a);
			if(value == null) value = new ArrayList<>();
			value.add(b);
			map.put(a, value);
			List<Integer> value2 = map.get(b);
			if(value2 == null) value2 = new ArrayList<>();
			value2.add(a);
			map.put(b, value2);
		}
		int[] ans = new int[n+1];
		ArrayDeque<Integer> dq = new ArrayDeque<>();
		dq.add(1);
		while(dq.size() > 0){
			Integer i = dq.removeFirst();
			List<Integer> value = map.get(i);
			for(Integer j: value){
				if(ans[j] == 0){
					ans[j] = i;
					dq.add(j);
				}
			}
		}
		System.out.println("Yes");
		for(int i=2; i<=n; i++){
			System.out.println(ans[i]);
		}
	}
}

解説
https://img.atcoder.jp/abc168/editorial.pdf