はじめに
今回はコンテストに参加できなかったので後日行なったバチャで解いたEまでを載せようと思います。
では、見ていきましょう。
なお、ライブラリは提出結果よりご確認ください。
A - Weekly Records
問題文はこちら
二重for文で答えを求めて出力しました。
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();
//答えを格納する配列
int[] ans = new int[N];
//数え上げ
for(int i=0;i<N;i++)
for(int j=0;j<7;j++)
ans[i] += sc.nextInt();
//答えの数え上げ
out.println(ans);
out.close();
}
}
まぁ難しくはないですね。
B - racecar
問題文はこちら
$N$も$S_i$も十分に小さいので全探索で解きました。
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、Sの受け取り
int N = sc.nextInt();
String[] S = sc.next(N);
//条件を満たす組み合わせが存在するか
boolean contains = false;
//全探索
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(i==j)
continue;
contains |= check(S[i]+S[j]);
}
}
//組み合わせあった？
out.println(contains?"Yes":"No");
out.close();
}
//回分か判定するメソッド(雑にS.length()まで見てる)
private static boolean check(String S){
for(int i=0;i<S.length();i++)
if(S.charAt(i)!=S.charAt(S.length()-i-1))
return false;
return true;
}
}
これもそこまで難しくはないですね。
C - Ideal Sheet
問題文はこちら
先に$A$、$B$の端にある透明なマスしかない行、列を調べておいて、黒いマスが範囲外から出ないように全探索しました。
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 ) {
//HA、WA、A、...の受け取り
int HA = sc.nextInt();
int WA = sc.nextInt();
char[][] A = sc.nextCharArray(HA);
int HB = sc.nextInt();
int WB = sc.nextInt();
char[][] B = sc.nextCharArray(HB);
int HX = sc.nextInt();
int WX = sc.nextInt();
char[][] X = sc.nextCharArray(HX);
//黒いマスの境界を求める({上,下,左,右}の順に入ってる
int[] minA = check(A);
int[] minB = check(B);
//仮想上のC(見る必要があるのはHX*WXだけ)
char[][] C = new char[HX][WX];
//Xを構築できるか
boolean canMake = false;
//黒の範囲が収まるようにずらして全探索
for(int i=0;i<HX-(minA[1]-minA[0]);i++){
for(int j=0;j<WX-(minA[3]-minA[2]);j++){
for(int k=0;k<HX-(minB[1]-minB[0]);k++){
for(int l=0;l<WX-(minB[3]-minB[2]);l++){
//Cを初期化
for(int ii=0;ii<HX;ii++)
for(int jj=0;jj<WX;jj++)
C[ii][jj] = '.';
//A側は特に何も考えず転写
for(int ii=minA[0];ii<=minA[1];ii++)
for(int jj=minA[2];jj<=minA[3];jj++)
C[ii-minA[0]+i][jj-minA[2]+j] = A[ii][jj];
//B側はA側の黒を潰さないように転写
for(int ii=minB[0];ii<=minB[1];ii++)
for(int jj=minB[2];jj<=minB[3];jj++)
if(C[ii-minB[0]+k][jj-minB[2]+l]=='.')
C[ii-minB[0]+k][jj-minB[2]+l] = B[ii][jj];
//Xと一致してるか見てcanMakeと論理和を取る
boolean equals = true;
for(int ii=0;ii<HX;ii++)
for(int jj=0;jj<WX;jj++)
equals &= C[ii][jj]==X[ii][jj];
canMake |= equals;
}
}
}
}
//構築できた？
out.println(canMake?"Yes":"No");
out.close();
}
//黒いマスの端っこを求めるメソッド
private static int[] check(char[][] A){
int[] minA = new int[4];
Check:for(int i=0;i<A.length;i++)
for(int j=0;j<A[i].length;j++)
if(A[i][j]=='#'){
minA[0] = i;
break Check;
}
Check:for(int i=A.length-1;i>=0;i--)
for(int j=0;j<A[i].length;j++)
if(A[i][j]=='#'){
minA[1] = i;
break Check;
}
Check:for(int i=0;i<A[0].length;i++)
for(int j=0;j<A.length;j++)
if(A[j][i]=='#'){
minA[2] = i;
break Check;
}
Check:for(int i=A[0].length-1;i>=0;i--)
for(int j=0;j<A.length;j++)
if(A[j][i]=='#'){
minA[3] = i;
break Check;
}
return minA;
}
}
ちょっと重いですけど、やってること自体は難しくないのが救いでした。
D - Mismatched Parentheses
問題文はこちら
(がある箇所をArrayDequeに記録していき、)に対応する(があればその区間にBITで1を加算していき、最終的に0である箇所だけを抜き出して文字列を構築すればそれが解となります。
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、Sの受け取り
int N = sc.nextInt();
String S = sc.next();
//(の場所を格納するDeque
ArrayDeque<Integer> deq = new ArrayDeque<>();
//区間に雑に足すためのBIT
BIT bit = new BIT(S.length()+1);
//先頭からよしなに
for(int i=0;i<S.length();i++){
if(S.charAt(i)=='(')
deq.add(i);
else if(S.charAt(i)==')'){
if(deq.size()>0){
bit.add(deq.pollLast()+1,1);
bit.add(i+2,-1);
}
}
}
//累積和が0の箇所だけ抜き出して出力
StringBuilder sb = new StringBuilder();
for(int i=0;i<S.length();i++)
if(bit.sum(i+1)==0)
sb.append(S.charAt(i));
out.println(sb.toString());
out.close();
}
}
これはすぐ思いつけました。
E - Distinct Adjacent
問題文はこちら
動的計画法で解きました。
$\mathrm{dp}[i]:$を$N=i$の時の解として保持し、以下のように遷移しました。
$$\mathrm{dp}[i] = M \times (M-1)^{i-1} - dp[i-1] \mod 998244353$$
遷移の説明
1人目から順に番号を決めていきましょう。最初の人は何でも良いので$M$通りです。
では2人目はどうでしょうか。これは1人目と異なる必要があるので$M-1$通りです。
これを順に繰り返していくと$N-1$人目までは$M-1$通りになるかと思います。
そして$N$人目ですが、1人目と$N-1$人目を考慮しないといけなそうです。ですがここでは便宜上$N-1$人目のみを考えて$M-1$通りとします。
さて、この数え方では「全員が隣の人と異なる組み合わせ」と「1人目と$N$人目のみ同じとなる組み合わせ」の二種類の和となってしまいます。「1人目と$N$人目のみ同じとなる組み合わせ」を除くにはどうすれば良いでしょうか。
ここで、$N$が1だけ小さい場合を考えてみます。もし$N$が1だけ小さい場合の組み合わせの個数がわかっているなら、「1人目と$N$人目のみ同じとなる組み合わせ」は求まっているも同然です。なぜなら、「$N-1$人全員が隣の人と異なる組み合わせ」という状態を考えてみると、仮想的に、1人目と同じ番号を持つ$N$人目を輪に加えても通り数は変わらず、この状態は「1人目と$N$人目のみ同じ」と同義だからです。
よって、$\mathrm{dp[i-1]}$まで求めてあれば、$M \times (M-1)^{i-1}$から$\mathrm{dp[i-1]}$を引いてあげることで$\mathrm{dp[i]}$が求まります。
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の受け取り
int N = sc.nextInt();
long M = sc.nextInt();
//mod
final int mod = 998244353;
//dpテーブル
long[] dp = new long[N+1];
//初期値(2がズレちゃうので)
dp[1] = M;
dp[2] = M*(M-1)%mod;
//遷移
for(int i=3;i<=N;i++)
dp[i] = (M*MathFunction.modPow(M-1,i-1,mod)%mod-dp[i-1])%mod;
//答えの出力
out.println((dp[N]+mod)%mod);
out.close();
}
}
バチャ終了ギリギリで思いつけたので達成感がありました。
感想
A,B:易しい
C:重い
D:慣れていればすぐ思いつくと思う
E:遷移が見えるまでかなり時間かかった…
って感じでした。
いやぁ、多分参加してたらCで焦ってたかもしれません。こういう問題超苦手…。