naoya_t@topcoder

Codeforces Beta Round #17 (Div.2)

22:17 |

• やってる事に気づき、途中から外野で問題を解いてみた。50分ぐらい
• これは自分のレーティング（lieutenant）だと参加できないのか？

続きを読む

Google Code Jam 2009: Round 2

過去問 | 19:38 |

• 去年のRound 2の問題を見てみた
• 去年は1758/3000位だったらしい。(500位で通過)
• しかし同じ問題だったらアウトな感じ

A. Crazy Rows

• [2,1,1,0] みたいな配列を [0,1,2,3] かそれ以下にするswapの回数。
• v[i]>iの場合、最初に手に入るi以下の数字を持ってくる。
• その繰り返し(0..N-1)でswap回数の和を取れば終わる

#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cctype>
using namespace std;

#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)

int main(){
  int T; cin >> T;//1..60
  rep(t,T){
    int N; cin >> N;//1..40
    vector<int> m(N,-1);
    rep(n,N){
      string s; cin >> s;
      rep(i,N) if(s[i]=='1')m[n]=i;
    }

    int k=0;
    rep(n,N){
      if (m[n]<=n) continue;
      for(int i=n+1;i<N;++i){
        int t=m[i];
        if(t<=n) { //n..)i
          k += i-n;
          for(int j=i;j>n;--j) m[j]=m[j-1];
          m[n] = t;
          break;
        }
      }
    }
    printf("Case #%d: %d\n", t+1, k);
  }
  return 0;
}

B. A Digging Problem

• あー。
• あとで見る

C. Stock Charts

• クロスないしタッチしてるかどうか見て、組分けの考えられる組み合わせを全て試す方法ではsmallならなんとか時間に間に合う。でもIncorrectだった。グラフ問題。最大フローとかで何とかなるような気がするんだけどどう解いたらよいか
• Contest Analysis読んだ。二部グラフの最大マッチングに落とせるので確かに最大フロー。
• すぱげってぃこーどからコピペしたmaximumFlowだと思った結果が出ない。確認のために自分で書いてみる（というか1年半前の自分からコピペ）

#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cctype>
using namespace std;

#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)

#define infty 987654321
int maximumFlow(const vector<vector<int> >& capacity, int s, int t) {
  int w = capacity.size();
  // residual networks
  vector<vector<int> > resid(w, vector<int>(w,0));
  for(int j=0; j<w-1; ++j){
    for(int k=j+1; k<w; ++k){
      resid[j][k] = capacity[j][k]; // = capacity[j][k] - flow[j][k]
      resid[k][j] = 0; // = flow[k][j]
    }
  }
  // find another way
  for (int total=0; ;++total) {
    bool another_way = false;
    vector<int> prev(w, infty);
    queue<pair<int,int> > q; q.push(pair<int,int>(s,-1));
    while (!q.empty()) {
      pair<int,int> p = q.front();
      int node = p.first, prev_node = p.second;
      q.pop();
      prev[node] = prev_node;
      if (node==t) { another_way = true; break; }
      rep(i,w) {
        if (resid[node][i] == 0) continue;
        if (prev[i] < infty) continue;
        q.push(pair<int,int>(i,node));
      }
    }
    // no more ways
    if (!another_way) return total;
    for (int node=t; node!=s; node=prev[node]) {
      int prev_node = prev[node];
      resid[prev_node][node]--;
      resid[node][prev_node]++;
    }
  }
  return 0;
}

int main(){
  int T; cin >> T;
  rep(t,T){
    int n, k; cin >> n >> k; // 1..100, 2..25
    vector<vector<int> > price(n,vector<int>(k));
    rep(j,n) rep(i,k) cin >> price[j][i]; //0..1e6
    vector<vector<bool> > dir(n,vector<bool>(n,false));

    int w=1+n+n+1;
    vector<vector<int> > capacity(w, vector<int>(w,0));
    rep(i,n) capacity[0][1+i] = 1;
    rep(i,n) {
      rep(j,n) {
        if (i==j) continue;
        bool x=true;
        rep(h,k) if (price[i][h] >= price[j][h]) { x=false; break; }
        if (x) capacity[1+i][1+n+j] = 1;
      }
    }
    rep(i,n) capacity[1+n+i][1+n+n] = 1;
    
    int maxflow = maximumFlow(capacity, 0, 1+n+n);
    int ans = n - maxflow;
    printf("Case #%d: %d\n", 1+t, ans);
  }
  return 0;
}

D. Watering Plants

• smallは簡単に解ける。問題はlarge
• あとで見る

UAPC 2010

00:03 |

http://rose.u-aizu.ac.jp/onlinejudge/cvolume.jsp?contestID=UAPC2010

途中から参戦。

• Aを解いて、Bで躓いて、Cの問題が理解できなくて、諦めて食事して、戻ってDを解いて、Gを解くのにサイコロを作って、提出しようと思ったらもう試合終了していた
• へぇー問題英語なんだーと思って頑張って読んでたけど、日本語で読めることに翌日気づいた
• というわけで風船２個＞＜

続きを読む

Member SRM 471 Hard(1000): ConstructPolyline

SRM, 過去問 | 12:53 |

• たまにはDiv1 Hard問題も眺めてみないとSTL使いこなし以上の実力がつかないと思いHard問題を開いてみる

続きを読む

Member SRM471

01:57 |

500解いてて気がついたら接続が切れてた。再ログインしたらSRM471が消えていた。ノーゲームか。

折角250と500は解いたので、書いたコードは晒しておこう。どちらも解き方はすぐに思いついたが実装がさらっと行かずデバッグに時間を取られた。

続きを読む

Member SRM471 Medium(500): ThirteenHard (再考)

SRM, 過去問 | 12:43 |

（最初に書いたコードはこちら: https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20100527/1274893027 ）

• (N-1)番目に到達すると分かっている（最短かは分からない）時刻があるなら、それ以降の時刻については検証無意味。
  • priority_queueを使ったほうがスマートかな。
• int[25][2^13]である駅までの最短時間が分かったとしても、その後でmod13死にするかもしれないのでmod13が違うやつは生かしておくべき。最短との比較枝切りをやめると最悪ケースでTLE。
  • やっぱりint[25][13][2^13]でないと駄目。
• それから

    ...
    bool boo = false;
    if (sm>0) {
      for(int k=0,p=1; k<13; k++,p<<=1){
        if (msk & p) {
          if (((sm + 13) - k) % 13 == 0) { boo=true; break; }
        }
      }
    }
    if (boo) continue;
    ...

ここは

    if (msk & (1 << (sm % 13))) continue;

と等価ではないか！

勿論、C/C++の演算子の優先順位に従えば括弧は省略できて

    if (msk & 1 << sm % 13) continue;

と書けるが直感的にこれが(msk&1)<<(sm%13)などに見えてしまって怖くてたまらない。

• てな感じで書き直したのがこれ:

続きを読む

TCO2010 Qualification Round 3

TCO2010 | 10:57 |

• みんなQR2までで通っちゃってるみたいで寂しいQR3
• 難易度は普段のDiv2程度？妙に易しく感じられた
• ３問全部submitできたのってDiv1・Div2通して初めてだ
• 一瞬全体の20番台だった！コンテスト中なので通るかはまだ不明…お願い600以内に残って
• →500が恥ずかしいミスで落ちて111位。とりあえず予選通過。そしてとりあえず黄色に戻れた

教訓：

配列は端をちゃんと見る

• レーヴェンシュタイン距離5未満のミスで落ちた場合は何かペナルティを課すことにしよう…

続きを読む