はじめに
今回はDまでしか解けなかったのでDまで載せようと思います。
では、見ていきましょう。
A - Majority
問題文はこちら
先頭の文字だけ見ればどちらか判別できるので、先頭の文字がFのものを数えて過半数か判定しました。
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){
//Nの受け取り
int N = System.in.nextInt();
//総数
int count = 0;
//一文字目がFのものを数える
for(int i=0;i<N;i++)
if(System.in.next().charAt(0)=='F')
count++;
//過半数か？
System.out.println(count*2>N?"Yes":"No");
System.out.close();
}
}
まぁ問題はないですね。
B - Postal Card
問題文はこちら
boolean型配列で$M$個の中に含まれるかを記録しておき、$S$を数字として受け取って$S$%$1000$が存在するかを判定しました。
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、Sの受け取り(Sは数値として)
int N = System.in.nextInt();
int M = System.in.nextInt();
int[] S = System.in.nextInt(N);
//Tが存在するか
boolean[] isT = new boolean[1000];
while(M-->0){
int T = System.in.nextInt();
isT[T] = true;
}
//Tの中にSがある数を数える
int count = 0;
for(int s:S)
if(isT[s%1000])
count++;
//出力
System.out.println(count);
System.out.close();
}
}
これもそこまで悩まなかったです。
C - Path Graph?
問題文はこちら
パスグラフの条件を満たすものは次数が$1$の頂点が$2$個、$2$の頂点が$N-2$個の連結グラフだと言い換えられるので、それを判定しました。
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();
//各頂点の次数
int[] count = new int[N+1];
//連結か見る用のUnionFind
UnionFind uf = new UnionFind(N);
//連結と次数の加算
while(M-->0){
int u = System.in.nextInt();
int v = System.in.nextInt();
count[u]++;
count[v]++;
uf.unite(u-1,v-1);
}
//次数が1のもの、2のもの、その他のもの
int count1 = 0;
int count2 = 0;
int countAny = 0;
//それぞれの次数に合わせて変数を増加
for(int num:count){
if(num==1)
count1++;
else if(num==2)
count2++;
else
countAny++;
}
//頂点0の分が数えられているのでcountAnyは1になっていて、それ以外は上記の条件で判定
System.out.println(count1==2&&count2==N-2&&countAny==1&&uf.groupCount()==1?"Yes":"No");
System.out.close();
}
}
連結かどうかを判定し忘れてずっと頭抱えてました…。
↓通らないケース
5 4
1 2
3 4
4 5
3 5
D - Match or Not
問題文はこちら
$x$から$x+1$に変化するときの$S'$の変化は$x$文字目が$S$の$|S|-x$番目から$x$番目の文字に入れ替わるだけなので、最初に$x=0$の時の不一致な箇所を数えておき、$x=1,2,...,|T|$では不一致が増えたか減ったかのみを見ることで解けると思い、それを実装しました。
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){
//S、Tの受け取り
char[] S = System.in.nextCharArray();
char[] T = System.in.nextCharArray();
//不一致の数を数える
int falseCount = 0;
for(int i=0;i<T.length;i++){
if(S[S.length-T.length+i]!=T[i]&&S[S.length-T.length+i]!='?'&&T[i]!='?')
falseCount++;
}
//最初x=0の時の判定
System.out.println(falseCount==0?"Yes":"No");
//x=1～|T|
for(int i=0;i<T.length;i++){
//最初不一致だったなら解消されるので-1
if(S[S.length-T.length+i]!=T[i]&&S[S.length-T.length+i]!='?'&&T[i]!='?')
falseCount--;
//変化後が不一致なら+1
if(S[i]!=T[i]&&S[i]!='?'&&T[i]!='?')
falseCount++;
//全部一致=falseCountが0か？
System.out.println(falseCount==0?"Yes":"No");
}
System.out.close();
}
}
Cで悩んだときに先にこっちに着手できたのは良かったです。
感想
A,B:易しい
C:考察抜けがあって沼った…。
D:比較的易しい気がする
って感じでした。
めちゃくちゃレート下がりました…。次回取り返せるかな…。
追記(E - Karuta)
問題文はこちら
詳しい説明は公式解説に任せます。
E.java
import java.util.Scanner;
import java.util.Arrays;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//Nの受け取り
int N = sc.nextInt();
//文字列に何番目のものかという情報も持たせたいのでクラス定義
class Pair implements Comparable<Pair>{
int id;
String str;
Pair(int i,String s){
id = i;
str = s;
}
@Override
public int compareTo(Pair p){
return str.compareTo(p.str);
}
}
//文字列の受け取り
Pair[] S = new Pair[N];
for(int i=0;i<N;i++)
S[i] = new Pair(i,sc.next());
//文字列でソート
Arrays.sort(S);
//前後比較してより良い方を格納
int[] ans = new int[N];
for(int i=0;i<N;i++){
int len1 = 0<i?check(S[i].str,S[i-1].str):0;
int len2 = i<N-1?check(S[i].str,S[i+1].str):0;
ans[S[i].id] = Math.max(len1,len2);
}
//出力高速化のための作業
StringBuilder sb = new StringBuilder();
for(int num:ans){
sb.append(num);
sb.append("\n");
}
//答えの出力
System.out.println(sb.toString());
}
//比較メソッド
static int check(String S1,String S2){
int len = Math.min(S1.length(),S2.length());
for(int i=0;i<len;i++)
if(S1.charAt(i)!=S2.charAt(i))
return i;
return len;
}
}
「ソートして前後しか見なくて良い」という発想になれませんでした…精進不足ですね。