はじめに
今回はコンテスト中にEまで解けたのでそれを載せようと思います。
僕のライブラリは提出結果よりご確認ください。
では、見ていきましょう。
A - First ABC
問題文はこちら
一文字ずつ受け取って、HashSetのsizeが3になったところを出力しました。
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();
//出現した種類数を数える用
HashSet<Character> set = new HashSet<>();
//先頭から一文字ずつ受け取る
for(int i=1;i<=N;i++){
set.add(sc.nextChar());
//ABC全部出たら出力して終了
if(set.size()==3){
out.println(i);
break;
}
}
out.close();
}
}
今思えば、indexOfを使って最大値を答える方が楽だったかもしれません。
A改.java
import java.util.Scanner;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//N、Sの受け取り
int N = sc.nextInt();
String S = sc.next();
//各文字の出現位置の最大値を取る
int ans = S.indexOf("A");
ans = Math.max(ans,S.indexOf("B"));
ans = Math.max(ans,S.indexOf("C"));
//1-indexedに修正して出力
System.out.println(ans+1);
}
}
B - Vacation Together
問題文はこちら
最初に、一人でもxならxで、全員oならoである文字列を作り、一番oが連続している箇所を探しました。
B.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、Dの受け取り
int N = sc.nextInt();
int D = sc.nextInt();
//一人以上ダメな日を記録
boolean[] isBad = new boolean[D];
for(int i=0;i<N;i++){
for(int j=0;j<D;j++){
isBad[j] |= sc.nextChar()=='x';
}
}
//今見ているところまでの連続しているoの数
int now = 0;
//最大値
int ans = 0;
//先頭から見ていく
for(boolean flag:isBad){
//全員暇なら加算
if(!flag){
now++;
}
//一人以上ダメなら直前までのoの長さをansに記録して0に
else{
ans = Math.max(ans,now);
now = 0;
}
}
//末尾のoも考慮する必要があるのでnowとansで大きい方を出力
out.println(Math.max(ans,now));
out.close();
}
}
これはそんなに難しくないですね。
C - Find it!
問題文はこちら
公式解説にも書いてありますが、どこから探索しても閉路にたどり着くので頂点1からDFSをし、閉路を検出して出力しました。
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 ) {
//N、Aの受け取り
int N = sc.nextInt();
int[] A = sc.nextInt(N);
//非再帰用Deque
ArrayDeque<Integer> deq = new ArrayDeque<>();
//頂点1からの距離
int[] count = new int[N];
Arrays.fill(count,-1); //初期化
//頂点1から探索
deq.add(0);
int p = -1; //閉路の先頭を記録するための変数
count[0] = 0;
//DFS
while(deq.size()>0){
int now = deq.peekLast();
//次の頂点は探索済み？
if(count[A[now]-1]>-1){
p = A[now]; //閉路先頭の記録
break;//DFS終了
}
//更新
count[A[now]-1] = count[now]+1;
deq.add(A[now]-1);
}
//距離の差が閉路の頂点の数
int[] ans = new int[count[deq.peekLast()]-count[p-1]+1];
//後ろから埋めていけばそのままBの条件を満たす順序に格納できる
for(int i=ans.length;i>0;i--)
ans[i-1] = deq.pollLast()+1;
out.println(ans.length);
out.println(ans);
out.close();
}
}
おまけですが、UnionFindを使って解いたやつも載せときます。
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 ) {
//N、Aの受け取り
int N = sc.nextInt();
int[] A = sc.nextInt(N);
//UnionFind
UnionFind uf = new UnionFind(N+1);
//今見ている頂点(なんとなく1で)
int now = 1;
//閉路が形成されるまでunite
while(uf.unite(now,A[now-1]))
now = A[now-1];
//閉路先頭に
now = A[now-1];
//Bの作成用
ArrayList<Integer> ans = new ArrayList<>();
ans.add(now);
//閉路先頭に戻るまで移動しながら格納
while(A[now-1]!=ans.get(0))
ans.add(now = A[now-1]);
//出力するのに都合が良いのでint型配列に入れ直し
int[] ans2 = new int[ans.size()];
for(int i=0;i<ans.size();i++)
ans2[i] = ans.get(i);
//答えの出力
out.println(ans.size());
out.println(ans2);
out.close();
}
}
D - Grid Ice Floor
問題文はこちら
公式解説の省略されている$O(NM(N+M))$解法に当たるかと思います(ユーザー解説のBFS版)。
D.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、M、Sの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
char[][] S = sc.nextCharArray(N);
//停止、通過したことがあるマスの記録
boolean[][] checked = new boolean[N][M];
checked[1][1] = true;
//BFS用Deque
ArrayDeque<Integer> deq = new ArrayDeque<>();
deq.add(1);
deq.add(1);
//BFS
while(deq.size()>0){
int x = deq.pollFirst();
int y = deq.pollFirst();
//上下左右に移動できるなら移動する(通過したところも記録しておく)
//停止する箇所が探索済みでないならDequeに格納する
if(S[x+1][y]=='.'){
int nx = x+1;
while(S[nx+1][y]=='.')
checked[nx++][y] = true;
if(!checked[nx][y]){
deq.add(nx);
deq.add(y);
checked[nx][y] = true;
}
}
if(S[x-1][y]=='.'){
int nx = x-1;
while(S[nx-1][y]=='.')
checked[nx--][y] = true;
if(!checked[nx][y]){
deq.add(nx);
deq.add(y);
checked[nx][y] = true;
}
}
if(S[x][y+1]=='.'){
int ny = y+1;
while(S[x][ny+1]=='.')
checked[x][ny++] = true;
if(!checked[x][ny]){
deq.add(x);
deq.add(ny);
checked[x][ny] = true;
}
}
if(S[x][y-1]=='.'){
int ny = y-1;
while(S[x][ny-1]=='.')
checked[x][ny--] = true;
if(!checked[x][ny]){
deq.add(x);
deq.add(ny);
checked[x][ny] = true;
}
}
}
//通過、停止済みのマスの数え上げ
int count = 0;
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
if(checked[i][j])
count++;
//答えの出力
out.println(count);
out.close();
}
}
実装汚い…。
E - Defect-free Squares
問題文はこちら
公式解説では左、上、左上のテーブルの最小値で更新していますが、左と左上、上と左上に分解して解きました。
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 ) {
//H、W、Nの受け取り
int H = sc.nextInt();
int W = sc.nextInt();
int N = sc.nextInt();
//穴空きマスの記録
boolean[][] isEmpty = new boolean[H+1][W+1];
while(N-->0){
int a = sc.nextInt();
int b = sc.nextInt();
isEmpty[a][b] = true;
}
//縦方向への空きマスの寄与のみを考えた時の、自分を右下とする最大の正方形の大きさ(辺の長さ)
int[][] sumH = new int[H+1][W+1];
for(int i=1;i<=H;i++)
Arrays.fill(sumH[i],Integer.MAX_VALUE);
for(int i=1;i<=H;i++)
for(int j=1;j<=W;j++)
if(!isEmpty[i][j])
sumH[i][j] = Math.min(sumH[i-1][j],sumH[i-1][j-1])+1;
else
sumH[i][j] = 0;
//横方向への空きマスの寄与のみを考えた時の、自分を右下とする最大の正方形の大きさ(辺の長さ)
int[][] sumW = new int[H+1][W+1];
for(int i=1;i<=H;i++)
for(int j=1;j<=W;j++)
if(!isEmpty[i][j])
sumW[i][j] = Math.min(sumW[i-1][j-1],sumW[i][j-1])+1;
//数え上げ用変数
long sum = 0;
//全マスの最大の正方形の大きさを加算
//n×nが作れるなら(n-1)×(n-1)も作れるはずで、その要領で数え上げると
//そのマスを右下とした正方形はn個作れるので
for(int i=1;i<=H;i++){
for(int j=1;j<=W;j++){
sum += Math.min(sumH[i][j],sumW[i][j]);
}
}
//総和の出力
out.println(sum);
out.close();
}
}
なんかいろいろとぐちゃぐちゃしちゃってますが、コンテスト中の焦り故の結果です…。
感想
A,B:易しい
C:最初びっくりしたけど非再帰DFSと気付いてからはサクッと
D:制約的に間に合うかな～とか思って実装した
E:なかなか思いつかなかった…
って感じでした。
Fねぇ…DPで、右側から更新したら良さそうだなぁ～とかは思いついたんですが、遷移の仕方とか持つべき状態とか思いつかなくてダメダメでした…。