Codeforces Round #355 (Div. 2)

ABCDを出してBDは落ちた. 悪い癖.
ちょっとやらかしてしまったよね...

A. Vanya and Fence

問題概要

高さ のフェンスがある.
の人がいて身長はそれぞれ であり, 幅は 1 である. 人はしゃがむことができて, しゃがむと身長は半分になるが幅が 2 になる.

フェンス沿いの道路にそって, 人の人が1列になって歩く. を超えないようにするとき, 必要な道路の最小値を求めよ.

解法

明らかに を超える人々のみしゃがめばよい. その人数を とすると, 答えは となる.

ソース

#include <bits/stdc++.h>
using namespace std;

int main()
{
  int N, H;
  cin >> N >> H;

  int ret = 0;
  while(N--) {
    int a;
    cin >> a;
    ++ret;
    if(a > H) ++ret;
  }
  cout << ret << endl;
}

B. Vanya and Food Processor

問題概要

芋粉砕機がある. 芋粉砕機には随時芋を何個か重ねて入れることが可能だが, 一度に入れることが可能な量は高々 である.
1回の操作で までの芋を潰すことができる.

大きさ の 個の芋を順番に入れる. 最小何回の操作ですべての芋を潰すことができるか.

解法

頑張って限界まで芋を入れながらシミュレーションする.
芋をオーバーキルしそうなときは, 次の芋を見てがんばる.

ソース

int 型でオーバーフローすることを失念していた...

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main()
{
  int N, H, K;
 
  cin >> N >> H >> K;

  queue < int > A;
  for(int i = 0; i < N; i++) {
    int a;
    cin >> a;
    A.push(a);
  }

  
  int stock = 0;
  int ret = 0;
  
  while(true) {
    while(!A.empty() && stock + A.front() <= H) {
      A.pop();
    }

    int which = stock / K;
    ret += which;
    stock -= which * K;
    
    if(A.empty()) break;
    
    if(stock + *A.front() > H) {
      ++ret;
      stock = 0;
    }
  }
  
  cout << ret + (stock != 0) << endl;
}

C. Vanya and Label

問題概要

64進数の文字列 が与えられる.
bit単位のANDをとった時, となるような 2 つの文字列のペアの候補数を で割った余りで求めよ.

解法

まず, ANDは文字位置で独立なので, それぞれの文字で分離して考えることができる.
すると, ANDをして文字 になるような文字ペアを求めたくなるが、これは前計算で簡単にできる.
あとは掛けるだけ.

ソース

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;

string poyo = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz-_";

int main()
{

  int lookup[64] = {};
  for(int i = 0; i < 64; i++) {
    for(int j = 0; j < 64; j++) {
      for(int k = 0; k < 64; k++) {
        if((j & k) == i) lookup[i]++;
      }
    }
  }
  
  string s;
  cin >> s;

  int ret = 1;
  for(int i = 0; i < s.size(); i++) {
    ret = (1LL * ret * lookup[poyo.find(s[i])]) % mod;
  }
  cout << ret << endl;
}

D. Vanya and Treasure

問題概要

の 2 次元グリッドのマップがある.
それぞれのセルには鍵 がある.
1 から順に までの鍵を1つずつ得るとき, 最小移動(マンハッタン)距離を求めよ.

解法

鍵 がある位置から鍵 を得ることを考える.
BFS で求めれば だが が大きい時, 合計 となってTLE.
鍵 の位置を保存しておいて総当りすることもできるが, 鍵 があるセル数が多い時, 合計 となってやはり TLE.

そこで, 鍵 の数によって, DP と BFS を使い分ける. それぞれの欠点を補完することができ, いい感じに計算量を抑えられて間に合う. 多分計算量は くらい.

ソース

BFSをDijkstraにしたら落ちた...
他の人々のを見ると, どうも 4 * W * H の閾値設定がまずいらしい.

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1LL << 60;
const int dy[] = {0, 1, 0, -1}, dx[] = {1, 0, -1, 0};

int H, W, P;
vector< pair< int, int > > point[300 * 300 + 1];
int memo[300][300];
int cost[300][300];
int ps[300][300];

signed main()
{
  fill_n(*cost, 300 * 300, INF);
  
  scanf("%I64d %I64d %I64d", &H, &W, &P);
  
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      scanf("%I64d", &ps[i][j]);
      point[ps[i][j]].push_back({i, j});
    }
  }
  
  for(auto& to : point[1]) {
    cost[to.first][to.second] = min(cost[to.first][to.second], to.first + to.second);
  }
        
  int ret = INF;
  for(int i = 2; i <= P; i++) {
    if(point[i - 1].size() * point[i].size() > 4 * W * H) {
      queue< pair< int, pair< int, int > > > que;
      fill_n(*memo, 300 * 300, INF);
      for(auto k : point[i - 1]) {
        memo[k.first][k.second] = cost[k.first][k.second];
        que.push({cost[k.first][k.second], k});
      }
      while(!que.empty()) {
        auto p = que.front(); que.pop();
        if(p.first > memo[p.second.first][p.second.second]) continue;
        if(ps[p.second.first][p.second.second] == i) {
          cost[p.second.first][p.second.second] = p.first;
        }
        for(int i = 0; i < 4; i++) {
          int ny = p.second.first + dy[i], nx = p.second.second + dx[i];
          if(ny < 0 || ny >= H || nx < 0 || nx >= W) continue;
          if(p.first + 1 >= memo[ny][nx]) continue;
          memo[ny][nx] = p.first + 1;
          que.push({memo[ny][nx], {ny, nx}});
        }
      }
      
    } else {
      for(auto& from : point[i - 1]) {
        for(auto& to : point[i]) {
         cost[to.first][to.second] = min(cost[to.first][to.second], cost[from.first][from.second] + abs(from.first - to.first) + abs(from.second - to.second));
        }
      }
    }
  }

  for(auto& to : point[P]) {
    ret = min(ret, cost[to.first][to.second]);
  }
  printf("%I64d\n", ret);
}