Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-06-18

SRM473 Div1 Medium(500): RightTriangle

14:33 | SRM473 Div1 Medium(500): RightTriangle - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM473 Div1 Medium(500): RightTriangle - naoya_t@topcoder SRM473 Div1 Medium(500): RightTriangle - naoya_t@topcoder のブックマークコメント

  • an^2+bn+cに該当する場所が空いていない時の処理が最悪ケースでTLE
  • an^2+bn+cの場所をインクリメントしておいて、あとで均せばO(points+places)で行けるじゃん
  • それだけ。passed system test
typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef long long ll;

class RightTriangle {
 public:
  long long triangleCount(int places, int points, int a, int b, int c) {
    if(places & 1) return 0LL;

    vector<int> cnt(places,0);
    for(ll n=0; n<points; ++n) {
      ll ix = n*n*a + n*b + c;
      cnt[ix % places]++;
    }

    int r=0;
    rep(ix,places*2){
      int j=ix%places;
      cnt[j]+=r;
      r=max(cnt[j]-1,0);
      cnt[j]=min(1,cnt[j]);
    }
    
    vector<int> acc(places*2+1,0);
    acc[0]=0;
    rep(n,places) acc[n+1]=acc[n]+cnt[n];
    int ap=acc[places];
    rep(n,places+1) acc[places+n]=ap+acc[n];
    
    ll accum=0LL;
    int h=places/2;
    rep(n,places){
      int nh = (n + h) % places;
      if(cnt[n] && cnt[nh]) {
        accum += acc[n+h] - acc[n+1];
      }
    }
    return accum;
  }
};

SRM473

11:56 | SRM473 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM473 - naoya_t@topcoder SRM473 - naoya_t@topcoder のブックマークコメント

リハビリ

Div1では初めての3問submit →oxx

続きを読む

DIVlevel問題名競技中後でSystem Test通過率備考levenshtein
1 250 SequenceOfCommands o - passed (233.65) - _ 0
1 500 RightTriangle 撃沈 - - - _ ?
1 1000 RooksParty 撃沈 - - - _ ?
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100618

2010-06-07

GCJ 2010 Round 2 : A. Elegant Diamond

13:19 | GCJ 2010 Round 2 : A. Elegant Diamond - naoya_t@topcoder を含むブックマーク はてなブックマーク - GCJ 2010 Round 2 : A. Elegant Diamond - naoya_t@topcoder GCJ 2010 Round 2 : A. Elegant Diamond - naoya_t@topcoder のブックマークコメント

教訓

・問題はよく嫁

・処理しやすい座標系を考える

・斜め移動は(自分の場合)バグりやすいのでご用心

サンプルは通るけどA-smallでIncorrect、なコード

続きを読む

GCJ 2010 Round 2 : B. World Cup 2010

14:57 | GCJ 2010 Round 2 : B. World Cup 2010 - naoya_t@topcoder を含むブックマーク はてなブックマーク - GCJ 2010 Round 2 : B. World Cup 2010 - naoya_t@topcoder GCJ 2010 Round 2 : B. World Cup 2010 - naoya_t@topcoder のブックマークコメント

後回しにしてたBが簡単すぎて泣きそう

教訓

もちつけ

続きを読む

GCJ 2010 Round 2 : C. Bacteria

16:34 | GCJ 2010 Round 2 : C. Bacteria - naoya_t@topcoder を含むブックマーク はてなブックマーク - GCJ 2010 Round 2 : C. Bacteria - naoya_t@topcoder GCJ 2010 Round 2 : C. Bacteria - naoya_t@topcoder のブックマークコメント

smallは簡単なシミュレーションで解ける。

  • B small/large + C smallだけ1時間36分以内に解ければ通っていた件。いまの自分に必要なのは落ち着くことと問題の捨て方
  • 続きを読む

GCJ 2010 Round 2 : D. Grazing Google Goats

