World CodeSprint 11 - ei1333の日記

75ドルー♪.

Balanced Array

www.hackerrank.com

問題概要

忘れた

解法

覚えてない

ソース

#include<bits/stdc++.h>

using namespace std;

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

const int B = 300;

int main()
{
  int N, A[100] = {};
  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> A[i + 1];
    A[i + 1] += A[i];
  }
  cout << abs(A[N] - A[N / 2] - A[N / 2]) << endl;
}

Numeric String

www.hackerrank.com

問題概要

文章にするのがつらい.

解法

左から尺取りみたいにやる.

ある長さ ${k}$ の区間 ${[i, i + K)}$ を ${10}$ 進表記した値 ${x}$ が分かっているとする.

これを右に ${1}$ 個ずらした区間 ${[i + 1, i + K + 1)}$ に効率的に動かせれば勝ち.

これは数字 ${S_i}$ が消えて, 数字 ${S_{i+K}}$ が入ってくる操作である.

で, 動かした後の値は ${x * m + S_{i+K} - S_i \times m^{K-1}}$ みたいな感じだとわかり, これは ${O(1)}$ でできるので完.

ソース

これわりと悩んだ.

難しい.

#include<bits/stdc++.h>

using namespace std;

int main()
{
  string S;
  int k, m, b;

  cin >> S;
  cin >> k >> m >> b;

  int sum = 0, add = 0, fact = 1;
  for(int i = 0; i < k - 1; i++) (fact *= m) %= b;

  for(int i = 0; i < k - 1; i++) {
    (sum = sum * m + S[i] - '0') %= b;
  }
  int ret = 0;
  for(int i = k - 1; i < S.size(); i++) {
    (sum = sum * m + S[i] - '0') %= b;
    ret += sum;
    int cur = S[i - (k - 1)] - '0';
    int sub = (cur * fact);
    (sum += b - sub % b) %= b;
  }

  cout << ret << endl;

}

Simple File Commands

www.hackerrank.com

問題概要

以下の ${q(1 \le q \le 10^5)}$ の ${3}$ 種類のコマンドを処理せよ.

crt file_name
file_name をつくる. もし既に file_name が存在すれば, file_name の末尾に ( ${x}$ ) を追加する. ここで ${x}$ は同名のファイルが存在しない値のうち最小値である.
del file_name
file_name を消す.
rnm file_name1 file_name2
del file_name1 をしてから crt file_name2 をする.

解法

†気合い† だと思いきや, わりと綺麗な解法がある. 嫌いだけど好き.

ファイル名ごとに優先度つきキュー que[] を用意しておく. で, 削除や挿入時に, 次の同名ファイルが来た時に次の値となるものを適切に管理しておけば解ける.

ソース

#include<bits/stdc++.h>

using namespace std;

map< string, priority_queue< int, vector< int >, greater< int > > > que;

void del(string s)
{
  if(s.find('(') == string::npos) s += "(0)";
  que[s.substr(0, s.find('('))].push(stoi(s.substr(s.find('(') + 1)));
}

string crt(string s)
{
  if(!que.count(s)) {
    que[s].push(1);
    return (s);
  } else {
    int p = que[s].top();
    que[s].pop();
    if(que[s].empty()) que[s].push(p + 1);
    if(p == 0) return (s);
    return (s + "(" + to_string(p) + ")");
  }
}

int main()
{
  int Q;
  cin >> Q;
  while(Q--) {
    string a, b, c;
    cin >> a >> b;
    if(a == "crt") {
      cout << "+ " << crt(b) << endl;
    } else if(a == "del") {
      del(b);
      cout << "- " << b << endl;
    } else {
      cin >> c;
      del(b);
      cout << "r " << b << " -> " << crt(c) << endl;
    }
  }
}

City Construction

www.hackerrank.com

問題概要

${n(1 \le n \le 5 \times 10^4}$ 頂点 ${1 \le m \le 10^4)}$ 辺の有向グラフが与えられる.

時系列順に ${q(1 \le q \le 10^5)}$ 個のクエリが与えられるので処理せよ.

1 x d : 頂点 ${x}$ から頂点 ${n+1}$ に方向 ${d}$ の辺を生やしたあと ${n}$ をインクリメントする

2 x y : 頂点 ${x}$ から頂点 ${y}$ に到達可能か判定する

解法

辺を生やすクエリは最初に処理しておいても, 到達可能クエリのアレには影響しないので, まとめる.

互いに行き来できる頂点同士はまとめたい気持ちになって, これは強連結成分分解すればよい.

強連結成分分解後のグラフは DAG になる.

DAG の到達可能性なので, クエリを ${3000}$ 個(この値は適切に) ごとにわけて bitset で ${3000}$ bit のアレを持たせておいて, トポロジカル順に OR をとっていけば, 頂点 ${x}$ からどの頂点に到達可能かどうかがクエリごとにわかるのでまあできる.

ソース

