Hatena::Grouptopcoder

blu_rayの日記

2011-08-31

SRM 516 Div2

| 14:30

ox-

250. NetworkXZeroOne / Passed System Test

そもそも英語が読めてない。'o'と'x'を同量にするらしいけど、なぜか交互に出現している

(部分列の'o'と'x'の量は等しいから?)から適当に交互に出力。

500. NetworkXOneTimePad / Challenge Suceeded

最後の一行

A key is consistent if for all members of ciphertexts C, there exists a member of plaintexts P such that when P is encrypted using the specified key, it becomes C.

適当に生成したkeyは、他の全てのplaintext,ciphertextでもうまくいくかどうか確認しないと駄目でした。

1000. NetworkXMessageRecovery / Opened

わからない。

rate := 976 -> 967

英語が死ねる

Codeforces Beta Round #84 Div2

| 14:12

ooo--

Lucky Number回。

A. Nearly Lucky Number

数えて足す。

B. Lucky String

abcdを繰り返す。

C. Lukcy Sum Of Digits

7を多く含める場合から計算していく。

D. Lukcy Probability

数え上げて全部の場合で割ったらいいと思ったけどコードがかけない。

E. Lucky Tree

未読

殆どの人が3問通してるので、早解きが大事だったけど能力的に無理だった。

rate := 1336 -> 1381

2011-08-24

Codeforces Beta Round #83

| 20:14

oxx--

A. Palindromic Times / Accepted

結構時間かかった。submitまで27分で、決め打ちでやったほうが早かったのか..?

B. Datatypes / TLE

submitは1時間後で、システムテストで落ちてる。

N=10^6で、O(N)で済むところをO(N^2)にしてて見積もってなかったのが原因。

もったいない。

C. Dorm Water Supply / WA

入次数が0の頂点から出次数が0の頂点までDFSするというか辿るだけだったのに、

本番中は入次数0から始めないで適当に端からDFSしてたのが原因だった。

これももったいない。

struct Result {
  int tank, tap, diameter;
  Result():tank(0),tap(0),diameter(0){}
  Result(int a, int b, int c):tank(a),tap(b),diameter(c){}
  bool operator<(const Result& a) const {return tank < a.tank;}
};

int n, p, es[1002][1002], a, b, res_size;
bool used[1002];
Result result[1002];

void dfs(int from, int cur, int meter) {
  if (used[cur]) return;
  used[cur] = true;
  rep(i,n) if (es[cur][i] > 0) {
    dfs(from, i, min(meter, es[cur][i])); return;
  }
  if (from != cur) {
    result[res_size] = Result(from+1, cur+1, meter);
    res_size++;  
  }
}

int main(int argc, char* argv[]) {
  memset(es, -1, sizeof es);
  set<int> taps;
  cin>>n>>p;
  rep(i,p) {
    cin>>a>>b;
    a--; b--;
    taps.insert(b);
    cin>>es[a][b];
  }
  fill(used, used + n, false);
  rep(i,n) {
    if (!used[i] && !taps.count(i)) dfs(i, i, 1<<28);
  }
  if (res_size) {
    sort(result, result+res_size);
    printf("%d\n", res_size);
    rep(i,res_size)
      printf("%d %d %d\n", result[i].tank, result[i].tap, result[i].diameter);
  } else {
    puts("0");
  }
  return 0;
}

D. BasketBall Team

英語は読めたけど、Sample inputの2と3を見て混乱した。

E. Arrangement

未読

rate := 1366 -> 1336

そろそろ減り幅が少なくなってきた.

上で冷静に書いてて、ありえない勘違いが多すぎる気がする

2011-08-21

SRM 515 Div2

| 22:51

oo-

250. FortunateNumbers / Passed System Test

Lucky Numberに続いてFortune Numberが。

3重ループ。

500. RotatedClock / Passed System Test

短針(時針)の mod 30を取ると、そこから適する長針(分針)が求まるので

あとは全12パターンの配置を確かめてvalidか判定。

多分一意に定まると思ったけど一応答えのパターンをキープしてソートするようにしたけど無駄だったのかな…。

->無駄だった様です

1000. NewItemShopTwo / Opened

一読 > 理解できない

rate := 899 -> 975

tatuyan_edsontatuyan_edson2011/08/22 03:25おっしゃるとおり、500は一意です。

時針の角度から何分か定まる→12時の方向がわかる→計算、という方針の連接構造で書いてみましたところ、普通に正解しました。

2011-08-19

Codeforces Beta Round #82 Div2

| 04:31

xoxx-

A. Card Game

完全に問題文読み違えてた。

嬉々として全部で6通りとかでsubmitしてた。

B. Choosing Laptop

ループ回すだけ。

C. Buns

ボケてたので、d[i]/c[i]でソートして貪欲に…みたいな、

