Intel Code Challenge Elimination Round (Div.1 + Div.2, combined)

ABCDを解いた.
AをHackされたのは頭悪いなぁ.
1932 → 1968(higest).

A. Broken Clock

codeforces.com

問題概要

${12}$ あるいは ${24}$ 時間表記で表示される壊れた時計がある.

${12}$ 時間表記のとき, 時間は ${1}$ から ${12}$ の範囲で変化し, ${24}$ 時間表記のとき, 時間は ${0}$ から ${23}$ の範囲で変化する.

分はともに ${0}$ から ${59}$ の間である.

${HH:MM}$ の形式で, 壊れた時計に表示された時間が与えられる.

正しいフォーマットとなるように任意の桁を変更する. 変更する桁数を最小にするとき, その時間をどれか出力せよ.

解法

時間と分は独立して考える事が可能.

分は簡単. ${0}$ から ${59}$ の範囲外のとき, 最初の桁を ${0}$ に変更すれば良い.

時間は少し面倒.

${12}$ 時間表記のときを考える. ${HH \% 10 == 0}$ のとき ${10}$ に変更し, ${HH \ge 13}$ のとき最初の桁を ${0}$ に変更すればよい.

${24}$ 時間表記のときを考える. ${HH \ge 24}$ のとき最初の桁を ${0}$ に変更すればよい.

実装によりけりだけど, ${HH \% 10}$ のときがコーナーケース??(これでHackされた

ソース

#include<bits/stdc++.h>

using namespace std;

int main()
{
  int N;
  int H, M;

  scanf("%d", &N);
  scanf("%d:%d", &H, &M);

  if(N == 12) {
    if(H % 10 == 0) printf("10");
    else if(H == 0) printf("01");
    else if(1 <= H && H <= 12) printf("%02d", H);
    else printf("0%d", H % 10);
  } else {
    if(0 <= H && H <= 23) printf("%02d", H);
    else printf("0%d", H % 10);
  }
  putchar(':');
  if(0 <= M && M <= 59) printf("%02d", M);
  else printf("0%d", M % 10);
}

B. Verse Pattern

codeforces.com

問題概要

音節を ${1}$ つの母音(a, e, i, o, u, y のいずれか) と ${0}$ 個以上の子音を含む文字列であると定義する.

${n(1 \le n \le 100)}$ 行にわたって文字列が与えられる.

すべての行で, 文字列を ${p_i(0 \le p_i \le 100)}$ 個の音節に分割できるか判定せよ.

解法

これはやるだけで, それぞれの行で母音が何個あるか数えて ${p_i}$ と比較すれば良い.

ソース

#include<bits/stdc++.h>

using namespace std;

int main()
{
  int N, P[100];
  string temp = "aiueoy";

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

  cin.ignore();

  for(int i = 0; i < N; i++) {
    string K;
    getline(cin, K);
    int sum = 0;
    for(int j = 0; j < K.size(); j++) {
      if(temp.find(K[j]) != string::npos) ++sum;
    }
    if(P[i] != sum) {
      cout << "NO" << endl;
      return(0);
    }
  }

  cout << "YES" << endl;
}

C. Destroying Array

codeforces.com

問題概要

長さ ${n(1 \le n \le 100\ 000)}$ の配列 ${a_i(0 \le a_i \le 10^9)}$ がある.

配列の要素を指定された順番で壊していく.

それぞれの破壊後の配列の状態で, 破壊された要素を含まない連続要素の最大和を出力せよ.

解法

破壊クエリを逆から見ると, すでに現れている左右の連結成分と自分をくっつけるクエリになる.

普通の Union Find に連結成分の要素の和を一緒に持たせておくと答えも分かる.

${\mathcal{O}(\alpha N)}$ .

ソース

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

int64 sum[100000];

struct UnionFind
{
  vector< int > data;

  UnionFind(int sz)
  {
    data.assign(sz, -1);
  }

  void unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x != y) {
      if(data[x] > data[y]) swap(x, y);
      data[x] += data[y];
      data[y] = x;
      sum[x] += sum[y];
    }
  }

  int find(int k)
  {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  int size(int k)
  {
    return (-data[find(k)]);
  }
};

