はじめに
今回はコンテスト中にD問題まで解けたのでそれを載せようと思います。
では見ていきましょう。
なお、自作ライブラリの内容を確認したいときは提出結果からご確認ください。
A - Overall Winner
問題文はこちら
勝利数が同数の時を考えるのがめんどうなので$N$が偶数の時は$N-1$まで見るようにして判定しました。
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();
//偶数だったら-1
N -= (N+1)%2;
//高橋君が勝った回数を数える
int count = 0;
for(int i=0;i<N;i++){
if(sc.nextChar()=='T')
count++;
else
count--;
}
//高橋君の方が多いかどうか
out.println(count>0?"T":"A");
out.close();
}
}
まぁ易しい問題ですね。
B - Fill the Gaps
問題文はこちら
$A_1$を受け取り、それ以降$A_{i+1}$を受け取って、$A_i \pm 1$から$A_{i+1} \mp 1$まで順に出力することで解きました。
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、A_1の受け取り
int N = sc.nextInt();
int A = sc.nextInt();
//とりあえず出力
out.print(A);
//それぞれ間を埋めるように出力
while(--N>0){
int nextA = sc.nextInt();
int d = Integer.signum(nextA-A);
for(int i=A+d;i!=nextA;i+=d)
out.print(" "+i);
out.print(" "+nextA);
A = nextA;
}
//おまけの改行
out.println();
out.close();
}
}
これもそこまで難しくは無いですね。
C - AtCoder Cards
問題文はこちら
ちょっとめんどくさい感じに解いてしまいましたが、事前に@の数を数えておき、atcoderに含まれるか否かで別々に集計して、atcoderに含まれる文字で差を@で埋められるか、他の文字の数は一緒かを見ることで判定しました。
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 ) {
//S、Tの受け取り
char[] S = sc.nextCharArray();
char[] T = sc.nextCharArray();
//@の数え上げ
int countS = 0;
int countT = 0;
for(char c:S)
if(c=='@')
countS++;
for(char c:T)
if(c=='@')
countT++;
//atcoder中の文字か否かで別々に数え上げ
HashMap<Character,Integer> atcoder = new HashMap<Character,Integer>();
HashMap<Character,Integer> map = new HashMap<Character,Integer>();
for(char c:S)
if("atcoder".contains(""+c))
atcoder.merge(c,1,Integer::sum);
else if(c!='@')
map.merge(c,1,Integer::sum);
for(char c:T)
if("atcoder".contains(""+c))
atcoder.merge(c,-1,Integer::sum);
else if(c!='@')
map.merge(c,-1,Integer::sum);
//atcoder中の文字以外で数が合ってなかったら揃えられない
for(int num:map.values()){
if(num!=0){
System.out.println("No");
return;
}
}
//うまく埋め合わせができるか調べる
for(int num:atcoder.values()){
if(num<0)
countS += num;
else
countT -= num;
}
out.println(countS>=0&&countT>=0?"Yes":"No");
out.close();
}
}
結構悩んでしまいました。特に、atcoderに含まれる文字のみを@で置き換えられることを気付いて無くてかなり時間をかけてしまいました。
D - Bitmask
問題文はこちら
1であるところのみを先に見て、その時点で$N$を超えていれば答えが存在しないので-1を出力します。
あとは先頭から貪欲に'?'を1に変換することで解きました。
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 ) {
//S、Nの受け取り
char[] S = sc.nextCharArray();
long N = sc.nextLong();
//?が全部0だった時の値を求める
long sum = 0;
for(int i=0;i<S.length;i++)
if(S[i]=='1')
sum += 1L<<S.length-i-1;
//この時点でNを超えているなら解無し
if(sum>N){
System.out.println(-1);
return;
}
//先頭から貪欲に?を変えていく
for(int i=0;i<S.length;i++){
if(S[i]=='?'){
long num = 1L<<S.length-i-1;
if(sum+num<=N)
sum += num;
}
}
//答えのしゅつりょく
out.println(sum);
out.close();
}
}
これはすぐ気付けました。
感想
A,B:易しい
C:結構悩んでしまった
D:典型かも？
って感じでした。
Eが解けなかったのが結構心残りですね…。もっと精進します。