Hatena::Grouptopcoder

hirosegolf@競技プログラミング

2012-04-04

SRM469Div1練習

| 22:18

250: 211.25

500: 232.12

1000: Opened

1000の問題文を読んでる途中で実は凄い眠いことに気がついた。やはり500を解くのが遅い。

2012-03-29

SRM470Div1練習

| 14:25

250: 134.64

500: 264.47

1000: Opened

250に時間がかかりすぎた。複数の方針があるので、それで迷ったのも良くなかった。迷わずbit dp一本でやるべきだった。500、もうすこし早く解きたいけど、こればっかりは慣れないことには仕方ないかな。

2012-03-17

SRM476Div1練習

| 13:31

250: 180.57

550: Opened

1000: Opened

久しぶりにSRMがあるので、感覚を取り戻すためにも練習。SRM250は、for(int v=n;v--;v>=0)というミスをして、再提出した。

550は、36人もいたら無理じゃない?とおもってた。

1000は問題文よく分からなさ過ぎて、諦めた。

550のEditorial見てみた。「友達最大15人?36人だろ。15とかどこから出てきた?」とか思ったら、between 1 and 36 "characters"に気づいて衝撃を受けた。こんなのありかよ。今までに無いパターンの罠だった。

2012-02-10

SRM479Div1練習

22:35

250: 182.74

500: Opened

1000: Opened

問題文を読むのがとにかく大変だった。easyを解くのに15分、HARDの問題文を読むのに15分で、それだけでhardを考える時間が殆ど無くなってしまう。500を読むのにも時間がかかって、駄目な感じだった。長文対策を何か考えたほうがいいかもしれない。長文の問題のときは、取り組む問題数が多いとそれだけ不利なので、Mediumを開いて長文だった場合は、最後までhardに取り組むことにするとか。

SRM480Div1練習

| 12:09

0点

あまりにも駄目すぎたので途中でやめた。EASYの実装量が多すぎて死んだ。今まではEasyだけは解くつもりだったけど、大変な実装問題のときは今度からはEasyは飛ばすことにする。

追記:Easyの実装で苦労した原因は変数名が明快でない割りに長すぎたのも原因にありそう。いい変数名が思いつかないときは一文字か二文字ぐらいの短い変数名を選ぶべき。Easyが落ちた原因は、continueと書くべき場所でbreakと書いてしまったことだった。

この手のミスは前にもあったのでなんらかの対策を採るべき。一番着実なのはsubmitしてから、見直すことだろうか。continueをbreakと書くミスは、pretestを通りやすいので気をつける。

参加環境メモ

10:13

色々メモ。

準備してあるライブラリ

Ahocorasick

extgcd, modの計算。行列の計算。

最大流、RMQ

SRMで今とっている戦略

Easy解く。

HARD開く。残り時間30~45分ぐらいまで粘って解けそうなら解く。

将来的にはHARD->Medium->Easyの順番に切り替える予定。

Medium、HARDを解くときはConstrainとサンプルを必ず慎重にチェックすることにしている。

問題文誤解は致命傷になりうると考えて。

デバッグの手間も考えて、配列はメモ化再帰のときぐらいしか使っていない。

殆どvectorですませているが、稀に実行時間がネック。

Codeforcesの時間配分は適当。

EditorはSciTEを使用。F5キーでコンパイル+実行。

スクリプトを書いてコーディング環境の改善をしたいが、面倒でまだ。

メモ化再帰は、コードを自動生成するためのjavascriptコードを使用。

dpはずっとメモ化再帰にこだわって書いていたが、あまりこだわらないようにする。

SRM Codeprocessorテンプレ

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <assert.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())

// BEGIN CUT HERE
#define clr(a) memset((a),0,sizeof(a))
#define nclr(a) memset((a),-1,sizeof(a))
#define pb push_back
#define INRANGE(x,s,e) ((s)<=(x) && (x)<(e))
// END CUT HERE


using namespace std;

// BEGIN CUT HERE
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define deb(x) cerr << #x << " = " << (x) << " , ";
#define debl cerr << " (L" << __LINE__ << ")"<< endl;
template<typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& z){
os << "[ ";REP(i,z.size())os << z[i] << ", " ;return ( os << "]" << endl);}
template<typename T> std::ostream& operator<<(std::ostream& os, const set<T>& z){
os << "set( "; EACH(p,z)os << (*p) << ", " ;return ( os << ")" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const map<T,U>& z){
os << "{ "; EACH(p,z)os << (p->first) << ": " << (p->second) << ", " ;return ( os << "}" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const pair<T,U>& z){
return ( os << "(" << z.first << ", " << z.second << ",)" );}
// END CUT HERE

// BEGIN CUT HERE
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
// END CUT HERE

class $CLASSNAME$ {
public:
  $RC$ $METHODNAME$($METHODPARMS$) {
    $RC$ ans;

    return ans;
  }

  $TESTCODE$
};

// BEGIN CUT HERE
int main() {
  $CLASSNAME$ ___test;
  ___test.run_test(-1);
}
// END CUT HERE

2012-02-09

SRM428Div1練習

| 22:14

250: 237.78

500: UnOpened

1000: Opened

buttomcoderで参加。

1000で計算量を吟味することなく、多分間に合うだろうと飛び込んだのはまずかった。結局解くのに非常に時間がかかってしまった。