Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

 | 

2010-06-12

[]Codeforces Beta Round #17 00:18 はてなブックマーク - Codeforces Beta Round #17  - TopCoderの学習のお時間

2010-06-10 24:00-

http://codeforces.com/contest/17


IDタイトル結果ひとこと
ANoldbach problemAC 00:08問題設定が不自然
BHierarchyWA*2->AC 00:28難しくやり過ぎた
CBalanceCompiledはやとちり
DNotepadWA*7WA地獄
EPalisectionUnOpened読んでない
  • A
    • 素数生成して書くだけですね
    • 連続する素数とか+1するのとか忘れててちょっと手間取ったが書けた
    • 提出。AC
  • B
    • 最小全域木作ればいいのかな
    • 最小全域木の書き方ちゃんと覚えてないのでいつも冷や冷やだ
    • とりあえず書けた、提出
    • WA
    • 1人が複数の上司を持つような木を作ってしまっていた
    • すでに上司がいる人からは上司方向に枝を伸ばさないよう修正
    • WA
    • ううむ何故だ。てかテストケース#1で落ちるとか
    • デバッグ出力残したままだった…
    • AC
    • よく考えてみると、最小全域木とかやらなくてももっと単純な貪欲で良かった
  • C
    • 一気に難しくなったぞ
    • 1文字ずつ進めていくDPかなぁ
    • dp[i][j][k][l]で、「i文字目まで見たとき、i文字目が('a'+j)で、0文字目〜i文字目までに含まれる'a'の数がk、'b'の数がlとなる場合の数」を表すようなDPを書いてみた。150*3*150*150
    • サンプルの答えが全然合わない
    • 前から後ろへ浸食していく変化しか考えてなかった…
    • これはわからん、解いてる人も少ないし次の問題へ行こう
  • D
    • とりあえずBigIntegerで単純に書いてみようか
    • TLE。まあそうですよね
    • 自分で最大テストケースを作ってみた
    • modPowする以前に、文字列からBigIntegerを作るところが遅い。そりゃ100万桁を食わすとそうなるか
    • 一気にやるのが無理なら、100桁ずつとか適当な桁数で区切って、インクリメンタルに処理していけばよいのではないか
    • いろいろバグったが書けた
    • 桁数を変えて試してみると、1000桁くらいで区切るのが一番速いようだった。自作最大ケースが手元で1秒。いけるか…
    • WA on case #61
    • ええー
    • そこまで進んでいるということは大枠は合っているのだと思うが、コーナーケースがあるのか…
    • 全然わからない
    • 終了
    • てか1桁ずつやればBigInteger使わなくても良かったですね

結果

  • 順位:193位/513人
  • レート:1661 -> 1597

3問目以降が難しかったので、BでWAした分かなり順位が下がってしまった

 |