Hatena::Grouptopcoder

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

2013/04/12

SRM 576

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

日本時間だとお昼前の時間に開催でした.ちょっと危なかったのですがなんとか 2 問正当しました. Challenge は早とちりして失敗したため -25.00pt です…….レーティングは微増して 1005 -> 1061 になりました.

TheExperimentDiv2: 239.96

冷静にループを回せば難しくない問題でした.

ArcadeManao: 172.00

領域のサイズが小さかったので,配列を作って X にたどり着くために必要な最低のはしごの長さをどんどん更新していくことにしました.とりあえずテストケースを突破した所で投稿したのですが,コンテスト終了間際に自分のコードを撃墜する入力を思いついてしまったので急遽訂正.かなり汚いコードになりましたがなんとかシステムテストは突破しました.

CharacterBoard2: Opened

単純にループを回したら大変なことになるのかなぁ……とか思いつつ手を付けられずにいます.


Challenge: -25.00

誤爆しました(´;ω;`)


ArcadeManao の再提出に伴う減点が痛かったですが,まるごと 0 点になるよりはマシです.書きなおしがコンテスト終了までに間に合ってよかったです.設計をミスして無駄の多いコードになってしまったので反省しなければ…….

2013/04/07

SRM 575

| 07:04 | はてなブックマーク - SRM 575 - どせいふんとうき。

500 点問題がシステムテスト弾かれたので解けたのは 1 問のみ.レーティングは前回からさらに下がって 1025 -> 1005 になりました.かろうじて 3 桁をキープ.ギリギリです.


TheSwapsDivTwo: 191.52

数列の任意の位置をひっくり返して異なる数列をいくつ作れるかという問題でした.場合分けに自信がなかったのでじっくり考えてしまいました.点数低めです.

TheNumberGameDivTwo: Failed System Test

数取りゲームです.ある数 n からその約数を引いていき,引けなくなった時点でその人の負になります.DP を使って解けばさほど難しくない問題だったのですが,問題をちょっと勘違いして解いてしまったので Failed System Test をいただきました.

確認はしていませんが,僕のコードは入力に 30 を与えれば落ちたはずです.

TheTilesDivTwo: Opened

与えられたチェッカーボードに L 字型のボードを最大でいくつ載せられるかという問題でした.深さ優先探索で解けると思ったのですが,時間オーバーでシステムテストを突破できていません.探索に無駄があるようです.


前回がひどい結果だったのでリベンジのつもりだったのですが,前回とはさほど変わらない結果になってしまいました.他の人のコードを参考にしつつ,勉強を続けていきます(´;ω;`)

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/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/02/20

SRM 571

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

今回で 5 回目の参加になります.レッドブルは友達です.250, 500 点問題はスムーズに終えて 1000 点問題にたっぷり時間を残せたました.しかし問題を読み間違えていたためにテストが通らず,気がついたら時間切れに…….レーティングは 1048 -> 1068 と微増しました.


今回は初めてプラグインを使用して問題を解いたのでした.結果としてすごくスムーズに問題を解くことができたと思います.プラグインの制作者様に心より感謝します.


FoxAndGame: 244.53

きつねさんのスコアが文字列のベクタで与えられます.この文字列の中から o の総数を数えるという問題です.与えられる文字列のバリエーションが "---", "o--", "oo-", "ooo" しかないので if 文で分けて足し続けました.

FoxAndMp3Easy: 456.51

数字じゃなくて文字列でソートしてしまうきつねさんの mp3 player のプレイリストを再現する問題です.存在するファイル名をすべて作成,ソートして若い順に最大 50 個まで取り出すという方法で解きました.

MagicMoleculeEasy: Compiled

Compiled ですがサンプル通ってません.終了後に書きなおしたコードを Practice Room で投稿してみたのですがテストケースで弾かれてしまいました.まだなにか見落としがあるみたいです.


とりあえず

最終的にテストをパスするかどうかはともかく 1000 点問題を「サンプルテストを通過して投稿する」というところまでいきたいです.