はじめに
今回はコンテスト中にEまで、コンテスト後にGまで解いたのでそれを載せようと思います。
では見ていきましょう。
なお、ライブラリは提出結果よりご確認ください。
A - N-choice question
問題文はこちら
$A+B$を、$C$を受け取りながら探しました。
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、A、Bの受け取り
int N = sc.nextInt();
int A = sc.nextInt();
int B = sc.nextInt();
//探すもの
int ans = A+B;
//順に受け取って探す
for(int i=1;i<=N;i++){
if(sc.nextInt()==ans){
out.println(i);
break;
}
}
out.close();
}
}
まぁ問題は無さそうですね。
B - Same Map in the RPG World
問題文はこちら
縦方向のシフト、横方向のシフトを全通り試しながら一致するか調べました。
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 ) {
//H、Wの受け取り
int H = sc.nextInt();
int W = sc.nextInt();
//A、Bの受け取り
char[][] A = sc.nextCharArray(H);
char[][] B = sc.nextCharArray(H);
//シフト回数全探索
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
//一致しているか調べる
boolean isSame = true;
for(int k=0;k<H;k++){
for(int l=0;l<W;l++){
isSame &= A[(i+k)%H][(j+l)%W]==B[k][l];
}
}
//一致してたら終わり
if(isSame){
System.out.println("Yes");
return;
}
}
}
//ループを抜けた=解が見つからなかったのでNo
out.println("No");
out.close();
}
}
これもそこまで難しくはないですね。
C - Cross
問題文はこちら
全マスを調べて、#であるならそこを中心とするバツ印の大きさを調べました。
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 ) {
//H、Wの受け取り
int H = sc.nextInt();
int W = sc.nextInt();
//Cの受け取り
char[][] C = sc.nextCharArray(H);
//答え用の配列
int[] ans = new int[Math.min(H,W)];
//全探索
for(int i=1;i<H-1;i++){
for(int j=1;j<W-1;j++){
//#のマスならバツ印の大きさを求める
if(C[i][j]=='#'){
int k = 1;
for(;;k++){
if(i-k<0||H<=i+k||j-k<0||W<=j+k)
break;
boolean isTrue = true;
isTrue &= C[i-k][j-k]=='#';
isTrue &= C[i+k][j+k]=='#';
isTrue &= C[i-k][j+k]=='#';
isTrue &= C[i+k][j-k]=='#';
if(!isTrue)
break;
}
//バツ印ならansに加算
if(k>1){
ans[k-2]++;
}
}
}
}
//答えの出力(空白区切り)
out.println(ans);
out.close();
}
}
これもそこまで悩まないですね。ちょっとだけめんどくさいですけど。
D - AABCC
問題文はこちら
適当に$\sqrt{N}$までの素数を予め列挙しておき、$a$、$b$、$c$を全探索しました。
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 ) {
//Nの受け取り
long N = sc.nextLong();
//適当な大きさまでの素数を列挙
int[] primes = MathFunction.primes((int)Math.sqrt(N));
//数え上げ
int ans = 0;
for(int i=0;function(primes[i],primes[i],primes[i])<=N;i++){
for(int j=i+1;function(primes[i],primes[j],primes[j])<=N;j++){
for(int k=j+1;function(primes[i],primes[j],primes[k])<=N;k++){
ans++;
}
}
}
//答えの出力
out.println(ans);
out.close();
}
//メソッド化した方が楽そうだったので書いた
private static long function(long a,long b,long c){
return a*a*b*c*c;
}
}
入力例2からそんなに数が多くないと気づけたので早めに実装できました。
E - Dice Product 3
問題文はこちら
動的計画法で解きました。
TreeMapを用いて、keyになる確率をvalueに持つようにして保持し、小さい方から取り出して遷移しました。
なお$\frac{1}{5}$をかけている理由は、1が0回出て遷移する確率、1が1回出て遷移する確率、1が2回出て遷移する確率、…という風に考えて確率を求めると
$$\sum_{k=0}^{\infty}{\frac{1}{6} \times \frac{1}{6^k}}=\frac{1}{5}$$
になるからです。
E.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の受け取り
long N = sc.nextLong();
//DP用のMap
TreeMap<Long,Long> map = new TreeMap<>();
map.put(1L,1L);
final int mod = 998244353;
//事前に5^-1 mod 998244353を求めておく
final long div = MathFunction.modPow(5,mod-2,mod);
//遷移
while(map.size()>0&&map.firstKey()<N){
Map.Entry<Long,Long> entry = map.pollFirstEntry();
long num = entry.getKey();
long p = entry.getValue();
for(int i=2;i<7;i++){
if(num*i>N)
break;
map.merge(num*i,p*div%mod,(s,t)->(s+t)%mod);
}
}
//Nに到達できたならその確率を出力
if(map.size()>0)
out.println(map.pollFirstEntry().getValue());
//Nに到達できなかったなら確率は0
else
out.println(0);
out.close();
}
}
最初$\frac{1}{6}$をかけていたので答えが合わなくて混乱してました…。
F - More Holidays
問題文はこちら
公式解説の通りです。
F.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、M、K、Sの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
long K = sc.nextLong();
String S = sc.next();
//xの数の累積和
int[] count = new int[N+1];
for(int i=0;i<N;i++)
count[i+1] = count[i]+(S.charAt(i)=='x'?1:0);
//答え用変数
long ans = 0;
//始点を決めて終点を求める
for(int i=1;i<=N;i++){
final int index = i;
long sum = Searcher.downSearch(i,(long)N*M,K,s->s/N*count[N]+count[(int)(s%N)]-count[index-1]);
ans = Math.max(ans,sum-i+1);
}
//最大値を出力
out.println(ans);
out.close();
}
}
全然気づけませんでした…。他の解説も読んで身につけたいです。
G - P-smooth number
問題文はこちら
公式解説の通りです。
高速化のためにArrayListではなく長めの配列を用いています。
G.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、Pの受け取り
long N = sc.nextLong();
int P = sc.nextInt();
//P以下の素数の列挙
int[] primes = MathFunction.primes(P);
//半分全列挙用の配列
long[] list1 = new long[10000000];
long[] list2 = new long[10000000];
int tail1 = 0; //末尾
int tail2 = 0; //末尾
list1[tail1++] = 1; //初期値代入
list2[tail2++] = 1; //初期値代入
//順に素数を見ていく
for(int p:primes){
//小さい方にかけていく
if(tail2<tail1){
int len = tail2;
for(int i=0;i<len;i++){
long num = list2[i]*p;
while(num<=N){
list2[tail2++] = num;
num *= p;
}
}
}
else{
int len = tail1;
for(int i=0;i<len;i++){
long num = list1[i]*p;
while(num<=N){
list1[tail1++] = num;
num *= p;
}
}
}
}
//ソート
Arrays.sort(list1,0,tail1);
Arrays.sort(list2,0,tail2);
//数え上げ
long ans = 0;
int index = tail2;
for(int i=0;i<tail1;i++){
while(0<index&&list1[i]>N/list2[index-1])
index--;
ans += index;
}
//答えのしゅつりょく
out.println(ans);
out.close();
}
}
半分全列挙自体は知っていましたが、コンテスト中に使えたことが無い…まだまだ身についてない証拠ですね…。
感想
A,B,C:易しい
D:答えがそんなに大きくないことに気付けば難しくない
E:1が出たときは考えなくて良いと発想できれば簡単めかも？
F:いろいろ考えたけど思いつけなかった…
G:何も思いつかなかった…
って感じでした。
今回は何事も無く終わって良かったです。これまでの平和のありがたみを感じました。