cafelier@SRM

SRM523 900

あとで | 08:13 |

思ったよりTLE厳しかった。

続きを読む

SRM519 900

あとで | 18:10 |

とっさにこれが書けないのはまだまだDP脳が足りてない。

続きを読む

SRM515 1000

あとで | 21:03 |

Rからの距離をBFSしてFからの距離をBFSして足し算してそこからLまでの距離をBFS。

続きを読む

競技プログラマのためのC++0xB

21:40 |

長らく C++0x と呼ばれていた C++ の次期国際規格が C++11 となることがほぼ決まった そうです。Topcoder で使えるようになるのが何年先かわかりませんが、Codeforces や、言語に制限のないコンテストでは、新しい g++ や VC++ を選択することで、今でもすでにかなりの機能を使うことができます。ということで布教。みんな使おう。

emplace_back

vector<pair<int,string>> v;
v.emplace_back(123, "hello");

push_back の代わりに使うと、追加したいオブジェクト「のコンストラクタに渡す引数」を指定して要素を増やせます。以前なら v.push_back(make_pair(123, "hello")); や v.push_back(pair<int,string>(123, "hello")); などと書いていたもので、比較するとコピーやキャストが起きる起きない等の違いもありますが、実際問題としては、単純に、いちいちコンストラクタ呼び出し書かなくていいので楽。

可変引数 min/max

cout << min({3,4,2,5,1,6}) << endl;

min(min(x,y),min(z,w)); のようなコードはもう不要。

<tuple>

tuple<int, double, string> t(1, 2.34, "hello");
cout << get<0>(t) << " " << get<1>(t) << endl;

pairは二つ組でしたがtupleなら何個でも。pair<pair<int,int>,int> よサヨウナラ。あと

enum {COST, NODE};
while( !dijkstra_queue.empty() ) {
  pair<double, vert> state = dijkstra_queue.top();
  if( get<NODE>(state) == goal ) ...
}

tupleに限らずpairでも、.first や .second じゃなくて get でアクセスできるので適当にenumでも置いておけばそれっぽい名前でアクセスしてる気分になれます。これが本当に良いコードかはさておき…。

initializer list

map<string, int> eng2int = {
  {"zero", 0},
  {"one",  1},
  {"two",  2},
};

mapやvectorでも、構造体や配列の初期化と同じ { ... } の構文で初期化。テストデータを書くときのお供に。

map::at

const map<string, int> eng2int;
int x = eng2int.at("two");

eng2int["two"] は const では無いので、変換表などを一度mapで作って固定したまま使い回す、という状況では「変更しないのに非constで扱う」か「簡潔なアクセスを捨てて.findで長々しいアクセスをする」の酷い二択を迫られていましたが、atならconstでmapを参照できます。

範囲 for 文

set<int> visited;
for(int v : visited)
  cout << v << endl;

auto

map<vector<int>, long long> memo;
auto it = memo.find(key);
if( it != memo.end() ) return it->second;

この辺りは説明不要と思います。もちろん範囲for文とautoの組み合わせも可です。

unordered_xxx

unordered_map<long long, string> table;

いわゆる O(1) アクセスのハッシュ表。mapではダメで unordered_map でないと…という問題がコンテストででることはほぼないかもしれませんが…

無名関数

vector<string> v = ...;
map<string, int> score = ...;
sort(v.begin(), v.end(), [&](const string& x, const string& y){return score[x] < score[y];});

[] で始めると周囲のローカル変数にはアクセスしない関数、[=] だと値コピー、[&] だと参照で周囲の環境をキャプチャします。もっと細かい制御もできますが、とりあえずは [&] しとけば楽（いい加減すぎて怒られそう）。

iota, all_of, any_of, none_of

if( all_of(v.begin(), v.end(), [](int x){return x>0;}) ) ...;

vector<int> v(100);
iota(v.begin(), v.end(), 0); // v={0,1,2,...,99};

アルゴリズムもいろいろ。無名関数書けるようになったので使いやすさは増しているはず。

※追記

C++11最大の改善点に触れるのを忘れていました！

vector<vector<int>> dp;

> と > の間にスペースいらない！

KUPC11

22:50 |

おもしろかった。提出したコード無編集貼り付け。問題文はこちら。

A

数える。

int main()
{
   string s;
   getline(cin, s);
   int K = count(s.begin(), s.end(), 'K');
   int U = count(s.begin(), s.end(), 'U');
   int P = count(s.begin(), s.end(), 'P');
   int C = count(s.begin(), s.end(), 'C');
   cout << min(min(K,U),min(P,C)) << endl;
}

B

ザ・DP。

