はじめに
今回はコンテスト中にDまで、コンテスト後にFまで解いたのでそれを載せようと思います。
なお、僕のライブラリは提出結果よりご確認ください。
では、見ていきましょう。
A - Online Shopping
問題文はこちら
総額を求めて$S$円未満かを判定して処理しました。
A.java
final class Main{
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner(System.in);
private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);
public static void main(String[] args){
//N、P、Kの受け取り
int N = sc.nextInt();
int P = sc.nextInt();
int K = sc.nextInt();
//総額を求める
long sum = 0;
for(int i=0;i<N;i++)
sum += sc.nextInt()*sc.nextInt();
//送料がかかるなら加算
if(sum<P)
sum += K;
//出力
out.println(sum);
out.close();
}
}
B - Glass and Mug
問題文はこちら
問題文をそのままコードに落とし込んでシミュレーションしました。
B.java
final class Main{
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner(System.in);
private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);
public static void main(String[] args){
//K、G、Mの受け取り
int K = sc.nextInt();
int G = sc.nextInt();
int M = sc.nextInt();
//シミュレーション
int gla = 0;
int mug = 0;
while(K-->0){
if(gla==G)
gla = 0;
else if(mug==0)
mug = M;
else{
int sub = Math.min(G-gla,mug);
mug -= sub;
gla += sub;
}
}
//答えの出力
out.println(gla+" "+mug);
out.close();
}
}
C - T-shirts
問題文はこちら
Bと同様にシミュレーションで解きました。
なるべく無地のTシャツをきた方が有利なのでそのように処理してます。
C.java
final class Main{
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner(System.in);
private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);
public static void main(String[] args){
//N、Mの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
//ロゴ入りTシャツ(着れる物)
int L = 0;
//洗濯待ち
int subM = 0;
int subL = 0;
//順に処理
String S = sc.next();
for(char c:S.toCharArray()){
//洗濯する
if(c=='0'){
M += subM;
L += subL;
subM = 0;
subL = 0;
}
//なるべく無地を使う
else if(c=='1'){
if(M>0){
M--;
subM++;
}
else{
L = Math.max(L-1,0); //無ければ1着購入
subL++;
}
}
//ロゴ入りを着る
else{
L = Math.max(L-1,0); //無ければ1着購入
subL++;
}
}
//最終的に所有している(=購入した)ロゴ入りTシャツの枚数を答える
out.println(L+subL);
out.close();
}
}
D - Swapping Puzzle
問題文はこちら
$H$、$W$が小さいので順列全探索で解きました。
操作回数はバブルソートで求めています。
D.java
final class Main{
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner(System.in);
private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);
public static void main(String[] args){
//H、W、A、Bの受け取り
int H = sc.nextInt();
int W = sc.nextInt();
int[][] A = sc.nextInt(H,W);
int[][] B = sc.nextInt(H,W);
//順列全探索
int[] r = new int[H];
int[] c = new int[W];
Arrays.setAll(r,i->i);
int ans = Integer.MAX_VALUE;
do{
Arrays.setAll(c,i->i);
Loop:do{
//一致してないなら次の候補へ
for(int i=0;i<H;i++)
for(int j=0;j<W;j++)
if(A[r[i]][c[j]]!=B[i][j])
continue Loop;
//全一致したなら最小値更新
ans = Math.min(ans,count(r,c));
}while(ArrayFunction.nextPermutation(c));
}while(ArrayFunction.nextPermutation(r));
//ちゃんと一致させることができたかで場合分け
out.println(ans==Integer.MAX_VALUE?-1:ans);
out.close();
}
//操作回数を数えるメソッド
private static int count(int[] r,int[] c){
//配列をコピーして、その配列をバブルソートする工程で操作回数を数える
int count = 0;
int[] subR = Arrays.copyOf(r,r.length);
for(int i=0;i<r.length;i++){
for(int j=1;j<r.length-i;j++){
if(subR[j-1]>subR[j]){
ArrayFunction.swap(subR,j-1,j);
count++;
}
}
}
int[] subC = Arrays.copyOf(c,c.length);
for(int i=0;i<c.length;i++){
for(int j=1;j<c.length-i;j++){
if(subC[j-1]>subC[j]){
ArrayFunction.swap(subC,j-1,j);
count++;
}
}
}
return count;
}
}
BFSする、という手法もありましたね(Twitterで見かけて確かに、になりました)。
E - Lucky bag
問題文はこちら
公式解説の通りです。
$$\sum_{i}{(x_i-\bar{x})^2}$$
$$=\sum_{i}{x_i^2}-\frac{(\sum_{j}{w_j})^2}{D}$$
より、$\sum_{i}{x_i^2}$の最小値を求めています(これのおかげでDPテーブルはlongで扱えます)。
E.java
final class Main{
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner(System.in);
private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);
public static void main(String[] args){
//N、D、Wの受け取り
int N = sc.nextInt();
int D = sc.nextInt();
long[] W = sc.nextLong(N);
//DPテーブルの構築
long[][] dp = new long[D+1][1<<N];
for(int i=1;i<1<<N;i++){
for(int j=0;j<N;j++)
if((i&1<<j)>0)
dp[1][i] += W[j];
dp[1][i] *= dp[1][i];
}
//遷移
for(int i=2;i<=D;i++){
for(int j=1;j<1<<N;j++){
int S = (j-1)&j;
dp[i][j] = dp[i-1][j];
while(S>0){
long num = dp[i-1][j^S]+dp[1][S];
if(num<dp[i][j])
dp[i][j] = num;
S = (S-1)&j;
}
}
}
//答えの出力
long sum = MathFunction.sum(W);
out.println((dp[D][(1<<N)-1]*D-sum*sum)/(double)D/D);
out.close();
}
}
思いつけたら良かったけど…う～ん…。
F - Random Update Query
問題文はこちら
遅延セグ木で解きました。
処理は一次関数$f(x)=ax+b$の形で表せるので、compositionなどもそのような処理になっています。
F.java
final class Main{
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner(System.in);
private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);
//mod
private static final int MOD = 998244353;
//一次関数を表すクラス
private static class F{
final long a,b;
F(long a,long b){
this.a = a;
this.b = b;
}
}
public static void main(String[] args){
//N、M、Aの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
Long[] A = new Long[N]; //セグ木に載せるためにLongで
for(int i=0;i<N;i++){
long num = sc.nextLong();
if(MOD<=num)
num -= MOD;
A[i] = num;
}
//遅延セグ木の宣言
LazySegmentTree<Long,F> lSegT = new LazySegmentTree<>(A,0L,new F(1,0),false){
public Long function(Long a,Long b){
return a; //何だって良いのでテキトーに
}
//一次関数を適用するメソッド
public Long mapping(Long a,F f){
long ans = a*f.a%MOD+f.b;
if(MOD<=ans)
ans -= MOD;
return ans;
}
//一次関数を合成するメソッド
public F composition(F a,F b){
long c = a.a*b.a%MOD;
long d = b.a*a.b%MOD+b.b;
if(MOD<=d)
d -= MOD;
return new F(c,d);
}
};
//前計算用
Factorial fact = new Factorial(200_000,MOD);
//クエリの処理
while(M-->0){
//L、R、Xの受け取り
int L = sc.nextInt();
int R = sc.nextInt();
int X = sc.nextInt();
if(MOD<=X)
X -= MOD;
//一次関数の形に直してapply
long a = (R-L)*fact.getInverse(R-L+1)%MOD;
long b = X*fact.getInverse(R-L+1)%MOD;
lSegT.apply(L-1,R,new F(a,b));
}
//答えの取得と出力
long[] ans = new long[N];
for(int i=0;i<N;i++)
ans[i] = lSegT.get(i);
out.println(ans);
out.close();
}
}
ずっと答え合わなくてどこミスったんだろう…とコンテスト後も考えていたんですが、まさかのライブラリがバグっておりました…。
こ、殺してくれ…。
感想
A,B,C,D:易しめ
E:何も見えてこなかった…
F:遅延セグ木とわかったのに…わかったのに…
って感じでした。
前日のARCでもレート下がったので、非常に悲しい…。まぁ、ライブラリのバグが見つかったと思えば…。