Hatena::Grouptopcoder

どせいふんとうき。 RSSフィード

2013/04/02

Round #177

| 04:19 | はてなブックマーク - Round #177 - どせいふんとうき。

成績は o-o-- で 807 位でした.レーティングは 1511 -> 1449 に変動しました.前回せっかくランクアップしたのですが早々に Specialist へと逆戻りです.


A. Polo the Penguin and Segments: 484

しばらく問題の意味がわからずぽけーっとしていました.計算するだけでした.

B. Polo the Penguin and Matrix: ---

3分探索で解ける!とひらめいたところまでは良かったのですが時間内にきちんと実装できず……くやしいです.

C. Polo the Penguin and Strings: 1092

最初は abab... を繰り返しておいて最後に cdef... と登っていけば解けるかな?と思ったら本当に解けました.キッタナイ場合分けをしました.

D. Polo the Penguin and Houses: ---

終了後に「1..k の部分は 1 を根とする全域木に一本足せば良いのでは?」とひらめきました.頂点の数が k の最小全域木の数は k^(k-2) だそうなので,その通りに実装したら Accepted をもらいました.

E. Polo the Penguin and XOR operation: ---

まだ読んでないです.


成績は悪かったですがコンテスト終了後わりと早い段階で解けなかった B, D 問題が解けたのはよかったです.次回以降のコンテストに活かしていきたいです.

April Fools Day Contest 2013

| 04:07 | はてなブックマーク - April Fools Day Contest 2013  - どせいふんとうき。

せっかくなので参加しました.ちゃっかり 411 位をゲットしました.


A. Mysterious strings: Accepted

Google 先生に相談→あとはタイピング.

B. QR code: Accepted