int main()
{
   int H, W;
   cin >> H >> W;
   vector<string> M(H);
   for(int y=0; y<H; ++y)
      cin >> M[y];

   vector< vector<int> > dp(H, vector<int>(W));
   for(int y=0; y<H; ++y)
      for(int x=0; x<W; ++x)
         if(y||x)
            dp[y][x] = min(y?dp[y-1][x]:99999999, x?dp[y][x-1]:99999999) + M[y][x]-'0';
   cout << dp[H-1][W-1] << endl;
}

C

「あ」攻め。

int main()
{
   char ch = 'a';
   set<string> used;
   for(int i=0 ;; ++i)
   {
      string me = string(1,ch) + char(i/26+'a') + char(i%26+'a') + 'a';
      cout << "?" << me << endl;
      used.insert(me);
      string you;
      cin >> you;
      if( used.count(you) || me[me.size()-1]!=you[0] ) {
         cout << "!OUT" << endl;
         return 0;
      }
      used.insert(you);
      ch = you[you.size()-1];
   }
}

D

すべて50%50%でランダムに0/1を決めれば、どのカードの和も期待値N/4になる。Nが大きければ[N/8, 3N/8]から逸れる確率は限りなくゼロに近い。N小さくても高い確率でこのゾーンに入るので、繰り返せば限りなく１に近い確率で入る。

bool check(const vector<int>& s, const vector< vector<int> >& card)
{
   for(int k=0; k<card.size(); ++k) {
      int sum = 0;
      for(int i=0; i<card[k].size(); ++i)
         sum += s[card[k][i]-1];
      if( sum < s.size()/8 || s.size()/8*3 < sum )
         return false;
   }
   return true;
}

int main()
{
   srand(time(0));

   int N, K;
   cin >> N >> K;
   vector< vector<int> > card(K, vector<int>(N/2));
   for(int k=0; k<K; ++k) {
      for(int i=0; i<N/2; ++i)
         cin >> card[k][i];
   }
   vector<int> s(N);
   for(;;) {
      for(int i=0; i<N; ++i)
         s[i] = rand()%2;
      if( check(s, card) ) {
         for(int i=0; i<N; ++i)
            cout << s[i];
         cout << endl;
         return 0;
      }
   }
}

I

列の交換は行の山nessに影響しないし、逆もそうなので、まず列を並べ替えて、次に行を、と別々に。O(N^3)に見えますがメモ化再帰の部分そこまで探索空間全部見尽くす入力ないような気がする。

vector<int> memo;
bool rec(const vector< vector<int> >& r, int H, int W, int L, int R)
{
   int N = max(L,R)+1;
   if( N >= W )
      return true;

   if(L>R)swap(L,R);
   int key = L*W+R;
   if(memo[key])
      return memo[key]==1;

   bool left = true;
   for(int y=0; y<H; ++y)
      if( r[L][y] >= r[N][y] )
         left = false;

   bool right = true;
   for(int y=0; y<H; ++y)
      if( r[R][y] >= r[N][y] )
         right = false;

   bool can = false;
   if( left && !can ) can = rec(r, H, W, N, R);
   if( right && !can ) can = rec(r, H, W, L, N);
   memo[key]=(can ? 1 : -1);
   return can;
}
bool ok(const vector< vector<int> >& h, int H, int W)
{
   vector< vector<int> > rank(H, vector<int>(W));
   for(int y=0; y<H; ++y) {
      vector< pair<int,int> > hi;
      for(int x=0; x<W; ++x)
         hi.push_back(make_pair(h[y][x],x));
      sort(hi.rbegin(), hi.rend());
      for(int i=0; i<W; ++i)
         rank[y][hi[i].second] = i;
   }

   vector< vector<int> > r(W);
   for(int x=0; x<W; ++x)
      for(int y=0; y<H; ++y)
         r[x].push_back(rank[y][x]);
   sort(r.begin(), r.end());

   for(int y=0; y<H; ++y)
      if( r[0][y] != 0 )
         return false;

   memo.assign(W*W, 0);
   return rec(r,H,W,0,1);
}

int main()
{
   int H, W;
   cin >> H >> W;
   vector< vector<int> > h(H, vector<int>(W));
   vector< vector<int> > htr(W, vector<int>(H));
   for(int y=0; y<H; ++y)
      for(int x=0; x<W; ++x) {
         cin >> h[y][x];
         htr[x][y] = h[y][x];
      }

   cout << (ok(h,H,W) && ok(htr,W,H) ? "YES" : "NO") << endl;
}

E

10^6までの素数をエラトステネスの篩で作りながら、目標区間[A-B,A+B]の数字をその素数で割っていく。何回割れたか覚えておいて（last_e）増えてたらアウト。

