Hatena::Grouptopcoder

capythm@TopCoder このページをアンテナに追加 RSSフィード

2012-11-18

Codeforces Round #150 (Div. 2)

21:03 | Codeforces Round #150 (Div. 2) - capythm@TopCoder を含むブックマーク はてなブックマーク - Codeforces Round #150 (Div. 2) - capythm@TopCoder Codeforces Round #150 (Div. 2) - capythm@TopCoder のブックマークコメント

ooo-- 2040pt で 47位、とかなり好調だったので日記書きます。

A. Dividing Orange

問題文 http://codeforces.com/contest/244/problem/A

問題概要

みかんの房(?)がn×k個ある。それぞれの房には1~n×kの番号が付いている。

子供がk人にて、それぞれの子供にn個ずつ分け与えたいが、それぞれの子供には a_i (i=1..k)番目の房が必ず行き渡るようにしなければならない。

それぞれの子供に分け与えるべき房の番号を出力せよ。

解法

やるだけ。

こういう問題は出力速度よりもコーディング速度を優先して書く。

ソースコード(汚い)

http://codeforces.com/contest/244/submission/2568357

B. Undoubtedly Lucky Numbers

問題文 http://codeforces.com/contest/244/problem/B

問題概要

十進表記したときに(先頭のゼロを除いて)2種類の数字のみで構成されている数値をLucky Numberと呼ぶ。

 n (1\leq n\leq 10^9)が与えられたとき、nを超えない正整数のLucky Numberの個数を求めよ。

解法

2桁まではすべての数値がLucky Numberなので、n≦99 なら n が答え。

o桁以上(o≧3)の場合は、

・数字が1種類のパターンを数え上げる

・先頭に0が来ないパターンに気をつけて、数字が2種類のパターンを数え上げる

(ただし、競技中はこう考えたけど、もっといい解法があると思う。)

ソースコード

汚い。デバッグに苦労した。

低速版のcalc2関数と値が同じになるようにcalc関数をデバッグした。

http://codeforces.com/contest/244/submission/2571096

C. The Brand New Function

問題文 http://codeforces.com/contest/244/problem/C

問題概要

数列 \{a_i\}が与えられる。

 f(l,r) = a_l | a_{l+1} | ... | a_rと定義する。

すべてのl,rを考えたとき、f(l,r)の取り得る値の個数を求めよ。

解法

(競技中は適当にsubmitして通ってしまったので、後から考えた結果をまとめる。)

 P_k f(l,k) (l\leq k)の集合と考えると、

 P_k = \{ a_k, a_k | a_{k-1}, a_k | a_{k-1} | a_{k-2}, ..., a_k | ... | a_1 \}

となる。最悪ケースで、 P_kのユニークな要素の個数はk個になると思ってしまいそうだが、

 a_iの制約条件が 10^6以下、つまり20ビットで表現できる値のため、

 P_kの要素数はたかだか21個である。

また、 P_{k+1}の要素は a_{k+1}および P_kの各要素に a_{k+1}を OR 演算したものであるから、

 P_kをメモしておけば P_{k+1}の最悪計算量は O(21)=O(1)となる。

出力すべき値は、 {P_1, P_2, ..., P_n}のユニークな要素の個数である。

最悪計算量はO(21×n)で、nが 10^5程度なので、上記を素直に実装すれば十分間に合う。

ソースコード(美しい・・・)

http://codeforces.com/contest/244/submission/2572707

#include <iostream>
#include <set>
using namespace std;
int main( void )
{
  int n,a;
  set<int> s,t[2];
  cin >> n;
  for( int i=0; i<n; i++ ){
    cin >> a;
    int c = i&1;
    t[c].clear();
    for( set<int>::iterator it = t[1-c].begin(); it != t[1-c].end(); ++it ){
      t[c].insert( *it | a );
    }
    t[c].insert( a );
    for( set<int>::iterator it = t[c].begin(); it != t[c].end(); ++it ){
      s.insert( *it );
    }
  }
  cout << s.size() << endl;
  return 0;
}

ただし、sはsetでなく、staticな配列で持っておく方がより早く計算できたかも。