int main()
{
  int N, A[100000], B[100000], C[100000];

  scanf("%lld", &N);

  for(int i = 0; i < N; ++i) {
    scanf("%lld", &A[i]);
  }

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

  UnionFind tree(N);
  int64 ret = 0, ans[100000];
  for(int i = N - 1; i >= 0; i--) {
    ans[i] = ret;
    if(B[i] > 0 && C[B[i] - 1] > i) tree.unite(B[i] - 1, B[i]);
    if(B[i] + 1 < N && C[B[i] + 1] > i) tree.unite(B[i] + 1, B[i]);
    sum[tree.find(B[i])] += A[B[i]];
    ret = max(ret, sum[tree.find(B[i])]);
  }

  for(int i = 0; i < N; i++) {
    printf("%lld\n", ans[i]);
  }
}

C. Destroying Array

codeforces.com

問題概要

長さ ${n(1 \le n \le 50\ 000)}$ の distinct な配列 ${y_i(1 \le y_i \le 10^9)}$ が与えられる.

配列 ${x_i}$ は以下の ${2}$ 種類の操作を何回か繰り返すことにより, ${y_i}$ に含まれる値とすべて同じものにできる distinct な配列である (言い換えるとソートしたときに ${x_i = y_i}$ ).

ある要素を選んで ${2x_i}$ に置換する.
ある要素を選んで ${2x_i + 1}$ に置換する.

要素の最大が最小となる配列 ${x_i}$ を出力せよ.

解法

最大値の最小化なので二分探索したい. 要素の最大を ${x}$ 以下にできるかを判定できれば二分探索できる.

それぞれの要素について ${y_i}$ になることができる ${x_i}$ は ${y_i}$ を何度か ${2}$ で割ったものだけ. この候補は高々 ${\log y_i}$ 個.

既に使った値を set で管理しておく. すると ${y_i}$ に対応する ${x_i}$ は, 候補の中でまだ使っていない値かつ ${x}$ 以下の要素を使うことになる. 小さい値はなるべくあとに残しておきたいのでその中で最大のものを使うようにすると, すべての ${a_i}$ を ${x}$ 以下にできるか判定ができる.

計算量は ${\mathcal{O}(n \log^2 \max(y_i) \log n)}$ になる( ${\log^3}$ でこわいが間に合った.)

ソース

#include<bits/stdc++.h>

using namespace std;

int N, Y[50000], Table[50000][30];

bool check(int val, bool output = false)
{
  set< int > used;
  for(int i = 0; i < N; i++) {
    int pos = 29;
    while(pos >= 0 && (Table[i][pos] > val || used.count(Table[i][pos]))) --pos;
    if(Table[i][pos] == 0) return (false);
    if(used.count(Table[i][pos])) return (false);
    used.insert(Table[i][pos]);
    if(output) cout << Table[i][pos] << " ";
  }
  return (true);
}

int main()
{
  cin >> N;

  for(int i = 0; i < N; i++) {
    cin >> Y[i];
    Table[i][29] = Y[i];
    for(int j = 28; j >= 0; j--) {
      Table[i][j] = Table[i][j + 1] >> 1;
    }
  }

  int low = 0, high = 1 << 30;
  while(high - low > 0) {
    int mid = (low + high) >> 1;
    if(check(mid)) high = mid;
    else low = mid + 1;
  }
  check(low, true);
}

ei1333の日記

ぺこい

Intel Code Challenge Elimination Round (Div.1 + Div.2, combined)

A. Broken Clock

問題概要

解法

ソース

B. Verse Pattern

問題概要

解法

ソース

C. Destroying Array

問題概要

解法

ソース

C. Destroying Array

問題概要

解法

ソース