PCK の鉄道路線と実質同値なので, そっちの解説スライドを見たりすると理解が深まる.

#include<bits/stdc++.h>

using namespace std;

struct StronglyConnectedComponents
{
  vector< vector< int > > gg, rg;
  vector< pair< int, int > > edges;
  vector< int > comp, order, used;

  StronglyConnectedComponents(size_t v) : gg(v), rg(v), comp(v, -1), used(v, 0) {}

  void add_edge(int x, int y)
  {
    gg[x].push_back(y);
    rg[y].push_back(x);
    edges.emplace_back(x, y);
  }

  int operator[](int k)
  {
    return (comp[k]);
  }

  void dfs(int idx)
  {
    if(used[idx]) return;
    used[idx] = true;
    for(int to : gg[idx]) dfs(to);
    order.push_back(idx);
  }

  void rdfs(int idx, int cnt)
  {
    if(comp[idx] != -1) return;
    comp[idx] = cnt;
    for(int to : rg[idx]) rdfs(to, cnt);
  }

  void build(vector< vector< int > > &t)
  {
    for(int i = 0; i < gg.size(); i++) dfs(i);
    reverse(begin(order), end(order));
    int ptr = 0;
    for(int i : order) if(comp[i] == -1) rdfs(i, ptr), ptr++;

    t.resize(ptr);
    set< pair< int, int > > connect;
    for(auto &e : edges) {
      int x = comp[e.first], y = comp[e.second];
      if(x == y) continue;
      if(connect.count({x, y})) continue;
      t[x].push_back(y);
      connect.emplace(x, y);
    }
  }
};

void solve(vector< vector< int > > &graph, vector< int > &X, vector< int > &Y)
{
  vector< bitset< 3000 > > dp(graph.size());

  for(int _ = 0; _ < X.size(); _ += 3000) {
    fill(dp.begin(), dp.end(), 0);
    int start = _, end = min< int >(X.size(), start + 3000);
    for(int i = start; i < end; i++) {
      dp[X[i]][i - start] = 1;
    }
    for(int i = 0; i < graph.size(); i++) {
      if(dp[i].none()) continue;
      for(int j : graph[i]) dp[j] |= dp[i];
    }
    for(int i = start; i < end; i++) {
      puts(dp[Y[i]][i - start] ? "Yes" : "No");
    }
  }
}

int main()
{
  int N, M;
  vector< int > g[50000];
  vector< int > X, Y;

  cin >> N >> M;
  for(int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    g[a].push_back(b);
  }

  int Q;
  cin >> Q;
  for(int i = 0; i < Q; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    --b;
    if(a == 1) {
      if(c == 0) g[b].push_back(N);
      else g[N].push_back(b);
      ++N;
    } else {
      X.push_back(b);
      Y.push_back(--c);
    }
  }

  StronglyConnectedComponents scc(N);
  for(int i = 0; i < N; i++) {
    for(auto &to : g[i]) scc.add_edge(i, to);
  }
  vector< vector< int > > gg;
  scc.build(gg);
  for(int i = 0; i < X.size(); i++) {
    X[i] = scc[X[i]];
    Y[i] = scc[Y[i]];
  }
  solve(gg, X, Y);
}

The Best Mask

www.hackerrank.com

問題概要

長さ ${n}$ の数列が与えられる.

すべての要素とそれぞれ or をとったときに非 0 かつ, 1 の bit 数が最小かつ最小値となる値を求めよ.

部分点解法

枝刈りDFS(このDFSは ${i}$ bit目を立てるか立てないかでそのまま) で気合いをすると 62 点くらい生える.

あと嘘をすると 3 点くらい増える.

ソース

#include<bits/stdc++.h>

using namespace std;

const int MAX = 1000000;

int n = 1000, a[100000];

void stupid()
{
  int large = (1 << 30) - 1;

  for(int i = 0; i < (1 << 19); i++) {
    if(__builtin_popcount(i) > __builtin_popcount(large)) continue;
    if(__builtin_popcount(i) == __builtin_popcount(large) && i > large) continue;
    bool flag = true;
    for(int j = 0; j < n; j++) {
      if(i & a[j]) {}
      else {
        flag = false;
        break;
      }
    }
    if(flag) large = i;
  }
  cout << large << endl;
}

bitset< 100000 > bits[28];
bitset< 100000 > zan[28];

int out[28] = {}, num[28];
int sz = 114, cost;

void dfs(bitset< 100000 > now, int idx, int curr, int sum)
{
  if(now.count() == n) {
    if(sz == sum && curr < cost) {
      cost = curr;
    } else if(sz > sum) {
      sz = __builtin_popcount(curr);
      cost = curr;
    }
    return;
  }
  if((zan[num[idx]] | now).count() < n) return;
  if(sz <= sum) return;
  dfs(now | bits[num[idx]], idx + 1, curr | (1 << num[idx]), sum + 1);
  dfs(now, idx + 1, curr, sum);
}


