Hello 2018 - ei1333の日記

ooooo--- 109th. 1962 -> 2108(+146).

Hello 2018 できた.

A. Modular Exponentiation

codeforces.com

問題概要

${m \bmod 2^n(1 \le n, m \le 10^8)}$ を出力せよ.

解法

${2^n}$ が ${m}$ より大きければ mod は無視してよい.

余裕をもって ${m \bmod 2^{\min(n,29)}}$ を出力すれば十分.

ソース

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int N, M;
  cin >> N >> M;
  int base = 1;
  for(int i = 0; i < min(N, 30); i++) base *= 2;
  cout << M % base << endl;
}

B. Christmas Spruce

codeforces.com

問題概要

${n(3 \le n \le 1000)}$ 頂点の根付き木が与えられる.

すべての葉以外の頂点が, ${3}$ つ以上の葉を持つか判定せよ.

解法

判定をします.

${O(n)}$ .

ソース

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int64 N;
  vector< int > g[1000];

  cin >> N;
  for(int i = 1; i < N; i++) {
    int x;
    cin >> x;
    g[--x].emplace_back(i);
  }

  for(int i = 0; i < N; i++) {
    if(g[i].empty()) continue;
    int sum = 0;
    for(auto& j : g[i]) if(g[j].empty()) ++sum;
    if(sum < 3) {
      cout << "No" << endl;
      return (0);
    }
  }

  cout << "Yes" << endl;
}

C. Party Lemonade

codeforces.com

問題概要

${n(1 \le n \le 30)}$ 種類のボトルがある. ボトル ${i}$ には ${2^{i-1}}$ のレモネードが入っていて, コストは ${c_i(1 \le c_i \le 10^9)}$ である.

${L(1 \le L \le 10^9)}$ 以上のレモネードを買うための最小コストを求めよ.

解法

まず各 ${i}$ について, ちょうど容量 ${2^{i-1}}$ のレモネードを買うための最小コストを求める. これは雰囲気で min をとるとできる.

次に ${L}$ 以上のレモネードを買うための最小コストを求める. ${L}$ を上の bit からみていって, 基本的には ${1}$ が立ってる bit の容量は買う必要があるが, ある bit で余分に買ってもよくてこのときそれより下の bit の購入は不要になる. 余分に買う bit 位置を全探索.

なんか考察ミスや実装ミスが不安だけど, お祈りをすると通る. ${O(n)}$ .

ソース

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;
const int64 INF = 1LL << 61;

int main()
{
  int N, L;
  int64 C[33];
  fill_n(C, 33, INF);

  cin >> N >> L;
  for(int i = 0; i < N; i++) {
    cin >> C[i];
  }

  for(int i = 31; i >= 0; i--) C[i] = min(C[i], C[i + 1]);
  for(int i = 1; i < 33; i++) C[i] = min(C[i], C[i - 1] + C[i - 1]);

  int64 sum = 0, ret = INF;
  for(int i = 31; i >= 0; i--) {
    if((L >> i) & 1) {
      ret = min(ret, sum + C[i + 1]);
      sum += C[i];
    }
  }

  cout << min(sum, ret) << endl;
}

D. Too Easy Problems

codeforces.com

問題概要

${n(1 \le n \le 2 \times 10^5)}$ 個の問題があって, 問題 ${i}$ は ${t_i(1 \le t_i \le 10^4)}$ ms で解決できる.

試験の得点は, ${k}$ 個の問題 ${p_1, p_2, \dots, p_k}$ を解いたとすると ${k \le a_{p_j}}$ の個数である. このとき ${T(1 \le T \le 10^9)}$ ms の間に得られる最大の得点を求めよ.

解法

priority_queue を持ちながらえい.

まず ${x}$ 点を得るとき ${x}$ 問解くのが最善である. ${x}$ 問より多くの問題を解くのは時間がかかるだけ. またこのとき解く問題の候補は ${a_j \ge x}$ の問題のみ. ${a_j \lt x}$ の問題を解いても得点は得られない.

最短時間で ${x}$ 問解くためには, 候補の中から昇順で ${x}$ 個とるのが最適で, この和が ${T}$ 以下であれば ${x}$ 点を得れる.

${x}$ が大きい順に全探索して, 条件を満たしたところが答え. 候補の問題の個数は ${x}$ の減少にともなって単調増加になっているため, priority_queue をもつといい感じに前の計算結果を利用できて ${O(n \log n)}$ .

ソース

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

int main()
{
  int N, T;

  scanf("%d %d", &N, &T);
  vector< pair< int, int > > D[200001];
  for(int i = 0; i < N; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    D[x].emplace_back(y, i);
  }

  priority_queue< pair< int, int > > que;
  int64 in = 0;


  for(int i = N; i >= 0; i--) {
    for(auto &p : D[i]) {
      que.emplace(p);
      in += p.first;
    }
    while(que.size() > i) {
      in -= que.top().first;
      que.pop();
    }
    if(que.size() == i && in <= T) {
      printf("%d\n%d\n", i, i);
      while(que.size()) {
        printf("%d ", que.top().second + 1);
        que.pop();
      }
      return (0);
    }
  }
}

E. Logical Expression

codeforces.com

問題概要

わかりやすいので原文を読んで♡

解法

DP.

Emin[bit] := 真理値表が bit のとき, E をつくるときの最小の文字列
Tmin[bit] := 真理値表が bit のとき, T をつくるときの最小の文字列
Fmin[bit] := 真理値表が bit のとき, F をつくるときの最小の文字列

生成規則は問題文に書かれているため, 遷移もそれに従って書くとできる. ${O(n^3)}$ くらい.

ソース

本番のとき無理全探索をしてて嵌ってた.

#include <bits/stdc++.h>

using namespace std;

string Emin[256], Tmin[256], Fmin[256];

bool chmin(string &a, string b)
{
  if(a.empty() || a.size() > b.size() || (a.size() == b.size() && b < a)) {
    a = b;
    return (true);
  }
  return (false);
}

int main()
{
  fill_n(Emin, 256, string(1000, '~'));
  fill_n(Tmin, 256, string(1000, '~'));
  fill_n(Fmin, 256, string(1000, '~'));

  Fmin[0b00001111] = "x";
  Fmin[0b00110011] = "y";
  Fmin[0b01010101] = "z";
  bool update = true;
  while(update) {
    update = false;
    for(int i = 0; i < 256; i++) {
      update |= chmin(Fmin[i ^ 255], "!" + Fmin[i]);
      update |= chmin(Fmin[i], "(" + Emin[i] + ")");
      update |= chmin(Emin[i], Tmin[i]);
      update |= chmin(Tmin[i], Fmin[i]);
      for(int j = 0; j < 256; j++) {
        update |= chmin(Emin[i | j], Emin[i] + "|" + Tmin[j]);
        update |= chmin(Tmin[i & j], Tmin[i] + "&" + Fmin[j]);
      }
    }
  }

  int N;
  cin >> N;
  while(N--) {
    string bit;
    cin >> bit;
    int bits = 0;
    for(int i = 0; i < 8; i++) if(bit[i] == '1') bits |= 1 << (7 - i);
    cout << Emin[bits] << endl;
  }
}