naoya_t@topcoder

SRM473 Div1 Medium(500): RightTriangle

14:33 |

• に該当する場所が空いていない時の処理が最悪ケースでTLE
• の場所をインクリメントしておいて、あとで均せば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 |

リハビリ

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

続きを読む

DIV	level	問題名	競技中	後で	System Test	通過率	備考	levenshtein
1	250	SequenceOfCommands	o	-	passed (233.65)	-	_	0
1	500	RightTriangle	撃沈	-	-	-	_	?
1	1000	RooksParty	撃沈	-	-	-	_	?

GCJ 2010 Round 2 : A. Elegant Diamond

13:19 |

教訓

・問題はよく嫁

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

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

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

続きを読む

GCJ 2010 Round 2 : B. World Cup 2010

14:57 |

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

教訓

もちつけ

続きを読む

GCJ 2010 Round 2 : C. Bacteria

16:34 |

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

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

続きを読む

GCJ 2010 Round 2 : D. Grazing Google Goats

12:32 |

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

教訓

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

続きを読む

SRM472 Div1 Easy(250): PotatoGame

過去問, 初心者記事 | 17:20 |

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

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

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

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

続きを読む

SRM472

10:35 |

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

TaroとかHanakoとか＞＜

続きを読む

DIV	level	問題名	競技中	後で	System Test	通過率	備考	levenshtein
1	250	PotatoGame	撃沈	-	-	-	_	0
1	500	TwoSidedCards	間に合わず	-	-	-	_	0
1	1000	開いてない	-	-	-	-	_	-

Google Code Jam 2010 Round 2

10:38 |

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

（あとで書く）

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

20:07 |

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

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

UAPC 2010 I. Mysterious Onslaught (みょんみょん問題) - サンプルは通るけどTLEが出る駄目コード

UAPC | 17:26 |

• とりあえず貼っとく

続きを読む