はじめに
今回はEまでコンテスト中に解けたのでそれを載せようと思います。
では、見ていきましょう。
なお、用いられている自作ライブラリは提出結果からご確認ください。
A - Job Interview
問題文はこちら
oが含まれていたか、xが含まれていなかったかがわかれば良いので、forで全部見ていきました。
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();
//oとxの存在確認用
boolean isGood = false;
boolean isBad = false;
for(char c:sc.nextCharArray()){
isGood |= c=='o';
isBad |= c=='x';
}
//条件満たしてる？
out.println(isGood&&!isBad?"Yes":"No");
out.close();
}
}
String型で受け取ってcontainsメソッドを用いる方が簡潔に書けましたね。
B - Coloring Matrix
問題文はこちら
問題文そのままを二重for分で実装しました。
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の受け取り
int N = sc.nextInt();
//A、Bの受け取り
int[][] A = sc.nextInt(N,N);
int[][] B = sc.nextInt(N,N);
//各状態で条件を満たしているか管理する用の変数
boolean isTrue1 = true;
boolean isTrue2 = true;
boolean isTrue3 = true;
boolean isTrue4 = true;
//全部確認していく
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
isTrue1 &= A[i][j]==1?B[i][j]==1:true;
isTrue2 &= A[N-j-1][i]==1?B[i][j]==1:true;
isTrue3 &= A[N-i-1][N-j-1]==1?B[i][j]==1:true;
isTrue4 &= A[j][N-i-1]==1?B[i][j]==1:true;
}
}
//どれか一個は条件を満たしたか？
out.println(isTrue1||isTrue2||isTrue3||isTrue4?"Yes":"No");
out.close();
}
}
forの中はコピペして書いたんですが、書き換え忘れてペナルティを頂いてしまいました…。
確認、大事。
C - Cards Query Problem
問題文はこちら
TreeMap<Integer,Integer>を用いて各値が何個ずつ入っているかを管理しました。
各値が入っている箱も、HashMap<Integer,TreeSet<Integer>>で管理しました。
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 ) {
//N、Qの受け取り
int N = sc.nextInt();
int Q = sc.nextInt();
//箱の中身用
ArrayList<TreeMap<Integer,Integer>> box = new ArrayList<>();
//各値が入っている箱の番号用
HashMap<Integer,TreeSet<Integer>> map = new HashMap<>();
//箱の準備
for(int i=0;i<=N;i++)
box.add(new TreeMap<>());
//各クエリに答える
while(Q-->0){
int q = sc.nextInt();
//クエリ1
if(q==1){
//i、jの受け取り
int i = sc.nextInt();
int j = sc.nextInt();
//箱に追加
box.get(j).merge(i,1,(s,t)->s+t);
//iが出現するのが初めてなら追加しておく
if(!map.containsKey(i)){
map.put(i,new TreeSet<>());
}
//箱の情報を追記
map.get(i).add(j);
}
//クエリ2
else if(q==2){
//iの受け取り
int i = sc.nextInt();
//各値を昇順に取り出し
for(Map.Entry<Integer,Integer> e:box.get(i).entrySet()){
//含まれている数だけ出力
int num = e.getValue();
while(num-->0)
out.print(e.getKey()+" ");
}
out.println();
}
//クエリ3
else{
//iの受け取り
int i = sc.nextInt();
//箱の番号を昇順に出力
for(Integer num:map.get(i))
out.print(num+" ");
out.println();
}
}
out.close();
}
}
ちょっと重めの実装になってしまった…。
TreeMap、TreeSetで管理しなくても、その都度ソートすれば良いということにコンテスト後に気付きました。
D - Writing a Numeral
問題文はこちら
加えられる、削除されるをArrayDeque<Integer>で管理し、ローリングハッシュみたいにクエリ3で出力すべき値を更新していくことで解きました。
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 ) {
//Qの受け取り
int Q = sc.nextInt();
//初期値1
long now = 1;
//あまり取る用
final int mod = 998244353;
//追加、削除される値を管理する用
ArrayDeque<Integer> deq = new ArrayDeque<>();
deq.add(1);
//各クエリに答える
while(Q-->0){
int q = sc.nextInt();
//クエリ1
if(q==1){
//xの受け取り
int x = sc.nextInt();
//追加
deq.add(x);
//元の値を10倍してxを足した値と同じなのでそれを求めておく
now = (now*10+x)%mod;
}
//クエリ2
else if(q==2){
//先頭の値の取り出し
int x = deq.pollFirst();
//x*1000...%modで引く
now -= x*MathFunction.modPow(10,deq.size(),mod)%mod;
//負の値になっている可能性があるのでその時はmodを加算
if(now<0)
now += mod;
}
//クエリ3
else
out.println(now);
}
out.close();
}
}
これは比較的早く思いつきました。
E - Unfair Sugoroku
問題文はこちら
動的計画法で解きました。
$\mathrm{dp}[i][j]$を$i$回サイコロを振ったときに$j$にいる確率とし、以下のように遷移しました。
$\mathrm{dp1}[i+1][j] = \sum_{k=j-P}^{j-1}{\mathrm{dp1}[i][k]} \times P^{-1}$
$\mathrm{dp2}[i+1][j] = \sum_{k=j-Q}^{j-1}{\mathrm{dp2}[i][k]} \times Q^{-1}$
求める答えは$\sum_{i=1}^N{dp1[i][N]} \times \sum_{j=i}^N{dp2[j][N]}$です。
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、A、B、P、Qの受け取り
int N = sc.nextInt();
int A = sc.nextInt();
int B = sc.nextInt();
int P = sc.nextInt();
int Q = sc.nextInt();
final int mod = 998244353;
//dp(1が高橋君、2が青木君)
long[][] dp1 = new long[N+1][N+1];
long[][] dp2 = new long[N+1][N+1];
//今いる場所を初期設定(絶対いるので確率は1)
dp1[0][A] = 1;
dp2[0][B] = 1;
//N回投げる(N回投げれば絶対マスNにはたどり着けるのでこれで良い)
for(int i=0;i<N;i++){
//遷移
for(int j=1;j<N;j++){
for(int k=1;k<=P;k++){
if(j+k<=N){
dp1[i+1][j+k] += dp1[i][j]*MathFunction.modPow(P,mod-2,mod);
dp1[i+1][j+k] %=mod;
}
else{
dp1[i+1][N] += dp1[i][j]*MathFunction.modPow(P,mod-2,mod);
dp1[i+1][N] %=mod;
}
}
for(int k=1;k<=Q;k++){
if(j+k<=N){
dp2[i+1][j+k] += dp2[i][j]*MathFunction.modPow(Q,mod-2,mod);
dp2[i+1][j+k] %=mod;
}
else{
dp2[i+1][N] += dp2[i][j]*MathFunction.modPow(Q,mod-2,mod);
dp2[i+1][N] %=mod;
}
}
}
}
//求めるべき確率を求める
long sum = 0;
for(int i=0;i<=N;i++){
for(int j=i;j<=N;j++){
sum += (long)dp1[i][N]*dp2[j][N]%mod;
sum %= mod;
}
}
//答えの出力
out.println(sum);
out.close();
}
}
思っていたより早く思いつけました。
感想
A:易しい
B:ちょっと面倒。問題文通りに変換するメソッドを作れば良かったか…？
C:ちょっとだけ重い
D:気付けば早く解ける
E:公式解説のDPのやり方全然思いつかなかった
という感じでした。
Unratedになってしまいましたが、面白い問題だったなと思いました。