あー. QR コード読み込んだら目的のデータファイルダウンロードできるとか気づかなかったわー.気づかなかったわー.(´;ω;`)

C. WTF?: Accepted

ネットスラングなんでしょうか.

D. Orange: Accepted

イラストを見ながらコードに落とすだけ.

E. HQ: ---

アライグマさんがきらいになる問題.

F. Greedy Petya: ---

問題を読んで速攻であきらめました.まさかコンテスト中に解けた人がいたなんて…….

2013/03/26

SRM 574

| 06:32 | はてなブックマーク - SRM 574 - どせいふんとうき。

撃沈回. 250, 500 点問題を提出してどちらもシステムテストで落ちました.というわけで問題の点数は 0 点.しかし 500 点問題でこれはひっかかりそう!という部分がわかったので 3 つほど撃墜しました.というわけで総合スコアは 150 点.レーティングは 1134 -> 1024 とがっくり落ちました.

CityMap: Failed System Test

解き方はすぐに思いついたのですが,サンプルテストで理解できないエラーを連発しました.結局,そのまま提出して,案の定システムテストで蹴られました.コンテスト終了後にコードを眺めていたら原因がわかりました.アホなミスをしたなぁと反省しています.

class CityMap {
  public:
  string getLegend(vector <string> cityMap, vector <int> POIs) {
    vector<int> counts(27,0);
    string s("");
    int H = cityMap.size();
    int W = cityMap[0].size();
    for (int h=0; h<H; ++h) {
      for (int w=0; w<W; ++w) {
        if (cityMap[h][w]=='.') continue;
           // ↑の行を忘れていたせいで死んでいました……
        counts[cityMap[h][w]-'A']++;
      }
    }
    int N = POIs.size();
    vector<int>::iterator cit = counts.begin();
    for (int n=0; n<N; ++n) {
      cit = find(counts.begin(),counts.end(),POIs[n]);
      s += (cit-counts.begin())+'A';
    }
    return s;
  }
};

TheNumberGameDiv2: Failed System Test

システムテストで蹴られたのは {999999, 9} みたいな入力でした.数字の反転を一回もしなくていい場合を想定していませんでした.抜けてました.

チャレンジフェーズで他の人のコードを眺めながら,貪欲に探索していけばもっと簡単に書けそうだと気づきました.ということで練習ではその方針でクリアしました.

class TheNumberGameDiv2 {
  public:
  int reverse(int N) {
    int R(0);
    while(N>0) {
      R *= 10; R += N%10; N /= 10;
    }
    return R;
  }
  int cutint(int N) {
    return N/10;
  }
  int minimumMoves(int A, int B) {
    queue< pair<int, int> > Q;
    stringstream sA; sA << A;
    Q.push(make_pair(A,0));
    while (Q.size()) {
      int cur  = Q.front().first;
      int cost = Q.front().second;
      if (B==cur) return cost;
      Q.pop();
      int r = reverse(cur);
      int c = cutint(cur);
      if (r>0) Q.push(make_pair(r,cost+1));
      if (c>0) Q.push(make_pair(c,cost+1));
      if (cost > sA.str().size()+2 ) break;
    }
    return -1;
  }
};

PolygonTravarsal2: Opened

他の対角線と交差しているかどうかの判定で苦戦しました.結局完成せずに終了.あとは終了判定でも問題の条件をスルーしている部分がありました.いけませんね.

深さ優先で探索していって最後まで辿りつけたら 1 を返す→どんどん足し合わせる,というプランで問題なくクリアすることができました.

class PolygonTraversal2 {
  public:
  bool is_intersect(int from, int to, vector<int> points) {
    int f = 0;
    int t = to - from;
    int N = points.size();
    for (int i =0; i<N-1; ++i) {
      int x1 = points[i] - from;
      int x2 = points[i+1] - from;
      if (f < x1 && x1 < t && t < x2) return true;
      if (f < x2 && x2 < t && t < x1) return true;
      if (x1 < f && f < x2 && x2 < t) return true;
      if (x1 < t && t < x2 && x2 < f) return true;
      if (t < x1 && x1 < f && f < x2) return true;
      if (t < x2 && x2 < f && f < x1) return true;
      if (x2 < f && f < x1 && x1 < t) return true;
      if (x2 < t && t < x1 && x1 < f) return true;
    }
    return false;
  }
  int run(int N, vector<int> points) {
    int cnt(0);
    int len = points.size();
    int tail = points[len-1];

    if (len==N) {
      if (is_intersect(tail,points[0],points)) {
        return 1;
      } else {
        return 0;
      }
    }

    vector<int>::iterator pb = points.begin();
    vector<int>::iterator pe = points.end();
    for (int i = 1; i <= N; ++i) {
      if (find(pb,pe,i)!=pe) continue;
      if (!is_intersect(tail,i,points)) continue;
      vector<int> p = points; p.push_back(i);
      cnt += run(N,p);
    }
    return cnt;
  }
  int count(int N, vector <int> points) {
    return run(N,points);
  }
};

Challenge: 150.00

500 点問題を 3 つ撃墜しました.初撃墜成功(「・ω・)「

使用した入力は {43212345, 234} です.最初に「A が B を含む」「逆順 A が B を含む」の場合分けをしている人はだいたいこれで落ちてくれました.


次回は問題をクリアして点をとりたいです(´;ω;`)

2013/03/14

Round #173

| 10:37 | はてなブックマーク - Round #173 - どせいふんとうき。

今回で 4 回目の参加です.結果は o-o-- の 2 完で 1712 点でした.C 問題を解いたおかげかレーティングは 1422 -> 1511 と上昇して Specialist から Expert にクラスチェンジしました.


A. Bit++: 494

"++X", "X++", "--X", "X--" の 4 パターンしか入力がないので場合分けしました.

B. Painting Eggs: ---

問題文をよく理解できないまま終わってしまいました.

Practice で解いてみました.まず何も考えずに A, G のうち数が少ない方だけを選択します.A, G のつけた値段の合計値は常に 1000 なので A->G または G->A に変更した場合,値段の差 (Sa-Sg) は常に 1000 だけ動きます.ということで差の絶対値が 500 以下になるまで選択を変更していけばいつか答えに辿り着きます.

C. XOR and OR: 1218

手を動かして色々と試してみたところ bit の立っている数が 0 か 1 以上かに注目するだけで解けそうだと予想できました.実際テストもパスしたので間違ってはいないと思います.

D. Yet Another Number Game: ---

