2010-06-12

■ [Codeforces]Codeforces Beta Round #17 00:18

2010-06-10 24:00-

http://codeforces.com/contest/17

ID	タイトル	結果	ひとこと
A	Noldbach problem	AC 00:08	問題設定が不自然
B	Hierarchy	WA*2->AC 00:28	難しくやり過ぎた
C	Balance	Compiled	はやとちり
D	Notepad	WA*7	WA地獄
E	Palisection	UnOpened	読んでない

• 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した分かなり順位が下がってしまった