ei1333の日記

ぺこい

Google Code Jam 2017 Qualification Round

A(Small/Large), B(Small,Large), C(Small1/Small2/Large) を解いて 65 pt.

Problem A. Oversized Pancake Flipper

問題概要

現在のパンケーキの状態が文字列  {S(1 \le |S| \le 1000)} として与えられる.  {S} の各文字は +- で, + はそのパンケーキが表, - は裏であることを意味する.

連続するちょうど  {K(1 \le K \le |S|)} 個のパンケーキを選んで, それらを全て反転させる操作を行える.

操作を何回か行うことでパンケーキを全て表にできるか判定し, 出来る場合は操作の最小回数を求めよ.

解法

なんとなく左から貪欲したい気持ちになる(なんでだろうね).

左から見ていった時に, そのケーキが裏ならそこから  {K} 個分反転させる操作を繰り返す.

‘o’ を反転させると悲しい気持ちになるので, そういう操作だけになる.

最終的にすべてのパンケーキが表であれば, そのときの回数が答え.

ソース

#include <bits/stdc++.h>

using namespace std;

void solve()
{
  string S;
  int K;

  cin >> S;
  cin >> K;

  int ret = 0;

  for(int i = 0; i <= S.size() - K; i++) {
    if(S[i] == '-') {
      for(int j = 0; j < K; j++) {
        S[i + j] = "+-"[S[i + j] == '+'];
      }
      ++ret;
    }
  }

  bool impossible = false;

  for(int i = 0; i < S.size(); i++) {
    if(S[i] == '-') impossible = true;
  }

  if(impossible) {
    cout << "IMPOSSIBLE" << endl;
  } else {
    cout << ret << endl;
  }
}

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

Problem B. Tidy Numbers

問題概要

ある値を文字列と見たときに各桁の数字が左から広義単調増加になっているとき, その値を tidy と呼ぶ.

 {N(1 \le N \le 10^{18})} 以下の値の中で, 最大の tidy である値を求めよ.

解法

dfsっぽくえいする.

この問題を見た瞬間に,

code-festival-2014-quala.contest.atcoder.jp

を思い出して, 実際にもこれをほんの少し変えれば通る(やったぜ).

たぶんソースコードを見たほうがわかりやすい(説明できないわけじゃないのよ…><)

ソース

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;

string A;

bool rec(int last, int idx, bool free, bool ue, int64 value)
{
  if(idx == A.size()) {
    cout << value << endl;
    return (true);
  }

  int end = (ue ? 9 : A[idx] - '0');
  for(int i = end; i >= 0; i--) {
    if(i < last) continue;
    if(free == false && i == 0) {
      if(rec(i, idx + 1, false, ue | (i != end), value * 10 + i)) return (true);
    } else {
      if(rec(i, idx + 1, true, ue | (i != end), value * 10 + i)) return (true);
    }
  }
  return (false);
}

void solve()
{
  cin >> A;
  rec(0, 0, 0, 0, 0);
}

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

Problem C. Bathroom Stalls

問題概要

横に  {N + 2(1 \le N \le 10^{18})} 個のトイレが並んでいて, 両端には誰かが入っている.

 {K(1 \le K \le N)} 人が順番に開いているトイレに入るが, このとき以下の規則に従う.

 {i} 番目の部屋について その部屋の左側で連続して空室な部屋の数を  {L_i}, その部屋の右側で連続して空室な部屋の数を  {R_i} と定義する.

  •  {\min(L_i, R_i)} が最大となる部屋に入る
  • このような部屋が複数ある時は,  {\max(L_i, R_i)} が最大となる部屋にはいる
  • このような部屋が複数ある時は, そのうち最も左の部屋に入る

最後の人が入った部屋について,  {\max(L_i, R_i)} {\min(L_i, R_i)} を求めよ.

解法

よくわからないので, 問題にかかれていることをそのままシミュレーションすればよい.

出てくる  {(\min(L_i, R_i), \max(L_i, R_i))} の種類数は対数オーダーで抑えられそうなので, このような個数を持ってシミュレーションをすればよい.

ソース

なんか不等号を微妙に間違えてセグフォして, その場でデバッグできずに 1 WA した.

4 分というデバッグ時間は短すぎる(そもそもデバッグのための時間ではない).

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;

pair< int64, int64 > getPair(int64 cur)
{
  --cur;
  return {(cur + 1) / 2, cur / 2};
}


void solve()
{
  int64 N, K;
  cin >> N >> K;

  map< pair< int64, int64 >, int64 > que;
  que[getPair(N)]++;
  --K;

  if(K == 0) {
    cout << getPair(N).first << " " << getPair(N).second << endl;
    return;
  }

  for(;;) {
    auto object = *--que.end();

    int64 get = min(K, object.second);
    K -= get;

    if(K == 0 && get <= object.second) {
      auto q = getPair(object.first.first);
      cout << q.first << " " << q.second << endl;
      return;
    }
    if(get > 0) que[getPair(object.first.first)] += get;

    get = min(K, object.second);
    K -= get;
    if(K == 0 && get <= object.second) {
      auto q = getPair(object.first.second);
      cout << q.first << " " << q.second << endl;
      return;
    }
    if(get > 0) que[getPair(object.first.second)] += get;
    que.erase(--que.end());
  }
}

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