ei1333の日記

ぺこい

Google Code Jam 2017 Round 1A

A-small/large, B-small/large, C-small を解いて 75pt, 362位.

あっさり通過できてしまってんー?ってなった.

Problem A. Alphabet Cake

問題概要

 {R \times C(1 \le R, C \le 25)} のグリッドがあって, それぞれのマスは, 未知のマス ‘?’ かあるアルファベットで表される. アルファベットは種類ごとに高々  {1} 回しか出現しない.

‘?’ に上手くアルファベットを割り当てることにより, アルファベットの種類ごとに長方形の区画に分けたい.

割り当て方の一例を出力せよ.

解法

アルファベットが一文字以上存在する行を取り出してみて, その行の ‘?’ について適当に割り当てる.

??A??BB

のような感じであれば

AAABBBB

が一例である.

この操作を行うと, 各行はすべて ‘?’ かアルファベットで埋まっているかのどちらかになる.

あとはすべて ‘?’ の行について, 埋まってる行を適当にクローン(?) させればよい.

ソース

難しすぎる.

#include <bits/stdc++.h>

using namespace std;

void solve()
{
  int H, W;
  string S[25];

  cin >> H >> W;
  for(int i = 0; i < H; i++) {
    cin >> S[i];
  }


  int appear[25] = {};
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      if(S[i][j] != '?') appear[i] = true;
    }
  }

  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      if(S[i][j] == '?') {
        if(appear[i]) {
          for(int k = j - 1; k >= 0; k--) {
            if(S[i][k] != '?') {
              S[i][j] = S[i][k];
              break;
            }
          }
          for(int k = j + 1; k < W; k++) {
            if(S[i][k] != '?') {
              S[i][j] = S[i][k];
              break;
            }
          }
        }
      }
    }
  }

  for(int i = 0; i < H; i++) {
    if(S[i][0] == '?') {
      if(i > 0 && S[i - 1][0] != '?') {
        for(int k = 0; k < W; k++) {
          S[i][k] = S[i - 1][k];
        }
      }
    }
  }


  for(int i = H - 1; i >= 0; i--) {
    if(S[i][0] == '?') {
      if(i != H - 1 && S[i + 1][0] != '?') {
        for(int k = 0; k < W; k++) {
          S[i][k] = S[i + 1][k];
        }
      }
    }
  }

  for(int i = 0; i < H; i++) {
    cout << S[i] << endl;
  }
}

int main()
{
  int T;
  cin >> T;
  for(int i = 1; i <= T; i++) {
    cout << "Case #" << i << ":" << endl;
    solve();
  }
}

Problem B. Ratatouille

問題概要

 {N(1 \le N \le 50)} 種類の具材がある.

各具材について  {P(1 \le P \le 50)} 種類のパッケージが {1} つずつあって, それぞれの量は  {Q_{i,j}(1 \le Q_{i, j} \le 10^6)} である.

 {N} 個のパッケージから  {1} つずつのパッケージをとってきて料理をつくる. 何人前の料理でもかまわないが, 種類ごとに  {1} 人前の具材の量は  {R_i(1 \le R_i \le 10^6)} の 90 % から 110% の範囲である必要がある.

これを  {1} セットとして数える.

最大で何セット作れるか求めよ.

解法

結論からいうと  {x} 人前の料理を作れるかどうかを,  {x} が小さい順に貪欲に作っていけば良い(なんでだろうね).

小さい方からとっていけば, こういうのはだいたい成り立つ(成り立たなかったら諦める).

 {x} 人前の料理を作れるかという処理は, それぞれの  {R_i} から適正な具材の量(±10%) を計算できるので, その範囲に収まるパッケージがあればそのうち最小のものをとっていけばよい.

ソース

かなり読解に苦労した(30分くらい誤読して ?? ってなってた). 英語は難しいね.

 {56000000} とかいう不穏な定数が見えますね….

自分のパソコンとGCJのテストケースへの†厚い信仰心†があれば通る.

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;
const int64 INF = 1LL << 58;

