ABC305A～Fの解答[Java]

## はじめに
今回はコンテスト中にEまで、コンテスト後にFまで解けたのでFまで載せようと思います。

では、見ていきましょう。
なお、ライブラリは[提出結果](https://atcoder.jp/contests/abc305/submissions?f.Task=&f.LanguageName=Java&f.Status=AC&f.User=viral)よりご覧ください。

## A - Water Station
問題文は[こちら](https://atcoder.jp/contests/abc305/tasks/abc305_a)

前後の地点を求めて近い方を出力しました。
```A.java
final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//Nの受け取り
		int N = sc.nextInt();

		//前後の地点を求める
		int a = N/5*5;
		int b = (N+4)/5*5; //雑だったので地点ぴったりの時はa==bになっちゃってる。問題は無いけど

		//最寄りの出力
		out.println(Math.abs(a-N)<Math.abs(N-b)?a:b);
 
		out.close();
	}
}
```
今思えば普通に`(N+2)/5*5`で良かったなと思いました。

## B - ABCDEFG
問題文は[こちら](https://atcoder.jp/contests/abc305/tasks/abc305_b)

コンテスト後に書いた物ですが、事前にAから何個目の地点かを求めておいて、Aからの距離を予め求めた配列を使って距離を求めました。
```B.java
import java.util.Scanner;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		//p,qのAからの距離を求める
		int p = sc.next().charAt(0)-'A';
		int q = sc.next().charAt(0)-'A';

		//Aからの距離を求めておいた配列
		int[] point = {0,3,4,8,9,14,23};

		//差の出力
		System.out.println(Math.abs(point[p]-point[q]));
	}
}
```
コンテスト中は焦って全通り書いてました…。

## C - Snuke the Cookie Picker 
問題文は[こちら](https://atcoder.jp/contests/abc305/tasks/abc305_c)

問題文の$a,b,c,d$を求めて、その範囲内で`.`の座標を求めることで解きました。
```C.java
final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 

		//H、W、Sの受け取り
		int H = sc.nextInt();
		int W = sc.nextInt();
		char[][] S = sc.nextCharArray(H);

		//a、b、c、dの探索
		int a=H,b=0,c=W,d=0;
		for(int i=0;i<H;i++){
			for(int j=0;j<W;j++){
				if(S[i][j]=='#'){
					a = Math.min(a,i);
					c = Math.min(c,j);
					b = Math.max(b,i);
					d = Math.max(d,j);
				}
			}
		}

		//i=a~b、j=c~dで.の地点を探して出力
		for(int i=a;i<=b;i++){
			for(int j=c;j<=d;j++){
				if(S[i][j]=='.')
					out.println((i+1)+" "+(j+1));
			}
		}
 
		out.close();
	}
}
```
比較的早く思いつけたので良かったです。

## D - Sleep Log
問題文は[こちら](https://atcoder.jp/contests/abc305/tasks/abc305_d)

コンテスト後に書いた物ですが、時間$t$に対して、0分から$t$分までで寝た時間を返すメソッドを作って累積和的な要領で解きました。
※下のコードは入出力高速化を行なっていないので結構ギリギリです(提出したら2646msだった)。
```D.java
import java.util.Scanner;
import java.util.TreeMap;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		//N、Aの受け取り
		int N = sc.nextInt();
		int[] A = new int[N];
		for(int i=0;i<N;i++)
			A[i] = sc.nextInt();

		//累積和準備
		initialize(A);

		//各問いに答える
		int Q = sc.nextInt();
		while(Q-->0){
			int l = sc.nextInt();
			int r = sc.nextInt();
			System.out.println(get(r)-get(l));
		}
	}

	//getメソッド用の事前構築
	private static void initialize(int[] A){
		sum.put(0,0);
		sTime.put(0,0);
		int num = 0;
		for(int i=1;i<A.length;i+=2){
			sum.put(A[i],num);
			num += A[i+1]-A[i];
			sum.put(A[i+1],num);
			sTime.put(A[i],A[i+1]);
			sTime.put(A[i+1],A[i+1]);
		}
	}

	//keyまでの累積和をvalueにしたmap
	static TreeMap<Integer,Integer> sum = new TreeMap<>();

	//寝始めた時間と起きた時間の組になってる(便宜上起きた時間と起きた時間の組も入れてる)
	static TreeMap<Integer,Integer> sTime = new TreeMap<>();

	//t分までの寝た時間を返すメソッド
	private static int get(int t){

		//累積和のmapから求める
		int ans = sum.get(sum.floorKey(t));

		//寝始めた時間と起きた時間の間にtがあるとき用
		int last = sTime.floorKey(t);

		//端数調整して返す
		return ans+Math.min(sTime.get(last),t)-last;
	}
}
```
本番中はごちゃごちゃ書いてバグらせてしまってめちゃくちゃ時間かけてしまいました…。弱さを実感しました…。

## E - Art Gallery on Graph
問題文は[こちら](https://atcoder.jp/contests/abc305/tasks/abc305_e)

ダイクストラ法で解きました。
距離ではなく、今残っている体力を基準に優先度を付けて上げることで適切に処理できます。
```E.java
final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//N、N、K、グラフの受け取り
		int N = sc.nextInt();
		int M = sc.nextInt();
		int K = sc.nextInt();
		int[][] graph = sc.nextGraph(N,M); //1-indexedの隣接リスト

		//地点iに行ったときの最大残り体力を管理する配列
		int[] dist = new int[N+1];

		//到達可能かを記録する配列(無くても良い)
		boolean[] canGo = new boolean[N+1];

		//初期値代入
		Arrays.fill(dist,-1);

		//警備員の情報の受け取り
		int[][] person = sc.nextInt(K,2);

		//ダイクストラ用queue
		PriorityQueue<Pair<Integer,Integer>> queue = new PriorityQueue<>();

		//各警備員をqueueに入れると共に情報の更新
		for(int[] p:person){
			queue.add(new Pair<>(-p[1],p[0]));
			canGo[p[0]] = true;
			dist[p[0]] = p[1];
		}

		//ダイクストラ
		while(queue.size()>0){
			Pair<Integer,Integer> pair = queue.poll();
			int now = pair.getValue();
			int h = -pair.getKey();
			for(int next:graph[now]){
				if(dist[now]-1>dist[next]){
					dist[next] = h-1;
					canGo[next] = true;
					if(h>1)
						queue.add(new Pair<>(-h+1,next));
				}
			}
		}

		//行ける地点のカウント
		int count = 0;
		for(boolean flag:canGo)
			if(flag)
				count++;

		//個数の出力
		out.println(count);

		//行ける地点を配列に入れる
		int[] ans = new int[count];
		int index = 0;
		for(int i=1;i<=N;i++)
			if(canGo[i])
				ans[index++] = i;

		//答えの出力
		out.println(ans);
 
		out.close();
	}
}
```
最初hの大きさで降順にソートしてBFSかな～とかいう甘い考えで提出してしまってTLEをいただきました。

## F - Dungeon Explore
問題文は[こちら](https://atcoder.jp/contests/abc305/tasks/abc305_f)

説明は[公式解説](https://atcoder.jp/contests/abc305/editorial/6542)に任せますが、DFSで解きました。
```F.java
final class Main {
 
	private static final boolean autoFlush = true;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//N、Mの受け取り
		int N = sc.nextInt();
		int M = sc.nextInt();

		//探索済みの管理用配列
		boolean[] checked = new boolean[N+1];

		//dfs
		dfs(1,checked,N);
 
	}

	//dfs(今いる頂点,探索済みか管理する配列,ゴール(=N))
	private static void dfs(int now,boolean[] checked,int G){

		//ゴールにたどり着いたら終了
		if(now==G){
			System.exit(0);
		}

		//探索済みに
		checked[now] = true;

		//今いる頂点から行ける頂点を全て探索済みか管理するフラグ
		boolean flag = true;

		//全部探索済みになるまで回す
		while(flag){

			//kと行ける頂点の受け取り
			int k = sc.nextInt();
			int[] next = sc.nextInt(k);

			//forで更新されなかったら抜けるようにfalseに設定
			flag = false;

			for(int ne:next){

				//重複探索は避ける
				if(checked[ne])
					continue;

				//行ける地点があったならフラグを立てて、遷移
				flag = true;
				out.println(ne);
				dfs(ne,checked,G);
				out.println(now);
				break;//入力を再度受け取る為に一旦forを抜ける
			}
		}
	}
}
```
最後の`OK`という入力なんですけど、何故か受け取ると全ケースTLEになるので多分最後に改行が入ってないです(質問がまだ返ってきてないので僕のライブラリがバグってる可能性もまぁまぁありますが、これまでそんな事無かったのであまりそうは考えられないかなと思ってます)(回答が返ってきたら追記します)。
まぁそもそもコンテスト中は戻ってきたときに入力受け取るの忘れてたので改行があっても無くても変わらないですが…。

## 感想
A:ちゃんと`(A+B-1)/B`の意味を理解していますか？という感じの問題だった
B:テンパってクソコードを…うぅ…
C:易しめかも
D:飛ばせば良かったか…
E:気付けばなんてことはないかも
F:DFSってのはすぐ気付けたので、易しめかも(解けなかったですけど…)
って感じでした。

レート下がってしまいましたがこれを糧に精進するしかないですね…。