ABC344A～Fの解答[Java]

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

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

## A - Spoiler
問題文は[こちら](https://atcoder.jp/contests/abc344/tasks/abc344_a)

`|`の中かをbooleanで管理して解きました。
```A.java
final class Main{
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner(System.in);
	private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);

	public static void main(String[] args){

		//Sの受け取り
		String S = sc.next();

  		//'|'の外側か
		boolean flag = true;

  		//順に処理
		for(char c:S.toCharArray()){
			if(c=='|')
				flag = !flag;
			else if(flag)
				out.print(c);
		}

		out.close();
	}
}
```

## B - Delimiter
問題文は[こちら](https://atcoder.jp/contests/abc344/tasks/abc344_b)

ArrayDequeに値を入れていって逆順に出力しました。
```B.java
final class Main{
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner(System.in);
	private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);

	public static void main(String[] args){

		//0が来るまで先頭にaddしていく
		ArrayDeque<Integer> deq = new ArrayDeque<>();
		int num = -1;
		while(num!=0){
			num = sc.nextInt();
			deq.addFirst(num);
		}

  		//逆順に出力
		for(Integer ans:deq)
			out.println(ans);

		out.close();
	}
}
```

## C - A+B+C
問題文は[こちら](https://atcoder.jp/contests/abc344/tasks/abc344_c)

$A+B+C$は高々$10^6$通りしかないので先に全通りをHashSetに入れて各問題に答えました。
```C.java
final class Main{
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner(System.in);
	private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);

	public static void main(String[] args){

		//N、A、M、B、L、Cの受け取り
		int N = sc.nextInt();
		int[] A = sc.nextInt(N);
		int M = sc.nextInt();
		int[] B = sc.nextInt(M);
		int L = sc.nextInt();
		int[] C = sc.nextInt(L);

  		//前計算
		HashSet<Integer> set = new HashSet<>();
		for(int a:A)
			for(int b:B)
				for(int c:C)
					set.add(a+b+c);

		//Qの受け取り
		int Q = sc.nextInt();

  		//各問題に答える
		for(int X:sc.nextInt(Q))
			out.println(set.contains(X)?"Yes":"No");

		out.close();
	}
}
```

## D - String Bags
問題文は[こちら](https://atcoder.jp/contests/abc344/tasks/abc344_d)

HashMapを使って動的計画法で解きました。
keyは今完成している長さ、valueは最小金額になっています。
```D.java
final class Main{
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner(System.in);
	private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);

	public static void main(String[] args){

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

  		//初期値設定
		HashMap<Integer,Integer> map = new HashMap<>();
		map.put(0,0);

  		//遷移
		for(String[] s:S){
			HashMap<Integer,Integer> next = new HashMap<>(map);
			for(Entry<Integer,Integer> entry:map.entrySet()){
				int first = entry.getKey();
				Loop:for(String str:s){
					if(first+str.length()>T.length())
						continue Loop;
					for(int i=0;i<str.length();i++)
						if(T.charAt(i+first)!=str.charAt(i))
							continue Loop;
					next.merge(first+str.length(),entry.getValue()+1,Integer::min);
				}
			}
			map = next;
		}

  		//答えの出力
		out.println(map.getOrDefault(T.length(),-1));

		out.close();
	}
}
```
今思えばわざわざHashMap使わなくても配列で良かったな…。

## E - Insert or Erase
問題文は[こちら](https://atcoder.jp/contests/abc344/tasks/abc344_e)

各値の前後の関係さえわかっていれば処理できそうなので、その二種の情報と自身の値を保持したNodeクラスを作り、連結リストの要領で解きました。
```E.java
final class Main{
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner(System.in);
	private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);

	public static void main(String[] args){

		//Nの受け取り
		int N = sc.nextInt();

  		//情報を保持するクラス
		class Node{
			Node prev,next;
			int value;
			Node(Node p,Node n,int v){
				prev = p;
				next = n;
				value = v;
			}
		}

  		//初期状態の設定
		HashMap<Integer,Node> map = new HashMap<>();
		Node bef = null;
		for(int num:sc.nextInt(N)){
			Node node = new Node(bef,null,num);
			if(bef!=null)
				bef.next = node;
			map.put(num,node);
			bef = node;
		}

  		//Qの受け取り
		int Q = sc.nextInt();

  		//クエリ処理
		while(Q-->0){
			int t = sc.nextInt();
			if(t==1){
				int x = sc.nextInt();
				int y = sc.nextInt();
				Node node = map.get(x);
				Node newNode = new Node(node,node.next,y);
				if(node.next!=null)
					node.next.prev = newNode;
				node.next = newNode;
				map.put(y,newNode);
			}
			else{
				int x = sc.nextInt();
				Node revNode = map.remove(x);
				if(revNode.prev!=null)
					revNode.prev.next = revNode.next;
				if(revNode.next!=null)
					revNode.next.prev = revNode.prev;
			}
		}

  		//先頭のNodeを探す
		Node first = null;
		for(Node node:map.values())
			if(node.prev==null)
				first = node;

    	//答えを順に格納
		int[] ans = new int[map.size()];
		for(int i=0;i<ans.length;i++){
			ans[i] = first.value;
			first = first.next;
		}

  		//答えの出力
		out.println(ans);

		out.close();
	}
}
```
こういうのは得意なので助かりました。

## F - Earn to Advance
問題文は[こちら](https://atcoder.jp/contests/abc344/tasks/abc344_f)

[公式解説](https://atcoder.jp/contests/abc344/editorial/9473)の通りです。
マスの情報をPointクラスを使って表現していて、HashMapで管理しているのもあってか結構実行時間が長めです。
```F.java
final class Main{
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner(System.in);
	private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);

	public static void main(String[] args){

		//N、P、R、Dの受け取り
		int N = sc.nextInt();
		int[][] P = sc.nextInt(N,N);
		int[][] R = sc.nextInt(N,N-1);
		int[][] D = sc.nextInt(N-1,N);

  		//初期設定
		HashMap<Point,HashMap<Integer,long[]>> dp = new HashMap<>();
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)
				dp.put(new Point(i,j),new HashMap<>());
		dp.get(new Point(0,0)).put(0,new long[]{0,0});

  		//遷移
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				Point p = new Point(i,j);
				Point pi = new Point(i+1,j);
				Point pj = new Point(i,j+1);
				for(Entry<Integer,long[]> entry:dp.get(p).entrySet()){
					int max = Math.max(entry.getKey(),P[i][j]);
					long cost = entry.getValue()[0];
					long value = entry.getValue()[1];
					if(i+1<N){
						long temp = Math.max(0,D[i][j]-value+max-1)/max;
						long nextValue = temp*max-D[i][j]+value;
						long nextCost = temp+1+cost;
						dp.get(pi).merge(max,new long[]{nextCost,nextValue},(a,b)->{
							if(a[0]<b[0])
								return a;
							if(a[0]>b[0])
								return b;
							if(a[1]>b[1])
								return a;
							return b;
						});
					}
					if(j+1<N){
						long temp = Math.max(0,R[i][j]-value+max-1)/max;
						long nextValue = temp*max-R[i][j]+value;
						long nextCost = temp+1+cost;
						dp.get(pj).merge(max,new long[]{nextCost,nextValue},(a,b)->{
							if(a[0]<b[0])
								return a;
							if(a[0]>b[0])
								return b;
							if(a[1]>b[1])
								return a;
							return b;
						});
					}
				}
			}
		}

  		//最小値を探す
		long ans = Long.MAX_VALUE;
		for(long[] val:dp.get(new Point(N-1,N-1)).values())
			ans = Math.min(ans,val[0]);

   		//答えのしゅつりょく
		out.println(ans);

		out.close();
	}
}
```
いやぁ…理解はできるけどコンテスト中には解けないねぇ…。

## 感想
A:ちょっと手間取った
B,C:易しい
D:DPっぽさを感じたから易しめに感じた
E:比較的好き
F:わからん…
って感じでした。

Fが解けなかったこともあって、レートは上がりましたが、ほんのりモヤモヤ…。