はじめに
今回はコンテスト中にEまで、コンテスト後にFを解いたのでFまで載せようと思います。
なお、僕のライブラリは提出結果よりご確認下さい。
では、見ていきましょう。
A - Spoiler
問題文はこちら
|の中かを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
問題文はこちら
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
問題文はこちら
$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
問題文はこちら
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
問題文はこちら
各値の前後の関係さえわかっていれば処理できそうなので、その二種の情報と自身の値を保持した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
問題文はこちら
公式解説の通りです。
マスの情報を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が解けなかったこともあって、レートは上がりましたが、ほんのりモヤモヤ…。