はじめに
今回はFまで解けたのでそれをそのまま載せようと思います。
なお、僕のライブラリは提出結果よりご確認ください。
では、見ていきましょう。
A - Spread
問題文はこちら
char型配列として受け取って空白区切りで出力しました。
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の受け取り
char[] S = sc.nextCharArray();
//空白区切りで出力
out.println(S," ");
out.close();
}
}
B - Next
問題文はこちら
最大値を求めておいて、それ未満での最大値を愚直に探索しました。
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 ) {
//N、Aの受け取り
int N = sc.nextInt();
int[] A = sc.nextInt(N);
//最大値を求めておく
int max = MathFunction.max(A);
//最大値未満での最大値を求める
int ans = 0;
for(int i=0;i<N;i++)
if(MathFunction.rangeCheck(A[i],ans,max))
ans = A[i];
//答えの出力
out.println(ans);
out.close();
}
}
C - Count xxx
問題文はこちら
ある文字$c$を使った文字列は、$S$内の$c$が連続している部分列のうち最長のものだけを考えれば良く、HashMapを使って最長のものを記録して、それを使って作れる個数を数え上げることで解きました。
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、Sの受け取り
int N = sc.nextInt();
char[] S = sc.nextCharArray();
//尺取の要領で各文字の最長を求める
HashMap<Character,Integer> map = new HashMap<>();
int l = 0;
while(l<N){
int r = l;
while(r<N&&S[l]==S[r])
r++;
map.merge(S[l],r-l,Integer::max);
l = r;
}
//各文字で作れる種類数を数え上げ
int ans = 0;
for(int num:map.values())
ans += num;
//答えの出力
out.println(ans);
out.close();
}
}
文字が英小文字しかないので配列で管理しても良かったかなと解いてる途中で思いました。
D - Election Quick Report
問題文はこちら
雑にTreeMap<Integer,TreeSet<Integer>>を使って、得票数をkey、その得票数の人たちのsetを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 ) {
//N、Mの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
//「得票数=候補者」となるようなMapの構築
TreeMap<Integer,TreeSet<Integer>> map = new TreeMap<>();
int[] sum = new int[N+1];
map.put(0,new TreeSet<>());
for(int i=1;i<=N;i++)
map.get(0).add(i);
//票に合わせて遷移させる
while(M-->0){
int A = sc.nextInt();
map.get(sum[A]++).remove(A);
if(!map.containsKey(sum[A]))
map.put(sum[A],new TreeSet<>());
map.get(sum[A]).add(A);
//現時点での最大得票数の人で最小値の人を出力
out.println(map.lastEntry().getValue().first());
}
out.close();
}
}
公式解説にもありますが、得票数が最大の人だけを保持しておけば得票数を保持した配列だけで処理できます。
E - Stamp
問題文はこちら
動的計画法で解きました。
$\mathrm{dp}[i][j]$が、$S$の$i$文字目までを、$j=0$なら$T$の末尾ぴったりで、$j=1$なら$T$の連続部分列で構築可能かを表すようにして解きました。
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、M、S、Tの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
String S = sc.next();
String T = sc.next();
//DPテーブル(範囲外参照とかめんどくさかったのでテキトーに大きく)
boolean[][] dp = new boolean[S.length()*3][2];
//初期値設定(最初の文字は先頭から始めて欲しいのでj=1)
dp[0][1] = true;
//遷移
for(int i=1;i<=S.length();i++){
for(int j=1;j<=Math.min(T.length(),i);j++){
//i-jまでをTの末尾ピッタリで構築可能なら
//今から押すスタンプの後にi-jまでの部分に
//スタンプを押した場合が考えられるのでその遷移
dp[i][0] |= dp[i-j][0]&&S.substring(i-j,i).equals(T.substring(T.length()-j));
//i-jからiまでの区間のスタンプが
//i-j以前とi以降のスタンプの前に押されている場合
dp[i][1] |= dp[i-j][0]&&T.contains(S.substring(i-j,i));
//i-j以前のスタンプより後で
//i以降のスタンプより前に押されている場合
dp[i][1] |= dp[i-j][1]&&T.startsWith(S.substring(i-j,i));
//i-j以前のスタンプより後で、i以降のスタンプで自身に被っているものが無い場合
if(j==T.length())
dp[i][0] |= dp[i-j][1]&&S.substring(i-j,i).equals(T);
}
}
//Sの末尾がTの末尾ピッタリで終わるなら構築可能
out.println(dp[S.length()][0]?"Yes":"No");
out.close();
}
}
めちゃめちゃ悩んじゃいました…。
F - Colored Ball
問題文はこちら
箱の中のボールの色をHashSetで管理する用にし、多い方のSetに少ない方のSetを入れるようにすれば十分高速に処理できます。
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、Qの受け取り
int N = sc.nextInt();
int Q = sc.nextInt();
//初期状態の箱を表すHashSetを構築
ArrayList<HashSet<Integer>> list = new ArrayList<>();
list.add(new HashSet<>());
for(int i=0;i<N;i++){
HashSet<Integer> temp = new HashSet<>();
temp.add(sc.nextInt());
list.add(temp);
}
//順に処理
while(Q-->0){
//a、bの受け取り
int a = sc.nextInt();
int b = sc.nextInt();
//多い方に少ない方の要素を移すように処理
HashSet<Integer> temp1 = list.get(a);
HashSet<Integer> temp2 = list.get(b);
if(temp1.size()<temp2.size()){
var temp = temp1;
temp1 = temp2;
temp2 = temp;
}
for(Integer num:temp2)
temp1.add(num);
list.set(a,new HashSet<>());
list.set(b,temp1);
//合わせたSetの大きさを出力
out.println(temp1.size());
}
out.close();
}
}
Eよりもめちゃくちゃ簡単に感じたので助かりました。
感想
A,B,C,D：易しめ
E：めちゃくちゃ難航してしまった…
F：Fにしては易しめ？
って感じでした。
Eで焦っていっぱいペナルティを頂いてしまったので、もう少し落ち着いて取り組まなきゃなぁ…と感じました…。