はじめに
今回はEまで解けたのでそのままそれを載せようと思います。
では、見ていきましょう。
なお、ライブラリは提出結果からご確認下さい。
A - Similar String
問題文はこちら
$S$と$T$が異なるときに、異なる箇所が$0$と$o$の組み合わせ、$1$と$l$の組み合わせかを判定することで解きました。
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、S、Tの受け取り
int N = sc.nextInt();
String S = sc.next();
String T = sc.next();
//先頭から一致してるか見る
for(int i=0;i<N;i++){
if(S.charAt(i)!=T.charAt(i)){
//似てる場合ではないときで不一致ならNoを出力して終了する
if(S.charAt(i)=='1'||S.charAt(i)=='l'){
if(T.charAt(i)!='1'&&T.charAt(i)!='l'){
System.out.println("No");
return;
}
}
else if(S.charAt(i)=='0'||S.charAt(i)=='o'){
if(T.charAt(i)!='0'&&T.charAt(i)!='o'){
System.out.println("No");
return;
}
}
else{
System.out.println("No");
return;
}
}
}
//ループを抜けた=似てるからYes
out.println("Yes");
out.close();
}
}
B解いてるあたりでユーザー解説にあるような解き方をすればサクッと解けたなぁと思いました。もっと早く気づけるようになりたい…。
B - Discord
問題文はこちら
自分よりも番号が大きくて不仲である可能性がある人をHashSet<Integer>で管理して、隣り合っている人をそこから消すことで求めました。
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、M、aの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int[][] a = sc.nextInt(M,N);
//不仲な可能性のある人として全組を入れておく
ArrayList<HashSet<Integer>> list = new ArrayList<>();
list.add(new HashSet<>());
for(int i=1;i<=N;i++){
HashSet<Integer> set = new HashSet<>();
for(int j=i+1;j<=N;j++)
set.add(j);
list.add(set);
}
//隣り合う組を不仲候補から消す
for(int[] A:a){
for(int i=1;i<N;i++){
list.get(Math.min(A[i-1],A[i])).remove(Math.max(A[i-1],A[i]));
}
}
//不仲候補の数え上げ
int ans = 0;
for(HashSet<Integer> set:list)
ans += set.size();
//答えの出力
out.println(ans);
out.close();
}
}
公式解説の全探索のやり方の方が良かったかな…どうだろ…。
C - Dash
問題文はこちら
シミュレーションで解きました。
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、M、H、K、Sの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int H = sc.nextInt();
int K = sc.nextInt();
String S = sc.next();
//アイテムのあるマスをHashSetに入れる
HashSet<Point> set = new HashSet<>();
for(Point p:sc.nextPoint(M))
set.add(p);
//シミュレーション
boolean canMove = true;
int x = 0;
int y = 0;
for(char c:S.toCharArray()){
if(c=='L')
x--;
if(c=='R')
x++;
if(c=='U')
y++;
if(c=='D')
y--;
H--;
canMove &= 0<=H; //負になったかどうかを記録しておく
if(set.contains(new Point(x,y))){
if(H<K){
set.remove(new Point(x,y)); //アイテムを取ったら消す
H = K;
}
}
}
//一度も負にならなかった？
out.println(canMove?"Yes":"No");
out.close();
}
}
最初アイテムを使用したときにremoveするのを忘れててペナルティを頂いてしまいました。
問題文は、ちゃんと読もう(自戒)。
D - Shift vs. CapsLock
問題文はこちら
動的計画法で解きました。
公式解説の遷移と大体同じです。
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 ) {
//X、Y、Z、Sの受け取り
int X = sc.nextInt();
int Y = sc.nextInt();
int Z = sc.nextInt();
String S = sc.next();
//dp[i][j]:i文字目までにかかる時間(j=0ならCapsLockがoff、j=1ならon)
long[][] dp = new long[S.length()+1][2];
dp[0][1] = Z;
//遷移
for(int i=0;i<S.length();i++){
char c = S.charAt(i);
dp[i+1][0] = Math.min(dp[i][0]+(c=='a'?X:Y),Z+dp[i][1]+(c=='a'?X:Y));
dp[i+1][1] = Math.min(Z+dp[i][0]+(c=='A'?X:Y),dp[i][1]+(c=='A'?X:Y));
}
//小さい方を出力
out.println(Math.min(dp[S.length()][0],dp[S.length()][1]));
out.close();
}
}
ちょっと不安でしたが通ったので良かったです。
E - A Gift From the Stars
問題文はこちら
ちょっと実装が汚いですけど、BFSで解きました。
適当に次数が1の頂点を見つけて、そこから次数が2以上の頂点を辿って探しました。
スターグラフ同士を結ぶ頂点かどうかを識別するための数字もArrayDequeに入れてます。
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の受け取り
int N = sc.nextInt();
//隣接リストの構築
ArrayList<HashSet<Integer>> list = new ArrayList<>();
for(int i=0;i<=N;i++)
list.add(new HashSet<>());
for(int i=1;i<N;i++){
int u = sc.nextInt();
int v = sc.nextInt();
list.get(u).add(v);
list.get(v).add(u);
}
//次数が1のところを記録
ArrayList<Integer> one = new ArrayList<>();
for(int i=1;i<=N;i++){
if(list.get(i).size()==1)
one.add(i);
}
//答えを入れとく用のArrayList
ArrayList<Integer> answer = new ArrayList<>();
//適当に次数1のところから行ける頂点(=どっかのスターグラフの中心)
int node = list.get(one.get(0)).iterator().next();
//BFSをする
ArrayDeque<Integer> deq = new ArrayDeque<>();
boolean[] checked = new boolean[N+1];
checked[node] = true;
deq.add(node);
deq.add(0); //0なら中心、1なら接続部として区別
while(deq.size()>0){
int now = deq.pollFirst();
int id = deq.pollFirst();
if(id==1){
for(int next:list.get(now)){
if(!checked[next]){
checked[next] = true;
//接続部から移動すると他のスターグラフとの接続部に移動するので、
//さらに一個進めてArrayDequeに入れる
Iterator<Integer> iter = list.get(next).iterator();
int num = iter.next();
if(num==now)
num = iter.next();
checked[num] = true;
deq.add(num);
deq.add(0);
}
}
}
else{
//中心ならレベルをArrayListに記録
answer.add(list.get(now).size());
//接続部を見つけたらそこに移動
for(int next:list.get(now)){
if(!checked[next]&&list.get(next).size()>1){
checked[next] = true;
deq.add(next);
deq.add(1);
}
}
}
}
//ライブラリ的に出力がしやすいのでint[]に変換
int[] ans = new int[answer.size()];
for(int i=0;i<answer.size();i++)
ans[i] = answer.get(i);
//ソート
ArrayFunction.sort(ans);
//出力
out.println(ans);
out.close();
}
}
コンテスト後に書いたものですが、次数2以上の頂点を数え上げ、頂点の数を求めて、それと辻褄を合わせるように次数2の個数を減らすことで解く方法もあります。
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、隣接リストの受け取り
int N = sc.nextInt();
int[][] graph = sc.nextGraph(N,N-1);
//次数別にカウントするようのバゲット
int[] map = new int[N];
//次数が2以上のものを数え上げる用の変数
int count = 0;
for(int i=1;i<=N;i++){
if(graph[i].length>1){
map[graph[i].length]++;
count++;
}
}
//スターグラフの次数2以上の頂点の個数
int sum = (count-1)/3+1;
//スターグラフ同士の連結で次数が2になっている頂点分を引く
map[2] -= sum-1<<1;
//答えの構築
int[] ans = new int[sum];
int index = 0;
for(int i=2;i<N;i++)
while(map[i]-->0)
ans[index++] = i;
//出力(小さい方からansに記録しているのでソートは要らない)
out.println(ans);
out.close();
}
}
コンテスト中に思いつきはしたんですが、sumの計算式を間違えてしまって合わなくて、結局普通にBFSする解法に切り替えました。距離をmod3で考えるの、思いつきたかった…。
感想
A,B:易しい
C:ペナったけど易しい方
D:DPだな～って思ったけど遷移に漏れがないか不安だった
E:普通にBFSで見れば良い気はしたけど実装に手間取った
って感じでした。
なんか全体的に実装が遅かったです…。精進不足が出てしまった…。