はじめに
今回はコンテスト中にDまで、コンテスト後にFまで解いたのでFまで載せようと思います。
なお、僕のライブラリに関しては提出結果をご確認ください。
では、見ていきましょう。
A - Three Threes
問題文はこちら
Stringのrepeatメソッドを用いると楽です。
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();
//NをN回繰り返したStringを出力
out.println((""+N).repeat(N));
out.close();
}
}
B - Pentagon
問題文はこちら
二つの線分の長さは$2$通りしか無いので$4$通り全部書けば良いです。
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、Tの受け取り(後々楽なのでソートしておく)
char[] S = sc.nextCharArray();
char[] T = sc.nextCharArray();
Arrays.sort(S);
Arrays.sort(T);
//頑張って分岐させる
if(S[0]+1==S[1]||S[0]=='A'&&S[1]=='E'){
if(T[0]+1==T[1]||T[0]=='A'&&T[1]=='E'){
out.println("Yes");
}
else{
out.println("No");
}
}
else if(T[0]+1==T[1]||T[0]=='A'&&T[1]=='E'){
out.println("No");
}
else{
out.println("Yes");
}
out.close();
}
}
C - Repunit Trio
問題文はこちら
入力例$3$に最大ケースがあり、そんなに大きく無さそうなのが読み取れます。
ですので、最大のレピュニットを決めうって、他の二つを探索することで作れる数の合計が$N$を超えるまで回してあげれば答えが出ます。
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個になるまでレピュニット同士の和を小さい方から列挙する
TreeSet<Long> set = new TreeSet<>();
int N = sc.nextInt();
long numI = 1;
for(int i=1;set.size()<N;i++){
long numJ = 1;
for(int j=1;j<=i;j++){
long numK = 1;
for(int k=1;k<=j;k++){
set.add(numI+numJ+numK);
numK *= 10;
numK++;
}
numJ *= 10;
numJ++;
}
numI *= 10;
numI++;
}
//N-1個取り出しておいて、N番目を出力
while(--N>0)
set.pollFirst();
out.println(set.pollFirst());
out.close();
}
}
D - Erase Leaves
問題文はこちら
頂点$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 SimpleWriter out = new SimpleWriter(System.out,autoFlush);
public static void main(String[] args){
//Nの受け取り
int N = sc.nextInt();
//頂点1と直接連結している頂点を記録しながらUnionFindの構築
ArrayList<Integer> list = new ArrayList<>();
UnionFind uf = new UnionFind(N+1);
for(int i=1;i<N;i++){
int u = sc.nextInt();
int v = sc.nextInt();
if(u==1)
list.add(v);
else if(v==1)
list.add(u);
else
uf.unite(u,v);
}
//頂点1と連結している頂点が1個だけならさっさと出力しちゃう(しなくても良いけど)
if(list.size()==1){
out.println(1);
}
else{
//sum-maxを求めて、頂点1を削除する分の+1を加算して出力
int max = 0;
int sum = 0;
for(int r:list){
max = Math.max(max,uf.size(r));
sum += uf.size(r);
}
out.println(sum-max+1);
}
out.close();
}
}
なんか実装に手こずってしまいました…。
E - Takahashi Quest
問題文はこちら
公式解説にあるとおり、貪欲で解けます。
所持数の最大値はimos法の要領で求められます。
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の受け取り
int N = sc.nextInt();
//ポーションの増減を記録する配列
int[] query = new int[N];
//直近で出現したイベント1を記録するList
ArrayList<ArrayDeque<Integer>> list = new ArrayList<>();
for(int i=0;i<=N;i++)
list.add(new ArrayDeque<>());
//貪欲に処理
for(int i=0;i<N;i++){
int t = sc.nextInt();
int x = sc.nextInt();
if(t==1){
list.get(x).add(i);
}
else{
query[i] = -1;
if(list.get(x).size()==0){ //勝てないとき
System.out.println(-1);
return;
}
query[list.get(x).pollLast()] = 1;
}
}
//答えを構築しながらimos法で最大値を求める
ArrayList<Integer> answer = new ArrayList<>();
int sum = 0;
int max = 0;
for(int num:query){
sum += num;
if(0<=num)
answer.add(num);
max = Math.max(sum,max);
}
//答えの出力
out.println(max);
out.println(answer);
out.close();
}
}
紙に書いて確認しようとしたんですが、メモが間違っていたために貪欲法ではだめだと思ってずっと考えていたらコンテストが終わっていました…。
F - Bomb Game 2
問題文はこちら
動的計画法で解きました。
遷移の仕方は公式解説に任せます。
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の受け取り
int N = sc.nextInt();
//DPテーブルの構築
long[][] dp = new long[N+1][];
//定数
final int MOD = 998244353;
final int invTwo = (MOD>>1)+1;
//初期値代入
dp[1] = new long[]{1};
//遷移
for(int i=2;i<=N;i++){
dp[i] = new long[i];
long d = MathFunction.modPow(2,i,MOD);
d *= MathFunction.modPow(d-1,MOD-2,MOD);
d %= MOD;
for(int j=0;j+1<i;j++){
dp[i][0] += dp[i-1][j]*MathFunction.modPow(invTwo,i-j,MOD)%MOD;
dp[i][0] %= MOD;
}
for(int j=1;j<i;j++){
dp[i][j] = MOD+dp[i][j-1]-dp[i-1][j-1]*MathFunction.modPow(invTwo,i,MOD)%MOD;
dp[i][j] += dp[i-1][j-1];
dp[i][j] %= MOD;
dp[i][j] *= invTwo;
dp[i][j] %= MOD;
}
for(int j=0;j<i;j++){
dp[i][j] *= d;
dp[i][j] %= MOD;
}
}
//答えの出力
out.println(dp[N]);
out.close();
}
}
DPで解けるのまでは気付いたんですけどね…。
俺は無力だ…。
感想
A,B,C:易しい
D:実装に手こずってしまったけど難易度自体は易しい方
E:う～ん…とりあえず実装して投げれば良かったか…
F:遷移が何も出なかった…
って感じでした。
二度目の落水…悲しい…。