12:32 | GCJ 2010 Round 2 : D. Grazing Google Goats - naoya_t@topcoder を含むブックマーク はてなブックマーク - GCJ 2010 Round 2 : D. Grazing Google Goats - naoya_t@topcoder GCJ 2010 Round 2 : D. Grazing Google Goats - naoya_t@topcoder のブックマークコメント

長らくハマってしまい敗退の原因となった問題D。 比較的容易と思って飛びついたD-smallでしたが、結果が合わないのは精度の問題でした。long doubleで解決するような話。

教訓

浮動小数点数の精度とかたまには考えたほうがいいよ。long doubleかわいいよlong double

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100607

2010-06-06

SRM472 Div1 Easy(250): PotatoGame

| 17:20 | SRM472 Div1 Easy(250): PotatoGame - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM472 Div1 Easy(250): PotatoGame - naoya_t@topcoder SRM472 Div1 Easy(250): PotatoGame - naoya_t@topcoder のブックマークコメント

Nimとかこういう石取り・芋喰い系ゲームが苦手…

  • 普通だったらDPで解くような問題なのだが
    • 今回は1e9までなので、DPしてたら間に合わない(ローカルマシンで60秒超)。パターンを見つけて数式を書くだけ
  • 大抵、両者が最適手を打つ、というのをすごく難しく考えてしまって破滅する
  • 落ち着いて順序を追って考えたらある重要かつ初歩的な事実に気がついた

芋数がNのとき、それは先手必勝か後手必勝かのどちらかしかない

次回、眠くても目を瞑ってても解けるようにメモしておく。恥ずかしい記事なのでDiv1の人は見ないようにw

続きを読む

SRM472

10:35 | SRM472 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM472 - naoya_t@topcoder SRM472 - naoya_t@topcoder のブックマークコメント

二時間半のGCJ Round 2の後で疲れてて眠いのに参戦。

TaroとかHanakoとか><

続きを読む

DIVlevel問題名競技中後でSystem Test通過率備考levenshtein
1 250 PotatoGame 撃沈 - - - _ 0
1 500 TwoSidedCards 間に合わず - - - _ 0
1 1000 開いてない - - - - _ -
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100606

2010-06-05

Google Code Jam 2010 Round 2

10:38 | Google Code Jam 2010 Round 2 - naoya_t@topcoder を含むブックマーク はてなブックマーク - Google Code Jam 2010 Round 2 - naoya_t@topcoder Google Code Jam 2010 Round 2 - naoya_t@topcoder のブックマークコメント

  • 問題全部読んで
  • どれか1完したいと思って
  • Dにはまって
  • 死にました

(あとで書く)

PKU関連のメモはPKU Judge Online部に

20:07 | PKU関連のメモはPKU Judge Online部に - naoya_t@topcoder を含むブックマーク はてなブックマーク - PKU関連のメモはPKU Judge Online部に - naoya_t@topcoder PKU関連のメモはPKU Judge Online部に - naoya_t@topcoder のブックマークコメント

SRMと流量が違いすぎるので、PKU部を作ってそちらに移動しました。

http://pku.g.hatena.ne.jp/n4_t/

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100605

2010-06-04

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100604

2010-06-03

Codeforces Beta Round #17 (Div.2)

22:17 | Codeforces Beta Round #17 (Div.2) - naoya_t@topcoder を含むブックマーク はてなブックマーク - Codeforces Beta Round #17 (Div.2) - naoya_t@topcoder Codeforces Beta Round #17 (Div.2) - naoya_t@topcoder のブックマークコメント

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

Google Code Jam 2009: Round 2

| 19:38 | Google Code Jam 2009: Round 2 - naoya_t@topcoder を含むブックマーク はてなブックマーク - Google Code Jam 2009: Round 2 - naoya_t@topcoder Google Code Jam 2009: Round 2 - naoya_t@topcoder のブックマークコメント

  • 去年の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
  • あとで見る
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100603