はじめに
今回はコンテスト中にDまで、コンテスト後にEまで解けたのでそれを載せようと思います。
では、見ていきましょう。
A - flip
問題文はこちら
先頭から文字を見ていって1と0を反転させて出力しました。
A.java
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//Sの受け取り
String S = System.in.next();
//反転させて出力
for(char c:S.toCharArray())
System.out.print(c=='0'?1:0);
//お気持ち程度の改行
System.out.println();
System.out.close();
}
}
xorで解く方法とかもあるそうですが、そこまでは発想が出来ませんでした。
B - レ
問題文はこちら
ArrayDequeを二つ用いて、$i=1,2,...$について一つ目のArrayDequeの先頭に追加し、$a$に無ければ二つ目のArrayDequeの末尾に一つ目のArrayDequeを追加することでレ点を再現しました。
B.java
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//N、M、aの受け取り
int N = System.in.nextInt();
int M = System.in.nextInt();
int[] a = System.in.nextInt(M);
//aの添え字(aの今見ている箇所を指す)
int index = 0;
//全体の答え
ArrayDeque<Integer> ans = new ArrayDeque<>();
//レ点による反転を管理する方
ArrayDeque<Integer> now = new ArrayDeque<>();
//1から順に
for(int i=1;i<=N;i++){
//aにiがあればnowの先頭に追加
if(index<M&&i==a[index]){
index++;
now.addFirst(i);
}
else{
//とりあえず先頭に追加して、nowをansの末尾に
now.addFirst(i);
while(!now.isEmpty())
ans.addLast(now.pollFirst());
}
}
//ansを先頭から出力
while(!ans.isEmpty())
System.out.print(ans.pollFirst()+" ");
//お気持ち程度の改行
System.out.println();
System.out.close();
}
}
非常に悩んでしまいました…。こういう問題は苦手ですね…。
C - Coverage
問題文はこちら
問題文と制約からbit全探索で解ける物だと判断して解きました。
集合はboolean型配列で管理しています。
C.java
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//N、Mの受け取り
int N = System.in.nextInt();
int M = System.in.nextInt();
//各集合を表す配列
boolean[][] contain = new boolean[M][N+1];
for(int i=0;i<M;i++){
//aに合わせてtrueに
int C = System.in.nextInt();
while(C-->0){
int a = System.in.nextInt();
contain[i][a] = true;
}
}
//答え
int ans = 0;
//bit全探索
for(int i=0;i<1<<M;i++){
//iに合わせてそれぞれの論理和を作製
boolean[] sum = new boolean[N+1];
for(int j=0;j<M;j++){
if((i&(1<<j))>0){
for(int k=1;k<=N;k++){
sum[k] |= contain[j][k];
}
}
}
//全部trueならansに加算
boolean isGood = true;
for(int j=1;j<=N;j++){
isGood &= sum[j];
}
if(isGood){
ans++;
}
}
//答えの出力
System.out.println(ans);
System.out.close();
}
}
今になってint型で集合を管理できたなと思いました。
D - Step Up Robot
問題文はこちら
動的計画法で解きました。
$\mathrm{dp}[i]$:$i$段目に到達可能か
という感じで管理して遷移させました。
D.java
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//N、A、Mの受け取り
int N = System.in.nextInt();
int[] A = System.in.nextInt(N);
int M = System.in.nextInt();
//モチがある場所をsetに追加
HashSet<Integer> mochi = new HashSet<Integer>();
while(M-->0)
mochi.add(System.in.nextInt());
//Xの受け取り
int X = System.in.nextInt();
//dpテーブル
boolean[] dp = new boolean[X+1];
dp[0] = true;
//0段目から順に、行ける場所に対して論理和を取る(配るDP)
for(int i=0;i<X;i++){
//到達不可なら弾く
if(mochi.contains(i))
continue;
for(int j=0;j<N&&i+A[j]<=X;j++){
dp[i+A[j]] |= dp[i];
}
}
//X段目に到達可能だった？
System.out.println(dp[X]?"Yes":"No");
System.out.close();
}
}
これは比較的早く思いつきました。
E - Swap Places
問題文はこちら
各ケースに対して、高橋君、青木君が同時にどこにいるかという情報を持ってBFSを行ないました。
何故間に合うかの説明は公式解説にあります。
E.java
import java.util.Scanner;
import java.util.ArrayList;
import java.util.ArrayDeque;
import java.awt.Point;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//Tの受け取り
int T = sc.nextInt();
//出力高速化用
StringBuilder ans = new StringBuilder();
Test:while(T-->0){
//N、M、Cの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int[] C = new int[N];
for(int i=0;i<N;i++)
C[i] = sc.nextInt();
//隣接リストの構築
ArrayList<ArrayList<Integer>> route = new ArrayList<>();
for(int i=0;i<=N;i++)
route.add(new ArrayList<>());
while(M-->0){
int u = sc.nextInt();
int v = sc.nextInt();
route.get(u).add(v);
route.get(v).add(u);
}
//特に効力は無いが、自明なものは弾く
if(C[0]!=C[N-1]){
//set[高橋君][青木君]:高橋君と青木君の位置が探索済みか？
boolean[][] set = new boolean[N+1][N+1];
//Point用のArrayDequeとそこまでのコスト用のArrayDeque
ArrayDeque<Point> bfsP = new ArrayDeque<>();
ArrayDeque<Integer> bfsC = new ArrayDeque<>();
//初期状態を追加
bfsP.add(new Point(1,N));
bfsC.add(0);
set[1][N] = true;
//BFS
while(bfsP.size()>0){
//今の状態とそこまでのコストを取り出す
Point now = bfsP.pollFirst();
int cost = bfsC.pollFirst();
//到達できたなら出力して次のケースへ
if(now.x==N&&now.y==1){
ans.append(cost);
ans.append("\n");
continue Test;
}
//今いる所から移動できる場所を探す
for(int nextT:route.get(now.x)){
for(int nextA:route.get(now.y)){
//二点の色が違う？
if(C[nextT-1]!=C[nextA-1]){
//到達済みでない？
if(!set[nextT][nextA]){
//setに記録してArrayDequeに追加
set[nextT][nextA] = true;
bfsP.add(new Point(nextT,nextA));
bfsC.add(cost+1);
}
}
}
}
}
}
//ここまで来た=移動できなかったので-1を出力
ans.append(-1);
ans.append("\n");
}
//答えの出力
System.out.println(ans.toString());
}
}
本番中に気づけなかったのが悔しいです…。
感想
A:易しい
B:超大変
C:bit全探索を知っていれば比較的早く発想出来そう
D:DPを知っていれば(以下同文)行けない段に注意
E:BFSで間に合うと思わなかった…
って感じでした。
いやぁ…精進不足ですね。もっと頑張ります。