int main()
{
  cin >> n;
  vector< int > ss;
  for(int i = 0; i < n; i++) {
    cin >> a[i];
    ss.push_back(a[i]);
  }

  for(int i = 0; i < 27; i++) num[i] = i;
  int sz = 0;
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < 27; j++) {
      if((a[i] >> j) & 1) {
        out[j]++;
        ++sz;
        bits[j][i] = true;
      }
    }
  }

  if(sz >= n * 15) {
    stupid();
    return (0);
  }

  sort(num, num + 27, [&](int a, int b)
  {
    return (out[a] > out[b]);
  });
  for(int i = 26; i >= 0; i--) {
    zan[num[i]] |= bits[num[i]];
    if(i) zan[num[i - 1]] |= zan[num[i]];
  }
  bitset< 100000 > bit;
  dfs(bit, 0, 0, 0);
  cout << cost << endl;
}

Figures in an Infinite Grid (Approximate)

問題概要

${n}$ 個のピースを ${w \times h}$ のグリッドに重ならないように敷き詰めたい.

${w \times h}$ の最小値を求めよ.

解法

ピースのセル数が大きい順ソートして, 左上から貪欲に埋めていくと 67 点くらい生える.

小さいケースについてビームサーチすると 3 点増えたが, 効果は薄かったのでソースコードでは省略.

ソース

#include<bits/stdc++.h>

using namespace std;

typedef pair< int, int > Pi;

int N, Y, X;
int mat[5000][5000];

int main()
{
  cin >> N;
  vector< int > pri(N);
  iota(begin(pri), end(pri), 0);
  vector< vector< Pi > > sst;
  for(int i = 0; i < N; i++) {
    int T;
    cin >> T;
    vector< Pi > st(T);
    for(auto &p : st) cin >> p.second >> p.first, --p.first, --p.second;
    sst.push_back(st);
  }

  sort(begin(pri), end(pri), [&](int a, int b)
  {
    if(sst[a].size() == sst[b].size()) return(a > b);
    return (sst[a].size() > sst[b].size());
  });

  for(int i : pri) {
    auto &st = sst[i];

    auto check2 = [&](int x, int y)
    {
      for(auto &p : st) {
        if(y != 0 && p.first + y > Y) return (false);
        if(mat[p.first + y][p.second + x] != 0) return (false);
      }
      for(auto &p : st) {
        Y = max(Y, p.first + y);
        X = max(X, p.second + x);
        mat[p.first + y][p.second + x] = i + 1;
      }
      return (true);

    };

    auto rotate = [&]()
    {
      int xmax = 0, ymax = 0;
      for(auto &pp : st) xmax = max(pp.second, xmax);
      for(auto &pp : st) ymax = max(pp.first, ymax);
      for(auto &pp : st) pp = {xmax - pp.second, pp.first};
    };

    auto check = [&](int x)
    {
      for(int pp = 0; pp < 4; pp++) {
        int y = 0;
        while(!check2(x, y) && y < 700) ++y;
        if(y < 700) return (true);
        y = 0;
        rotate();
      }
      return (false);
    };

    int x = 0;
    while(!check(x++));
  }
  cout << Y + 1 << " " << X + 1 << endl;
  for(int i = 0; i <= Y; i++) {
    for(int j = 0; j <= X; j++) {
      cout << mat[i][j] << " ";
    }
    cout << endl;
  }
}

Road Trip

www.hackerrank.com

問題概要

疲れた.

解法

${O(NQ)}$ 解なら自明で, 足りなくなったら今まで訪れたガソリンスタンドで一番安いものを買うようにする貪欲でいい.

テストケースが弱いため 96.67 点とれる.

ソース

#include<bits/stdc++.h>

using namespace std;

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

int N, Q;
int64 W[200000], G[200000], P[200000];

int main()
{

  cin >> N >> Q;
  for(int i = 0; i < N - 1; i++) {
    cin >> W[i];
  }
  for(int i = 0; i < N; i++) {
    cin >> G[i] >> P[i];
  }

  int64 ans[200000] = {};
  vector< pair< int, int > > vq[200000];
  for(int i = 0; i < Q; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    vq[a].emplace_back(b, i);
  }

  for(int j = 0; j < N; j++) {
    if(vq[j].empty()) continue;
    sort(begin(vq[j]), end(vq[j]));
    int64 smallest = INF, curr = 0, cost = 0LL;
    int64 tail = 0;
    for(int i = j; i < vq[j].back().first; i++) {
      curr += G[i] - W[i];
      smallest = min(smallest, P[i]);
      if(curr < 0) {
        cost += -curr * smallest;
        curr = 0;
      }
      while(tail < vq[j].size() && i + 1 == vq[j][tail].first) {
        ans[vq[j][tail].second] = cost;
        ++tail;
      }
    }
  }

  for(int i = 0; i < Q; i++) cout << ans[i] << endl;
}