数字が 2 つの場合は後者が勝つことのできる組み合わせはかなり限られることがわかりました.では数字が 3 つの場合は……と手を動かしているうちにタイムオーバーでした.

E. Sausage Maximization: ---

読んでないっす:(;゙゚'ω゚'):


3 問完答を目指したいところです!

2013/03/07

SRM 572

| 14:18 | はてなブックマーク - SRM 572 - どせいふんとうき。

今回で参加は 5 回目です.結局 Hard には手が出なかったのですが 486.05(=511.05-25.00) で 94 位,レーティングも 1068 -> 1133 と上昇しました.500 点問題に思ったより時間がかかってしまったのでもっと順位は悪いと覚悟していたのですが,思わぬレーティング上昇でした.500 点問題の記述があいまいだったのでもしかしたらそのせいだったのかもしれません.

EasyHomework: 245.47

全部掛け算した時の符号を答える問題でした.書くだけです.

NextOrPrev: 265.58

ダイヤル式ワイヤー錠みたいな感じでアルファベットを start から goal まで遷移させるためのコストを計算する問題でした.問題文には直接書かれてはいなかったのですが「変換途中でも同じアルファベットが文字列中に出現してはならない」というルールのようです.

startgoal でどの 2 文字も前後関係が逆転していないことが変換可能な条件になります.変換可能ならコストを計算,不可能なら -1 を返して終了です.念のため文字列を vector<int> に変換して解いたのですが特に必要ありませんでしたね…….

DistinctRmainders: opened

整数 NM で割った余りが互いに異なる和に分解する問題です.分解した整数の集合に同じ数は決して含まれません.k 個に分解する単調増加な数列の個数 N(k) がわかれば k 個に分割する組み合わせは k!×N(k) 通りになります.しかし N が最大で 1e18 にもなるのでループを回すことができません. N(k) を計算する方法を試行錯誤しているうちにタイムオーバーとなりました…….


Challenge: -25.00

NextOrPrev で「これ隣同士しか前後関係をチェックしていないんじゃ?」と早とちりして誤爆です.

貴重な 25 点を失いました(´;ω;`)


目指せ!時間内に Hard 提出! Challenge で自爆しない!を目標に精進します.

xr0038xr00382013/03/08 18:07"NextOrPrev" は問題文の every occurrence を見落としていた模様

2013/03/05

Round #171

| 14:05 | はてなブックマーク - Round #171 - どせいふんとうき。

今回で 3 回目です.結果は o---- ということでレーティングも 1482 -> 1422 にダウンです.


A. The Point on the Spiral: 470

くるくる回りながら曲がった回数を数えるだけでした.

B. Books: ---

いい方法が思いつかないまま時間とメモリの制限に引っかかりまくりました.

結局 Practice で粘るも解けず,他の方のプログラムをみて勉強しました.どうやらシャクトリムシのように head と tail でポインタを動かしていくとうまくいくようです.これなら head が配列を舐めるだけの計算時間で済むので時間の制限に引っかかりません.なるほど.ある数列から数の決まっていない連続成分を抜き出すときに活用できそうです.

C. Ladder: ---

いい方法が思いつかないまま時間の制限に引っかかりまくりました.

結局 Practice で粘るも解けず,他の方のプログラムをみて勉強しました. 2 重にループを回してしまうと計算量オーバーになってしまいます.指定された区間の中に山が 1 つだけある(谷はない)ということを簡潔に評価する必要があります.ここで,区間の左端は山を左から,区間の右端は山を右からみることに注目します.区間の左端については「今登っている坂の頂上」の情報,区間の右端については「今降りている坂の頂上」の情報があればよいことになります.この 2 つが一致する(あるいはどちらも同じ坂にいる)かどうかを調べれば問題はすぐに評価できます.判定に必要な配列はそれぞれループを 1 回舐めればよいので時間的にも問題ありません.与えられた区間の中に特徴量が存在しているかどうかを判定するような問題で活用できそうです.

D. The Minimum Number of Variables: ---

読んですらいません.

E. Beautiful Decomposition: ---

問題を読んだだけです.


悔しいのでふんぬーと復習してがんばります.