はじめに
今回はコンテスト中にEまで解けたのでそれを載せようと思います。
では、見ていきましょう。
なお、僕のライブラリは提出結果よりご確認ください。
A - Order Something Else
問題文はこちら
$\mathrm{min}(P,Q+D_i)$を求めて出力してあげれば良いです。
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、P、Q、Dの受け取り
int N = sc.nextInt();
int P = sc.nextInt();
int Q = sc.nextInt();
int[] D = sc.nextInt(N);
//最小値を求める
for(int num:D)
P = Math.min(P,Q+num);
//最小値の出力
out.println(P);
out.close();
}
}
これは特に問題ないですね。
B - Strictly Superior
問題文はこちら
全通りを調べて条件を満たすものが存在するかを判定しました。$i$、$j$が同じ場合も探索していますが、同じものは条件を満たさないため判定に影響はありません。
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、Mの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
//各商品の値段と機能を有しているかを記録(ずっと機械だと思ってたのでmachineになってる)
int[] P = new int[N];
boolean[][] machine = new boolean[N][M];
for(int i=0;i<N;i++){
P[i] = sc.nextInt();
int C = sc.nextInt();
while(C-->0){
int F = sc.nextInt()-1;
machine[i][F] = true;
}
}
//条件を満たすものがあるかを保持する変数
boolean contain = false;
//i、jの全探索
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
//条件1を満たしているか？
if(P[i]>=P[j]){
//条件2と条件3の後ろの方を満たしているかを保持する変数
boolean flag1 = true;
boolean flag2 = false;
for(int k=0;k<M;k++){
flag1 &= machine[i][k]?machine[j][k]:true; //iの機能を被覆できているか？
flag2 |= machine[i][k]?false:machine[j][k]; //+αの機能を有しているか？
}
//条件2と条件3を満たしているかをcontainに反映(このifの中に入っているかで条件1は判定済み)
contain |= flag1 && (flag2||P[i]>P[j]);
}
}
}
//条件を満たしたやつがあった？
out.println(contain?"Yes":"No");
out.close();
}
}
ちょっと重いような気もしますが、まぁ許容範囲でしょう()。
C - Reversible
問題文はこちら
$S_i$を、そのままと逆順のうち辞書順で小さい方で置き換えることで文字列の種類を考えるだけの問題に落とし込んで解きました。
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、Sの受け取り
int N = sc.nextInt();
String[] S = sc.next(N);
//辞書順で小さい方になるように置換
for(int i=0;i<N;i++){
String s1 = S[i];
String s2 = new StringBuilder(S[i]).reverse().toString();
if(s1.compareTo(s2)<0)
S[i] = s1;
else
S[i] = s2;
}
//文字列をsetに入れて種類数を数える
HashSet<String> set = new HashSet<>();
for(String s:S)
set.add(s);
out.println(set.size());
out.close();
}
}
最初悩みましたが気付けばサクッと実装出来ました。
D - Peaceful Teams
問題文はこちら
DFSで解きました。
今存在するチームへ加えるの時と新しいチームを作成してそこに所属させる時を再帰関数で探索することで全探索できます。
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、T、Mの受け取り
int N = sc.nextInt();
int T = sc.nextInt();
int M = sc.nextInt();
//悪い組み合わせかを記録
boolean[][] isBad = new boolean[N][N];
while(M-->0){
int A = sc.nextInt()-1;
int B = sc.nextInt()-1;
isBad[A][B] = true;
isBad[B][A] = true;
}
//DFS
out.println(dfs(N-1,T,isBad,new ArrayList<>()));
out.close();
}
//DFS用メソッド(引数はそれぞれ今見てる人、作りたいチーム数、悪い組み合わせかを記録している配列、現在構築しているチーム)
private static long dfs(int now,int T,boolean[][] isBad,ArrayList<HashSet<Integer>> list){
//全員格納し終わったならチーム数がTかどうかで1か0を返す
if(now<0)
return list.size()==T?1:0;
//数え上げ用変数
long ans = 0;
//現状あるチームに加える組み合わせを探索
for(int i=0;i<list.size();i++){
//このチームに悪い組み合わせが無いなら探索
if(check(list.get(i),now,isBad)){
list.get(i).add(now);
ans += dfs(now-1,T,isBad,list);
list.get(i).remove(now);
}
}
//チーム数がT未満なら、新しいチームを作ってそこに所属させる組み合わせも探索
if(list.size()<T){
list.add(new HashSet<>());
list.get(list.size()-1).add(now);
ans += dfs(now-1,T,isBad,list);
list.remove(list.size()-1);
}
//数え上げた通り数を返す
return ans;
}
//悪い組み合わせがないかを確認するメソッド(悪い組み合わせが無いならtrue、あればfalse)
private static boolean check(HashSet<Integer> set,int now,boolean[][] isBad){
//チームの人と今加えようとしている人の組み合わせを見る
for(int num:set){
if(isBad[num][now])
return false;
}
//ループを抜けた=悪い組み合わせが無い
return true;
}
}
最初全然思いついてなかったんですけど、ChatGPTに聞いてみたらこれに近いコードを実装してきたので方針を参考に書いてみました。
E - NAND repeatedly
問題文はこちら
動的計画法で解きました。
$\mathrm{dp}[i][j]$を$i$番目までで$j$になる通り数として、以下のように遷移しました。
$$\mathrm{dp}[i][0]=1,\ \mathrm{dp}[i][1]=\mathrm{dp}[i-1][0]+\mathrm{dp}[i-1][1] (S[i]=0)$$
$$dp[i][0] = dp[i-1][1],\ dp[i][1] = dp[i-1][0]+1 (S[i]=1)$$
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、Sの受け取り
int N = sc.nextInt();
String S = sc.next();
//DPテーブルの宣言
long[][] dp = new long[N][2];
dp[0][S.charAt(0)-'0']++;//初期値
//遷移
for(int i=1;i<N;i++){
if(S.charAt(i)=='0'){
dp[i][1] = dp[i-1][0]+dp[i-1][1]; //0でも1でも0との否定論理積は1なのでこっちに
dp[i][0] = 1; //今見ているものを始点とした組み合わせを数えるため、こっちは1
}
else{
dp[i][0] = dp[i-1][1]; //1と1の否定論理積は0なので、1の組み合わせをこっちに
dp[i][1] = dp[i-1][0]+1; //0と1の否定論理積は1なので、0の組み合わせはこっちに
//なお、//今見ているものを始点とした組み合わせを数えるため1の組み合わせに1足す
}
}
//終点を全探索して数え上げ
long ans = 0;
for(int i=0;i<N;i++)
ans += dp[i][1];
//答えのしゅつりょく
out.println(ans);
out.close();
}
}
Dすっ飛ばして考えたのでDより簡単に感じました。
感想
A,B,C:易しい
D:精進不足を痛感しました…
E:DPって見えてからはそこまで難しくはない
って感じでした。
う～ん…結果としてはレート上がったんですけど、Dでかなり時間使ったりFが何もできなかったり、モヤッとする結果な気がします…。夏休み早く来てくれ、精進したい…。
追記(F - Make 10 Again)
問題文はこちら
公式解説の通りです。
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、Aの受け取り
int N = sc.nextInt();
int[] A = sc.nextInt(N);
final int mod = 998244353;
//DPテーブル
int[][] dp = new int[N+1][1<<11];
dp[0][1] = 1;
//範囲外の探索を避けるためのビットマスク
int mask = 1<<11;
mask--;
//遷移
for(int i=1;i<=N;i++){
//事前にモジュラ逆数を取っておく
long div = MathFunction.modPow(A[i-1],mod-2,mod);
long over = Math.max(0,A[i-1]-10)*div%mod; //11以上の手が出る確率
//各状態から遷移
for(int j=1;j<1<<11;j++){
//1～10の目が出たときの確率を加える
for(int k=1;k<=Math.min(A[i-1],10);k++){
int next = (j|(j<<k))&mask;
dp[i][next] += (int)(dp[i-1][j]*div%mod);
if(dp[i][next]>=mod)
dp[i][next] -= mod;
}
//11以上の目が出たときの確率を加える
dp[i][j] += (int)(dp[i-1][j]*over%mod);
if(dp[i][j]>=mod)
dp[i][j] -= mod;
}
}
//10が作れている確率の和を求める
int ans = 0;
for(int i=1<<10;i<1<<11;i++){
ans += dp[N][i];
if(ans>=mod)
ans -= mod;
}
out.println(ans);
out.close();
}
}
いやぁ…コンテスト中に気付きたかった…。