int64 solve()
{
  int N, P, R[50];
  multiset< int > t[50];

  cin >> N >> P;
  for(int i = 0; i < N; i++) {
    cin >> R[i];
  }
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < P; j++) {
      int s;
      cin >> s;
      t[i].emplace(s);
    }
  }

  int64 ret = 0;
  for(int i = 0; i < 56000000; i++) {
    int64 highest = INF;
    for(int j = 0; j < N; j++) {
      int64 low = (1LL * R[j] * i * 9 + 9) / 10;
      int64 high = (1LL * R[j] * i * 11) / 10;
      if(t[j].empty() || low > *--t[j].end()) return (ret);
      int64 proc = 0;
      for(auto &p : t[j]) proc += low <= p && p <= high;
      highest = min(highest, proc);
    }
    if(highest > 0) {
      for(int j = 0; j < N; j++) {
        int64 low = (1LL * R[j] * i * 9 + 9) / 10;
        int64 high = (1LL * R[j] * i * 11) / 10;
        int64 proc = 0;
        for(multiset< int >::iterator it = t[j].begin(); it != t[j].end();) {
          if(low <= *it && *it <= high) {
            it = t[j].erase(it);
            ++proc;
          } else {
            ++it;
          }
          if(proc == highest) break;
        }
      }
      ret += highest;
    }
  }
  return (ret);
}

int main()
{
  int T;
  cin >> T;
  for(int i = 1; i <= T; i++) {
    cout << "Case #" << i << ": " << solve() << endl;
  }
}

Problem C. Play the Dragon (Small)

自分の体力  {H_d(1 \le H_d \le 100)}, 攻撃力  {A_d(1 \le A_d \le 100)}, 敵の体力  {H_k(1 \le H_k \le 100)}, 攻撃力  {A_k(1 \le A_k \le 100)} が与えられる.

自分が以下のいずれかの命令を実行し, 次に相手が自分に攻撃する, というのを自分か敵の体力が  {0} 以下になるまで繰り返す.

  • Attack: 現在の攻撃分のダメージを敵に与える.
  • Buff: 自分の攻撃力が  {B(0 \le B \le 100)} 増加する.
  • Cure: 自分の体力が  {H_d} に回復する.
  • DeBuff: 相手の攻撃力が  {D(0 \le D \le 100)} 減少する.

相手を倒すための最短ターンを求めよ. どのようにしても自分が負ける時 “IMPOSSIBLE” を出力せよ.

解法

Small なので色々  {100} 以下. 自分の攻撃力などが  {100} より大きくなっても無駄なことを利用すると,

dp[ターン][min(100,現在の自分の攻撃力)][min(100,現在の自分の体力)][min(100,現在の相手の攻撃力)] := 現在の相手の体力の最小値

とした動的計画法が適用できる. ターン数が微妙だが, 実験をするとなんとなく  {200} 以下になることがわかる.

 {O(N^4)} くらいになる.

ソース

自分のパソコンへの信仰心その  {2}.

#include <bits/stdc++.h>

using namespace std;

void chmin(int &a, int b)
{
  a = min(a, b);
}

const int INF = 1LL << 30;

int dp[101][101][101];
int dp2[101][101][101];


void solve()
{
  int Hd, Ad, Hk, Ak, B, D;
  cin >> Hd >> Ad >> Hk >> Ak >> B >> D;


  fill_n(**dp, 101 * 101 * 101, INF);
  dp[Ad][Hd][Ak] = Hk;

  for(int i = 0; i < 300; i++) {
    fill_n(**dp2, 101 * 101 * 101, INF);
    for(int j = 0; j < 101; j++) {
      for(int k = 0; k < 101; k++) {
        for(int l = 0; l < 101; l++) {
          if(dp[j][k][l] == INF) continue;
          chmin(dp2[j][k][l], dp[j][k][l] - j);
          chmin(dp2[min(100, j + B)][k][l], dp[j][k][l]);
          chmin(dp2[j][Hd][l], dp[j][k][l]);
          chmin(dp2[j][k][max(0, l - D)], dp[j][k][l]);
        }
      }
    }
    fill_n(**dp, 101 * 101 * 101, INF);

    for(int j = 0; j < 101; j++) {
      for(int k = 0; k < 101; k++) {
        for(int l = 0; l < 101; l++) {
          if(dp2[j][k][l] == INF) continue;
          if(dp2[j][k][l] <= 0) {
            cout << i + 1 << endl;
            return;
          }
          if(k - l <= 0) continue;
          dp[j][k - l][l] = dp2[j][k][l];
        }
      }
    }
  }

  cout << "IMPOSSIBLE" << endl;
}


int main()
{
  int T;
  cin >> T;
  for(int i = 1; i <= T; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
}