AtCoder Beginner Contest 332

AtCoder Beginner Contest 332 - AtCoder

結果

A - Online Shopping : AC(2:18)
B - Glass and Mug : AC(9:48)
C - T-shirts : AC(30:03)(1ペナ)
D - Swapping Puzzle : WA

A - Online Shopping

オンラインショップで$${N}$$種類の商品を買うことにし、それぞれ$${P_{i}}$$円の商品を$${Q_{i}}$$個購入する
購入する商品の合計金額が$${S}$$円以上であるとき送料は$${0}$$円、そうでないときは$${K}$$円である
最終的に支払う金額を求める問題

自分の回答

int main(){
  int N, S, K;
  cin >> N >> S >> K;
  int sum = 0;
  for(int i = 0; i < N; i++){
    int p, q;
    cin >> p >> q;
    sum += p * q;
  }
  if(sum < S){
    sum += K;
  }

  printf("%d\n", sum);
}

そのまま

公式解説

省略

B - Glass and Mug

容量が$${G}$$mlのグラスと$${M}$$mlのマグカップを$${1}$$つずつ持っている
最初、両方とも空の状態から以下の操作を$${K}$$回操作した後それぞれ水が何ml入っているか求める問題
・グラスが水で満たされている時グラスを空にする
・そうでなく、マグカップが空であるときマグカップを水で満たす
・上のいずれでもないとき、マグカップが空になるかグラスが満たされるまでマグカップの水をグラスに移す

自分の回答

int main(){
  int K, G, M;
  cin >> K >> G >> M;

  int g = 0, m = 0;
  for(int i = 0; i < K; i++){
    if(g == G){
      g = 0;
    }
    else if(m == 0){
      m = M;
    }
    else{
      int e = min(m, G - g);
      g += e;
      m -= e;
    }
  }

  printf("%d %d\n", g, m);
}

そのまま

公式解説

省略

C - T-shirts

高橋君の$${N}$$日間の予定が「0」「1」「2」からなる長さ$${N}$$の文字列$${S}$$で与えられる
・「0」であるときその日は何も予定は入っていない
・「1」であるとき食事に行く予定が入っている
・「2」であるとき競技プログラミングのイベントに行く予定が入っている
イベントに行くときはロゴ入りのTシャツを着ていく必要があり、食事に行くときはロゴ入りのTシャツか無地のTシャツを着ていく
一度着たTシャツは洗濯するまで着ることができず、予定が入っていない日に着用済みのTシャツを全て洗濯する
始め無地のTシャツを$${M}$$枚持っているとき、ロゴ入りのTシャツを最低何枚買う必要があるか求める問題

自分の回答

int main(){
  int N, M;
  string S;
  cin >> N >> M >> S;

  int at = 0, sa = 0, m = M;
  for(int i = 0; i < N; i++){
    if(S[i] == '0'){
      m = M;
      sa = at;
    }
    else if(S[i] == '1'){
      if(m > 0){
        m--;
      }
      else{
        if(sa > 0){
          sa--;
        }
        else{
          at++;
        }
      }
    }
    else{
      if(sa > 0){
        sa--;
      }
      else{
        at++;
      }
    }
  }

  printf("%d\n", at);
}

1日目からやってみて必要になったら買っていく

最初0区切りで1と2が何個あるかでやってみたけど見逃しあってWA
こっちの方が楽だった

公式解説

省略

D - Swapping Puzzle

$${H}$$行$${W}$$列のグリッド$${A,B}$$があり、各マスには整数が書かれている
グリッド$${A}$$の任意の隣接する行もしくは列を入れ替える操作を最低何回すれば$${B}$$と一致させられるか、もしくは一致させることができないか求める問題

自分の回答

入れ替えが各行、列でだけだから行列の操作を別々で考えることができる
HW共に最大5なため並び順のパターンは5!で120通りなため総当たりは余裕
幅優先探索の要領で各並び順に操作何回で行けるかを求めて行列で総当たりしてBと一致する並び順があったらその並び順に到達する回数の和

入れ替えが隣接するものなのを見逃して任意の入れ替えで書いてて気づいたのが終了5分前だった
間に合わんかった

公式解説

int main(void)
{
  int h, w, a[6][6], b[6][6];
  cin >> h >> w;
  for(int i = 1; i <= h; i++) for(int j = 1; j <= w; j++) cin >> a[i][j];
  for(int i = 1; i <= h; i++) for(int j = 1; j <= w; j++) cin >> b[i][j];
  
  int p[6], q[6];
  for(int i = 1; i <= h; i++) p[i] = i;
  for(int i = 1; i <= w; i++) q[i] = i;
  
  int ans = inf;
  do{
    do{
      
      bool match = true;
      for(int i = 1; i <= h; i++) for(int j = 1; j <= w; j++){
        if(a[p[i]][q[j]] != b[i][j]) match = false;
      }
      if(!match) continue;
      
      int pinv = 0, qinv = 0;
      for(int i = 1; i <= h; i++) for(int j = 1; j <= h; j++) if(i < j && p[i] > p[j]) pinv++;
      for(int i = 1; i <= w; i++) for(int j = 1; j <= w; j++) if(i < j && q[i] > q[j]) qinv++;
      ans = min(ans, pinv+qinv);
      
    }while(next_permutation(q+1, q+w+1));
  }while(next_permutation(p+1, p+h+1));
  
  if(ans == inf) cout << -1 << endl;
  else cout << ans << endl;
  
  return 0;
}

https://atcoder.jp/contests/abc332/editorial/7893より

そうか転倒数か
それなら幅優先探索しなくてもnext_parmutationでやればいいのか

なるほど