はじめに
今回はコンテスト中にEまで、コンテスト後にFまで解いたのでそれを載せようと思います。
なお、僕のライブラリは提出結果よりご確認ください。
では、見ていきましょう。
A - Scoreboard
問題文はこちら
愚直に数え上げて答えを求めました。
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){
//Nの受け取り
int N = sc.nextInt();
//得点数え上げ
int X = 0;
int Y = 0;
while(N-->0){
X += sc.nextInt();
Y += sc.nextInt();
}
//答えの出力
out.println(X>Y?"Takahashi":X<Y?"Aoki":"Draw");
out.close();
}
}
B - Extended ABC
問題文はこちら
先頭3種の文字を圧縮してABCの部分列かどうかを判定すれば良いので、それを実装しました。
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){
//Sの受け取り
String S = sc.next();
//3文字目まで圧縮
while(S.length()>1&&S.charAt(0)=='A'&&S.charAt(1)=='A')
S = S.substring(1);
while(S.length()>2&&S.charAt(1)=='B'&&S.charAt(2)=='B')
S = S.charAt(0)+S.substring(2);
while(S.length()>3&&S.charAt(2)=='C'&&S.charAt(3)=='C')
S = S.substring(0,2)+S.substring(3);
//ABCの部分列か判定
Set<String> set = Set.of("A","B","C","AB","AC","BC","ABC");
out.println(set.contains(S)?"Yes":"No");
out.close();
}
}
C - Lining Up 2
問題文はこちら
$i$番目の人の後ろの人を$\mathrm{next}[i]$とすると、$\mathrm{next}[A[j]]=j$なので、$\mathrm{next}$を構築して先頭から順に遷移して答えを求めました。
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の受け取り
int N = sc.nextInt();
//自分の次が誰か、最初は誰かを求めておく
int[] next = new int[N+1];
int first = -1;
for(int i=1;i<=N;i++){
int A = sc.nextInt();
if(A>0)
next[A] = i;
else
first = i;
}
//答えの構築
int[] ans = new int[N];
for(int i=0;i<N;i++){
ans[i] = first;
first = next[first];
}
//出力
out.println(ans);
out.close();
}
}
D - Cheating Gomoku Narabe
問題文はこちら
特に特別なことはせず、見ている区間をスライドしながら答えを求めました。
区間に含まれなくなるマスと含まれるようになるマスの2箇所の増減しかしないので十分高速に処理できます。
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){
//H、W、K、Sの受け取り
int H = sc.nextInt();
int W = sc.nextInt();
int K = sc.nextInt();
char[][] S = sc.nextCharArray(H);
//最小値記録用
int ans = K+1;
//スライドさせながら見ていく(横)
if(K<=W){
for(int i=0;i<H;i++){
int o = 0;
int x = 0;
int dot = 0;
for(int j=0;j<K;j++)
switch(S[i][j]){
case 'o' -> o++;
case 'x' -> x++;
case '.' -> dot++;
}
if(x==0)
ans = Math.min(ans,dot);
for(int j=K;j<W;j++){
switch(S[i][j]){
case 'o' -> o++;
case 'x' -> x++;
case '.' -> dot++;
}
switch(S[i][j-K]){
case 'o' -> o--;
case 'x' -> x--;
case '.' -> dot--;
}
if(x==0)
ans = Math.min(ans,dot);
}
}
}
//縦方向も見る
if(K<=H){
for(int j=0;j<W;j++){
int o = 0;
int x = 0;
int dot = 0;
for(int i=0;i<K;i++)
switch(S[i][j]){
case 'o' -> o++;
case 'x' -> x++;
case '.' -> dot++;
}
if(x==0)
ans = Math.min(ans,dot);
for(int i=K;i<H;i++){
switch(S[i][j]){
case 'o' -> o++;
case 'x' -> x++;
case '.' -> dot++;
}
switch(S[i-K][j]){
case 'o' -> o--;
case 'x' -> x--;
case '.' -> dot--;
}
if(x==0)
ans = Math.min(ans,dot);
}
}
}
//答えがあるならそれを無ければ-1
out.println(ans>K?-1:ans);
out.close();
}
}
E - Bad Juice
問題文はこちら
毒入りワインだかなんだかみたいな問題設定で有名なやつに似てますね。
$N$を二進数表記したときの桁数と同じだけ人数がいれば特定は可能なので(二進数表記の各桁に$M$人の人を割り当てれば、飲んだか飲んでないかの$2$通りを$01$で表現できるので)、$M=\lceil \log_2 N \rceil$になります。
E.java
final class Main{
private static final boolean autoFlush = true;
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の受け取り
int N = sc.nextInt();
//人数決め
int M = 0;
while(N>1<<M)
M++;
out.println(M);
//各人が飲む番号を記録
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
for(int i=0;i<M;i++)
list.add(new ArrayList<>());
for(int i=1;i<=N;i++)
for(int j=0;j<M;j++)
if((i&(1<<j))>0)
list.get(j).add(i);
//出力
for(ArrayList<Integer> temp:list){
out.print(temp.size());
out.print(" ");
out.println(temp);
}
//答えの受け取り(文字列を反転させて2進数として解釈)
int ans = Integer.parseInt(Converter.reverse(sc.next()),2);
if(ans==0)
ans = N;
//出力
out.println(ans);
out.close();
}
}
変に$+1$しちゃったりしてペナ出したのほんと良くなかった…。
F - Usual Color Ball Problems
問題文はこちら
公式解説と同じで、どの色が箱を占有しているかだけが重要なので、尺取り法の要領で答えを求めました。
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、M、K、Cの受け取り(便宜上Cは二つ連結させた形に)
int N = sc.nextInt();
int M = sc.nextInt();
int K = sc.nextInt();
int[] C = new int[N<<1];
for(int i=0;i<N;i++)
C[i] = C[i+N] = sc.nextInt();
//先に数え上げをしておく
HashMap<Integer,Integer> map = new HashMap<>();
int[] count = new int[N+1];
for(int i=0;i<N;i++)
count[C[i]]++;
//尺取の要領で各答えをもとめｒ
int r = 0;
int sum = 0;
int kind = 0;
for(int l=0;l<N;l++){
while(r<N+l&&kind<M){
map.merge(C[r],1,Integer::sum);
if(K==1||map.get(C[r])%K==1){
sum += Math.min(K,count[C[r]]-(map.get(C[r])-1)/K*K);
kind++;
}
r++;
}
out.println(sum);
map.merge(C[l],-1,Integer::sum);
if(map.get(C[l])%K==0){
sum -= Math.min(K,count[C[l]]-map.get(C[l]));
kind--;
}
}
out.close();
}
}
最後投げたけど、ちょっとしたところミスってて間に合わず…悔しい…。
感想
A:易しい
B:Bにしてはほんのり難しめ？
C:解法さえ浮かべばサクッとできる
D:易しめ
E:問題自体は易しめ
F:気付くまでが遅すぎた…
って感じでした。
むむむ…今度こそは再入青したい…！