int main()
{
   LL A, B;
   cin >> A >> B;
   vector<LL> cand;
   LL start = max(2LL, A-B);
   for(LL x=start; x<=A+B; ++x)
      cand.push_back(x);
   vector<int> last_e(A+B-start+1, 0x7fffffff);
   int cnt = last_e.size();

   static const int PM = 1000000;
   vector<bool> is_prime(PM+1, true);
   for(int p=2; p<=PM; ++p)
      if( is_prime[p] ) {
         for(int q=p+p; q<=PM; q+=p)
            is_prime[q] = false;

         for(int i=(p-start%p)%p; i<cand.size(); i+=p)
            if( last_e[i] )
            {
               int e = 0;
               LL c = cand[i];
               while( c%p == 0 ) {
                  c /= p;
                  ++e;
               }
               if( last_e[i] >= e )
                  last_e[i] = e;
               else
                  last_e[i] = 0, cnt--;
            }
      }

   cout << cnt << endl;
}

H

二分探索で焼け具合Vまで焼けるか探索。Vが決まれば、各鉄板では

• 1秒でVまで焼き尽くす地獄の業火 V*C[i]
• このまま残り時間いっぱい動かないとギリギリ焼き尽くす低温火傷作戦 V*C[i]/残り時間

のどっちかだけやってみる、というのを嘘解法のつもりでsubmitしたら通ってしまったがこれでよい理由がわかっていない。最初内側のループでも２分探索していて、さすがに 10^5 * log(10^10)^2 はTLEだったのですが誤差と２分探索の回数のベストバランスを探るメタレベル２分探索などをやって6WA出したりしていました。

template<typename Ite>
double minEneFor(Ite s, Ite e, double V)
{
   double curE = 0;
   double best = 1e+300;
   for(; s!=e; ++s) {
      best = min(best, curE+V**s);
      double heatForS = V / (e-s);
      double eneForS = heatForS * *s;
      curE += eneForS;
      V    -= heatForS;
   }
   return best;
}

bool canHeat(int T, double E, const vector<double>& C, double V)
{
   double heatFor0 = V / (T+1);
   double eneFor0 = heatFor0 * C[T];
   return eneFor0
      + minEneFor(C.begin()+T+1, C.end(), V-heatFor0)
      + minEneFor(C.rbegin()+T+1, C.rend(), V-heatFor0) <= E;
}

int main()
{
   int T;
   double E;
   cin >> T >> E;
   vector<double> C(2*T+1);
   for(int i=0; i<C.size(); ++i)
      cin >> C[i];

   double L = E / C[T];
   double R = (E / *min_element(C.begin(), C.end())) * (T+1) + 0.000001;
   for(int _=0; _<100; ++_) {
      double Ce = (L+R)/2;
      (canHeat(T,E,C,Ce) ? L : R) = Ce;
   }

   cout << setiosflags(ios::fixed) << setprecision(9) << L << endl;
}

※追記：そうか、V/残り時間ちょうどギリギリ焼き切れるよりも強めに炙った方が良いという可能性があるとしたら、それは、その鉄板より先がすべてその鉄板より熱効率悪い場合しかなくて、その場合はその鉄板で目一杯焼き尽くすのがよい。よってこの２通りのどちらか、でいいのかな？

G

ランダムに0/1決めれば50%の確率で答えが1になる。1になれば、そのとき入力につかっていたビット集合を二つに分けたらどちらかは1になるので、これを繰り返すと最終的に1になるところが決まる。これをK≦10繰り返す。めんどうだったので二つに分ける部分もランダムに分けた…。

map<vector<int>, int> memo;
int ask(const vector<int>& b)
{
   if(memo.count(b))
      return memo[b];

   cout << "?";
   for(int i=0; i<b.size(); ++i)
      cout << b[i];
   cout << endl;

   int res;
   cin >> res;
   return memo[b] = res;
}

int main()
{
   srand(time(0));
   int N, K;
   cin >> N >> K;

   set<int> done;
   while( done.size() < K )
   {
      vector<int> b, cand;
      for(int i=0; i<N; ++i) {
         b.push_back( done.count(i) ? 0 : rand()%2 );
         if(b.back())
            cand.push_back(i);
      }

      int res = ask(b);
      if(res)
      {
         while(cand.size() > 1) {
            vector<int> bb(N);
            vector<int> cX, cY;
            for(int i=0; i<cand.size(); ++i)
               if(rand()%2) {
                  bb[cand[i]] = 1;
                  cX.push_back(cand[i]);
               } else {
                  cY.push_back(cand[i]);
               }
            int r = ask(bb);
            swap(cand, r ? cX : cY);
         }
         done.insert(cand[0]);
      }
   }

   cout << "!";
   for(set<int>::iterator it=done.begin(); it!=done.end(); ++it)
      cout << (it==done.begin() ? "" : " ") << (1 + *it);
   cout << endl;
}

100000C10 ≦ 2^200 なので適切にバランスよい戦略をとれば決定的なアルゴリズムでも確定できるのだろうか。