2010-06-19

TCO Round1

TopCoder

すぐ寝ようかと思ったけど，惜しかったからｲﾗｲﾗっとしてねれないので更新．

250 EqualizeStrings

二つの文字列を同じにする．各文字を1文字進める/戻るコスト(a -> b, a -> z)は1．最小コストでおなじになる文字列を求めよ．複数ある場合は辞書順最初のを．

とりあえず文字の小さい方に適当に合わせてみよう．
- tとgの場合真ん中のaにした方がいいのか…
- tとgの真ん中あたりってどう求めよう．偶奇で分ける？う〜ん…
- a-z全部やってみるか．a - > zに変換するときに25とかにしないように気をつけよう．
- サンプル通った．出そう．

500 TwoRegisters

レジスタにX=1,Y=1が入っている．可能なオペレーションは X=X+Y,Y=X+Yのみ．命令数最小ででRにする命令列を求めよ．複数ある(ry

後半加速しませんかね．X=1,Y=1からキャッシュmap[1000000][1000000]でやってみるか．
- 余裕のTLE
適当にノートに書いて考える．
発想を逆転させるのよ，ナルホドくん！
逆にやってみよう．X=R,Y=1..RをX=1，Y=1に戻すって考え方で．
- 仮にひとつずつ減っていって，R * R / 2ぐらいかなぁ…間に合わなそうだけどやってみよう．
- 500000ぐらいまでなら答えが出そう．
- チューニングすれば通るか？どこ速くなるかな…
- 文字列処理が明らかに遅いけど，早くする方法が上手く思い浮かばない…
- あれ，gcd(R,i) != 1のときって(1,1)にならなくない？
- xの倍数どおしの差はxの倍数だろう．これで刈れる？
- 1000000が通った！これで勝つる！

チャレンジフェイズ

500落ちてると仮定すると，ギリギリ通ってない程度．
- 自分がやったような間違いをしているソースが，勇気を出せ…

出せませんでした．誰かに落とされてました．自分と同じ間違いは他の人のを落とすチャンスなので，とても大事．点数的には落としに行くのが最適戦略だよなぁ．

結果

500はTLEで通らないケースが有った．あとで人のソース見て，文字列を生成しない方法にしたら通った．string(x,'X')みたいの大杉…

今回は十分考えられて，十分手を動かすことができたのでよく戦えた．今回の感想．

とりあえず手を動かす
- コード書くにしても，ノートに書くにしても．
逆転裁判
- 結論から考えたりしてみる．

次にいけたなぁ．(´・ω・`)

2010-05-23

GCJ Round1A-Cを振り返っておく

凡ミス

Round1落ちしてしまった…全体を振り返るに，しょんぼりなミスがいつも以上に多かったと思う．
やはりあの呪いか．

ミスを繰り返さないように，メモっておこう．

Round1A

なんかGCJがお祭りな感じだなーとか思いながら，今回通れないと次回でるの大変だなーとか思いながら参加．

A. Rotates

やるだけ，なんだけど，回転と幅詰めに手間取った．
前も手間取って，意外とでるからライブラリ入りしとこうかな．特にミスなし．

B. Make it Smooth

DPなのはすぐにわかるけど，上手く考えられない．small通そうとしたけど，なんか場合分けができない．
場合分けじゃなくて再帰全探索が良かった．これにこだわったのがこのラウンドの１番の失敗．

C. Number Game

本番中ろくに読まなかった．イクナイ．読んでみたら，smallはmapとかでキャッシュつければ通りそうってことはわかった．

結果

Aのみで1000ちょっと．全体としては戦略的ミスだった．一回目だしいいかっていう油断もあった．
でも全部とけなきゃ．

Round1B

一日二回か．しんどい．って思いながら参加．本番前に呪いのキーワードを吐いてしまった．これが転落の始まりだったのだろうか．

A. File Fix-It

やるだけ．日本人最速だったらしい．っていうのを聞いて，考え方が守りに入った．small通せばいっかなって．

B. Picking Up Chicks

とりあえずsmallを通そうとして，queueでも使ってswap全部試そうと思った．が，答え合わない…
本番後検証したら，queue中のbreakに何故かswapがK回超えたらやめるになってた．Kは最低限の鶏の数だよ…
ひどい凡ミス
途中皆結構点数あげてて，これはlarge通さないと勝てないと思って方針を変えた(たぶん遅かったけど)．
冷静に考えると，largeも貪欲にやっていけばいけそうってすぐ気づいた．けど，なんでか通らない．
本番後に少し条件が抜けてたことが発覚．2,3行足りなかった．

C. Your Rank is Pure

読めない！ていうか素数の話なに？？

本番後に説明聞いたら，とりあえずDPはすぐわかって，理解できたらとけてたかなーと思う．
ググル様は英語できない人に用ないんだなぁ．

結果

1700ぐらい．Bを冷静に通したかった．もしくは読みたかった．

Round1B

A. Rope Intranet

やるだけ．簡単すぎてなんども確認して1分ほどロスした．

B. Load Testing

読めないんですよ．まだ読めてない．皆結構解いてたので，簡単なんだろうなーと思って1時間以上読んだけどよくわからなかった．ゲシュタルト崩壊した．
数字の大きさから，なんとなーくBinary SearchでLargeをとくのかなーって思った．そうだったらしい．読めない．

[追記]バイナリサーチと言うかアドホック．意味を教えてもらって，最初トップダウンに考えていてイミフだったけど，ボトムアップに考えたらすぐわかった．でも，説明を日本語で聞いてもなかなか理解できなかったから本番中は無理ぽ．

C. Making Chess Boards

Bが読めないので，とりあえずCに来た．Cを読んだらLargeは知らないけどsmallはやるだけっぽかったのでガリガリ書き始める．
30分程でだいたいかけて，40分ぐらいで提出．small合わない…
本番後に少し条件が抜けていたことがわかった．数行訂正すれば直ってた．気づきにくいといえば気づきにくい．

結果

1300ぐらい．英語が読めなかったことと，Cでミスに気づかなかったのが原因かな．
でもCをn^5で出してたかというと怪しい．その根性はなかったなァ…通るなんて．

総括

今回は凡ミスと言うか条件抜けメインの英語ムズイだった．これはこれでちょっと珍しいのでやっぱりあの呪(うわなにをするやめ
自分は英文読むのは苦手ではないけど，数学的？な話になると苦手になる(今回はfactor)．これは慣れが足りないと思うので，
gcjの過去問でも読んでなれよう．

条件のデバッグは結構本質的なので気づきにくい．今回はコードはしっかり書けている自信があったので，やはりifの中とかをしっかり
考えなきゃ気付かなかったと思う．普段でいう凡ミスとはまたちょっと違う感じで．

Round2に進んだ方はTシャツを見せてください！

2010-05-07

謎

PKU

PKU 2671なんだけど，while (1);を書くかどうかでACがWAになる．
ダイクストラで解いたのだけど，擬似コードはこんな感じ．

int bfs(){
   while (!q.empty()){

   }
   while (1); // これを消すとWA
}
int main(){
   ...
   ...
   cout << bfs() << endl;
}

なんぞこれ？

実際のコード

#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;

int distsum[300][300];
int costsum[300][300];
int dist[300];
int cost[300];
int totaldist,totalcost;
int dp[300][300][2];
int N;
#define RIGHT 1
#define LEFT 0
struct State{
  int left,right,which;
  int cost;
  bool operator<(const State& s)const{
    return cost > s.cost;
  }
};
int bfs(){
  priority_queue<State> up;
  up.push((State){0,0,0,0});
  up.push((State){0,0,1,0});
  while (!up.empty()){
    State st = up.top();
    up.pop();
    int l = st.left;
    int r = st.right;
    int c = st.cost;
    int w = st.which;
    //cout << l << " " << r << " " << c << " " << w << endl;
    if (c > dp[l][r][w]) continue;
    if ((r+1)%N==l) return c;
    
    int nl = (l + N - 1) % N;
    int nr = (r + 1) % N;
    int nc,nw;
    if (w == RIGHT){
      
      nc = c + (totalcost - costsum[l][r])*distsum[nl][r];
      nw = LEFT;
      if (dp[nl][r][nw] > nc){
        up.push((State){nl,r,nw,nc});
        dp[nl][r][nw] = nc;
      }
      
      nc = c + (totalcost - costsum[l][r])*distsum[r][nr];
      nw = RIGHT;
      if (dp[l][nr][nw] > nc){
        up.push((State){l,nr,nw,nc});
        dp[l][nr][nw] = nc;
      }
      
    }else{ // from LEFT

      nc = c + (totalcost - costsum[l][r])*distsum[nl][l];
      nw = LEFT;
      if (dp[nl][r][nw] > nc){
        up.push((State){nl,r,nw,nc});
        dp[nl][r][nw] = nc;
      }
      
      nc = c + (totalcost - costsum[l][r])*distsum[l][nr];
      nw = RIGHT;
      if (dp[l][nr][nw] > nc){
        up.push((State){l,nr,nw,nc});
        dp[l][nr][nw] = nc;
      }
      
    }
  }
  while (1); // これを消すとWA
}
int main(){
  while (1){
    scanf("%d",&N);
    if (!N) break;
    totaldist = 0;
    totalcost = 0;
    for (int i=0;i<N;i++){
      scanf("%d%d",&cost[i],&dist[i]);
      totalcost += cost[i];
      totaldist += dist[i];
    }
    
    for (int i=0;i<N;i++)
      for (int j=0;j<N;j++)
        for (int k=0;k<2;k++)
          dp[i][j][k] = 1 << 30;
    
    for (int i=0;i<N;i++){
      int dsum=0,csum=0;
      for (int j=i;;j++){
        j %= N;
        csum += cost[j];
        costsum[i][j] = csum;
        distsum[i][j] = dsum;
        dsum += dist[j];
        if ((j+1)%N==i) break;
      }
    }
    cout << bfs() << endl;
  }
}

なんぞこれ？

追記

intの関数が値を返した方がいいというのはまさにそのとおりでございます．
でもwhile(1)

2010-05-04

SRM469

topcoder 凡ミス

すごい久しぶりに更新．５月病．
なんかやらなきゃいけないことをやってない気がして……

250 TheMoviesLevelOneDivOne

long long を掛け算につけなかった＼(^o^)／

500 TheMoviesLevelTwoDivOne

N=20の時点で1 << 20を考えて，TSPっぽいなーって思った．
とりあえず深さ優先で解いて，それにキャッシュをつけようとしたけど
なんだかバグが抜けなくて落ちるの確定だけど出してしまった．
僕の点数をだれかが喜んでいるはず……！！
そんなに難しくないと思うんだけどなァ．

プラクティスでといたけど，キャッシュを上手く使ってなくて一度TLEになった．

結果

1204ｗDiv2転落リーチ．次回からdiv2に上がりたい(ryになるかも．

最近やるきがでなくてサボっているのが良くない．人生に対して凡ミスをしている気がする．

2010-04-23

Emacs23 on Windows のフォント設定

EmacsLisp

Windowsのemacs23.1で好きなフォントにする方法．調べたら EmacsWikiに書いてあったので，日本語で説明．

emacsを起動してスクラッチバッファを開く．( C-x b *scratch* )
(w32-select-font)と入力して，行末(')'の右)でC-j
フォントを選択する窓が開くので，使いたいフォントを選んでOK
バッファに次のようにフォント名が挿入される

(w32-select-font)
#("ＭＳ Ｐ明朝-12" 0 9 (charset cp932-2-byte))

.emacsを開いて次のように入力する．ダブルクォーテーション内は(w32-select-font)で取得したフォントを指定する．

(set-face-font 'default "ＭＳ Ｐ明朝-12")

emacsを再起動する

2010-04-19

3140 Contestants Division

PKU

この問題は読むのが難しかった＞＜

the organizing committee can only afford to set the system up such that 
there will be only one way to transfer information from one university to another
without passing the same university twice

この一文はグラフが木であることを意味しているらしい．

without passing the same university twiceの部分は，行ったり来たりしないでってこと，

only one way はpassが一通りしかないよってこと．

点から点の移動に，同じ点を二回通らないパスが一通りしかないことは木の必要十分条件ということだ．

で，この問題は，重みのある木の辺を，どこできると二つの木は近い重さになるかって問題で，まあ再帰とかでとけばいいと思います．

さくっと読める上海の方がすごいお(´・ω・`)

2010-04-11

Codeforces Beta Round #9

Codeforces 凡ミス

凡ミスタグを付けなくてすむその日まで頑張る.

A Die Roll

(^p^)

B Running Student

sqrtの中身にintの範囲を超えるものを渡してて,それに気付かなかった(^p^)前にもsqrtの中身が負でバグってたことがあった。はぁ…

引数がおかしくなるケースがあるか考えよう

あとintの範囲は2^31^1 == 2147483647 だいたい 2 * 10^9.今回は(10^5)^2でint超えてた

C Hexadecimal's Numbers

10進数で0と1だけで構成できる,ある数を超えない数はいくつ？

1から*10 + 1、*10 を再帰的に数えた.

D How many trees?

ノード数N,高さがH以上の2分木は何通り構成できる？

木の性質かなぁ…ググル
大した情報ないので考える.
あるノードの左,右につけるものを考えるとき,自分より大きい数字がいくつ,小さい数字がいくつって情報だけでいいよな
じゃあこれに今の高さの情報を付け加えて再帰かな
高さがH以上になるには,あるノードの左の木が高さH以上じゃなくても右の木がH以上ならいいから…
返り値に最大の高さと構成数が必要？pair？？
って考えててこんがらかって終了
無条件の構成方法から,高さがH未満の構成方法を引くって方針に切り替えたらすんなり書けた

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
#include <complex>
#include <set>
#include <vector>
#include <bitset>

#define REP(i,N)for(int i=0;i<(int)N;i++)
#define MP(a,b) make_pair(a,b)
using namespace std;

int nextInt(){
  int ret=0,sign=1;
  char c=' ';
  while (!isdigit(c=getchar())){
    if (c==EOF) return -1;
    if (c=='-') sign=-1;
  }
  do{
    ret=ret*10+(c-'0');
  }while (isdigit(c=getchar()));
  return ret*sign;
}
void printlineInt(int num){
  char str[101];
  if (num<0) num=-num,putchar('-');
  else if (num==0) {puts("0");return;}
  str[100]='\0';
  int i=99;
  for (;num;i--){
    str[i]=num%10+'0';
    num/=10;
  }
  puts(&str[i+1]);
  return;
}
//template end
int N,H;
long long dp[36][36][36];
long long dp2[36][36][36]; 

long long rec(int l,int u,int h){
  if (dp[l][u][h] != -1LL) return dp[l][u][h];
  //cout << h << " " << H << endl;
  if (h >= H) return dp[l][u][h] = 0;
  if (l == 0 && u == 0){
    return dp[l][u][h] = 1LL;
  }
  long long r1=0,r2=0;
  REP(i,l){
    r1 += rec(i,l-i-1,h+1);
  }
  if (!l) r1 = 1;
  REP(i,u){
    r2 += rec(i,u-i-1,h+1);
  }
  if (!u) r2 = 1;
  //cout << l << " " << u << " " << h << " " << r1 * r2 << endl;
  return dp[l][u][h] = r1 * r2;
}
long long rec2(int l,int u,int h){
  if (dp2[l][u][h] != -1LL) return dp2[l][u][h];
  if (l == 0 && u == 0){
    return dp2[l][u][h] = 1LL;
  }
  long long r1=0,r2=0;
  REP(i,l){
    r1 += rec2(i,l-i-1,h+1);
  }
  if (!l) r1 = 1;
  REP(i,u){
    r2 += rec2(i,u-i-1,h+1);
  }
  if (!u) r2 = 1;
  //cout << l << " " << u << " " << h << " " << r1 * r2 << endl;
  return dp2[l][u][h] = r1 * r2;
}

int main(){
  N=nextInt(),H=nextInt();
  REP(i,36) REP(j,36) REP(k,36) dp[i][j][k] = -1LL;
  REP(i,36) REP(j,36) REP(k,36) dp2[i][j][k] = -1LL;
  long long ans=0;
  REP(i,N){
    ans += rec2(i,N-i-1,1) - rec(i,N-i-1,1);
  }
  cout << ans << endl;
}

(^p^)