はじめに
今回もEまでコンテスト中に解けたのでそれをそのまま載せようと思います。
では、見ていきましょう。
※テンプレ等、実際の提出が見たい方はこちらからどうぞ
A - Pawn on a Grid
問題文はこちら
#の位置を数え上げれば良いですね。
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){
//H、Wの受け取り
int H = System.in.nextInt();
int W = System.in.nextInt();
//#の数え上げ
int count = 0;
for(int i=0;i<H;i++)
for(int j=0;j<W;j++)
if(System.in.nextChar()=='#')
count++;
//答えの出力
System.out.println(count);
System.out.close();
}
}
二重forは以下のように書き換えても良いかもしれません。
A改.java
//H行分繰り返す
for(int i=0;i<H;i++){
//Siを受け取って拡張for文で探す
char[] S = System.in.next().toCharArray();
for(char c:S)count += c=='#'?1:0;
}
まぁ特に悩みはしなかったです。
B - Inverse Prefix Sum
問題文はこちら
$i$番目までの総和を記録しながら、$A_{i+1}$を計算して総和に加算する、というのを順に繰り返しました。
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、Sの受け取り
int N = System.in.nextInt();
int[] S = System.in.nextInt(N);
//これまでの総和を記録する変数
long now = 0;
//順に条件を満たすAiを求めて出力
for(int num:S){
System.out.print((num-now)+" ");
now += num-now;
}
//念のため改行
System.out.println();
System.out.close();
}
}
これもそこまで難しくないですね。
C - Extra Character
問題文はこちら
$i$番目に挿入された=$S$の$i$番目と$T$の$i$番目が異なるので、そのような$i$を探しました。
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){
//S、Tの受け取り
String S = System.in.next();
String T = System.in.next();
//別変数に記録しておく
int len = S.length();
//0～lenまでに相違点が見つかったか記録する変数
boolean find = false;
//順に比較して探す
for(int i=0;i<len;i++){
if(S.charAt(i)!=T.charAt(i)){
System.out.println(i+1);
find = true;
break;
}
}
//Sの末尾に挿入されている時用
if(!find)
System.out.println(len+1);
System.out.close();
}
}
$S$をS+" "にしておけば最後の場合分けがいりませんでしたね。
D - Factorial and Multiple
問題文はこちら
事前に$K$の素因数を列挙してHashMapに記録して(keyは素因数、valueは個数)、各素因数が個数分表れる最小の$N!$を探し、それぞれの素因数での$N$の最大値を求めました。
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){
//Kの受け取り
long K = System.in.nextLong();
//素因数とその個数を記録するmap
HashMap<Long,Integer> list = new HashMap<>();
//素因数候補
long div = 2;
//√Kまで試す
while(div*div<=K){
//素因数ならKをそれで割っておく&listに記録
if(K%div==0){
list.merge(div,1,(i,j) -> i+j);
K /= div;
}else
div++;
}
//最後のKも入れておく
list.merge(K,1,(i,j) -> i+j);
//答えを記録する変数(なんとなく2にしただけで、0でも-1でも良い)
long ans = 2;
//各素因数を個数分だけ持つN!を探す
for(Long key:list.keySet()){
//mult番目のkeyの倍数まで使う
int mult = 0;
//keyの数
int count = 0;
//mult番目のkeyの倍数の値
long now = key;
//countが目的の個数に達するまで繰り返す
while(count<list.get(key)){
mult++;
//nowのkeyの個数をcountに加算
while(now%key==0){
now /= key;
count++;
}
//nowを更新
now = (mult+1)*key;
}
//temp!でちょうど条件を満たす
long temp = key*mult;
//ansより大きかったら更新
if(ans<temp)
ans = temp;
}
//答えの出力
System.out.println(ans);
System.out.close();
}
}
素因数の数を数える方法がなかなか浮かばなくてペナルティを頂いてしまいました･･･。
E - Critical Hit
問題文はこちら
動的計画法で解きました。
$dp[i]:$残りの体力が$i$の時の攻撃回数の期待値の$\mathrm{mod}\ 998244353$
として$0$から順に更新して$dp[N]$を求めました。
E.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、Pの受け取り
int N = System.in.nextInt();
int P = System.in.nextInt();
//dp[i]:体力がiの時の攻撃回数の期待値
long[] dp = new long[N+1];
//0の時は操作しないので0、1の時は絶対1回なので1
dp[0] = 0;
dp[1] = 1;
int mod = 998244353;
//ダメージが1の時、2の時の確率を事前計算
long div = System.modPow(100,mod-2,mod);
long d1 = (100-P)*div%mod;
long d2 = P*div%mod;
//遷移
for(int i=2;i<=N;i++){
//2ダメージ与えたときの期待値
long sum = (dp[i-2]+1)*d2%mod;
//1ダメージ与えたときの期待値
sum += (dp[i-1]+1)*d1%mod;
//和の%modをdp[i]に
dp[i] = sum%mod;
}
//体力がNの時の期待値をしゅつりょく
System.out.println(dp[N]);
System.out.close();
}
}
想像よりサクッと解けました。
感想
A:グリッドに苦手意識があるのでAから出てくるのか･･･と面食らったが、そんなに難しくはなかった
B:理解するのに時間がかかってしまったが、これも易しい
C:Cにしては易しい？
D:ペナルティをいっぱい頂いたのが心残り･･･
E:Eにしては易しい？
って感じでした。
入水･･･ってなるはずが、ペナルティのせいかレートが5足りませんでした。非常に悔しい･･･。