初めてナップサック問題に取りかかった時の様な間違いをした。

なので、ナップサックのコードでPractice通った

int n, m, a[12], b[12], c[12], d[12], dp[12][1002];

int rec(int i, int j) {
  if (dp[i][j] >= 0) return dp[i][j];
  if (i == m+1) return 0;
  int res = rec(i+1, j);
  if (j >= c[i]) {
    for(int k=1;k<=a[i]/b[i] && j-c[i]*k >= 0;k++)
      res = max(res, rec(i+1, j - c[i]*k) + d[i]*k);
  }
  return dp[i][j] = res;
}

int main(int argc, char* argv[]) {
  cin>>n>>m>>c[0]>>d[0];
  a[0] = 1000;
  b[0] = 1;
  rep(i,m) cin>>a[i+1]>>b[i+1]>>c[i+1]>>d[i+1];
  memset(dp, -1, sizeof dp);
  cout<<rec(0, n)<<endl;
  return 0;
}

DPでかけない。

D. Treasure Island

ナイーブ実装をする > 兄貴にHackされる

そのうち確認

E. Space Rescuers

問題読めない。

rate := 1411 -> 1366

順調に減少

2011-08-16

Codeforces Beta Round #81

| 17:17

xx---

A. Transmigration / Failed System Test

Wrong Answer on test31.

Editorialの

be careful with comparation of floating numbers and if it is possible do it in integers.

ですね。

B. Dark Assembly / WA

問題文の勘違い。

If strictly more than half of the senators take a positive decision ..

太字になってたのに、半数以上と過半数以上を間違えた…。条件を直したら通った。

キャンディの上げ方はk^k通りで、確率を計算する時は2^n通りの状態を考えるけど、2^nをbitでやってる人のが格好良かった。

C. Item World

D. Entertaining Geodetics

E. Lift and Throw

unratedみたいですね。

2011-08-10

SRM 514 Div2

| 16:26

ox-

魔法少女回。

250. MagicalGirlLevelOneDivTwo / Passed System Test

愚直に水平、垂直、斜め移動を考えて書く。

submitまでに22分かかってる…。

500. MagicalGirlLevelTwoDivTwo / Failed System Test

最初に

for(int loop=1;loop;loop--) rep(i,MAX_N) rep(j,MAX_N) if (visited[i][j]) {
  rep(k,jumpTypes.size()) {
    // 塗りつぶし
    // 更新があったら
    loop++;
  }
}

みたいなコードでsubmitして1000Openして帰ってきて大きめのケースを試してみたらTLEして焦る。

その後、BFSに書き直したらTLEしなくなったので喜んでたらシステムテスト落ちた。

const int MAX_N = 60;
int visited[MAX_N][MAX_N];

座標を+30してやっていて、(x,y)のどちらか30とかのケースで死んでる ><

PracticeはMAX_N = 61で通ったけど、Div1Easyとかみて偶寄だけで通す問題ということを知って複雑。

1000. MagicalGirlLevelThreeDivTwo / Opened

みたけど読んでない。


rate := 936 -> 899 (灰色にもどる)

凡ミスがおおい。

2011-08-07

Codeforces Beta Round #80 Div2

| 01:49

ox---

A. Blackjack

書くだけだけど、submitまで12分かかってる。

B. Testing Pants for Sadness

方針はあってたけど、オーバーフローで死んでる!!

int * intの計算で32bit越えてた...

long longにしたらPracticeで通ったけど、もったいない。

C. Cthulhu

問題が読めなかった。

他の人のsubmitみるに、無向グラフが与えられて、

閉路が一つあるかどうか調べる(?)。そのうちやろう。

D. Russian Roulette

E. Time to Raid Cowavans

みてない。

げきちん

rate := 1480 -> 1411

2011-08-05

Codeforces Beta Round #79 Div2

| 04:03

ooo--

A. Clothes

混乱して全域木のこととか考え出してたけど、n=100でO(n^3)だった。

B. Sum of Digits

収束するまで繰り返すだけだと思った。long longかintか迷ったけど。

C. Homework

よくわからなかったけど、覚える単語の数を最小にすればいいっぽいから

単純に単語の出現数を数え上げて、少ないほうからk個分ずつ取っていけばいいだけ。

最後に出現する文字列も、よく訳せなかったけど覚えなくていい文字を

全部出力する感じになってたから、そういう感じにしたら通った。

D. Buses

問題は読めたと思う。

E. Vectors

問題は読めたと思う。

rate := 1379 -> 1480

IndiaIndia2011/08/30 09:32My hat is off to your astute cmmonad over this topic-bravo!

koabgqtnxkoabgqtnx2011/08/30 17:24GIPmAv <a href="http://oxpmayudnrxt.com/">oxpmayudnrxt</a>