2010-10-09

■ [Codeforces]Codeforces Beta Round #33 (Codeforces format) 23:44

2010-10-07 24:00-

http://codeforces.com/contest/33

Codeforcesはあまりレーティング気にしないのでC++でやっています。

ID	タイトル	結果	ひとこと
A	What is for dinner?	hacked->AC 01:38	英語が難し過ぎる
B	String Problem	WA->AC 00:33	違う長さの入力があり得る意味はあるのか
C	Wonderful Randomized Sum	AC 00:44	好きなタイプの問題
D	Knights	PE->AC 01:00	SRMと問題被っちゃった
E	Helper	Opened	問題文読んでやる気なくした

Coding

• A
  • 珍しく開始直後にすんなり開けた
  • 問題文難しいよ
  • サンプルから何をすればいいか推測できたので提出。CE…
  • デバッグ用の自作ヘッダファイルをインクルードしてたのを忘れていた
  • 消して提出。pretest Accepted.
  • 〜1時間後〜
  • hackされた…
  • vectorの初期化を適当に10000でやってたけど入力は10^6までだから間違ってた
  • 再提出、AC
• B
  • まずワーシャルフロイドして各文字対について遷移コストを出しといて、
  • 文字ごとに1つ目の文字列と2つ目の文字列のどっち側に合わせるかコストが小さい方に決めればよいか
  • 提出、WA
  • ああ、a->c、b->c みたいに、どちらも初期状態から変化するケースがあるわ
  • 26通り全部確かめるようにして再提出、AC
• C
  • O(N)になるように気をつければどうやってもできそう
  • とりあえず、交差するパターンは結局真ん中に反転しない領域ができるだけで、交差しないパターンと同じだから考えなくて良い
  • まず先頭から見ていって、「1文字目〜k文字目を反転させるパターンの中で、元の数列から最もプラスに変化する場合の値」を各kについてDPで求めておく、これをX(k)とする
  • 次に後ろから見ていく。「n-k+1文字目〜n文字目を反転させたときに元の数列からどれだけ変化するか」をY(k)とすると、(元の数列の和) + max(X(n-k) + Y(k)) が答え
  • 提出、AC
• D
  • あ…この問題、ITmediaのアルゴリズマー連載でやったところだ！（2回目）
  • サイズが微妙に大きい（1億）けどC++だから間に合うんじゃないのと高をくくって書く
  • 一応、各人が各円の中にいるかどうかは前計算しといたり、cin/coutじゃなくてscanf/printfを使ったり、という程度には気を使った
  • 提出、PE。え。
  • 改行じゃなくて"\n"という文字列を出力してた…しょぼい
  • 再提出、AC
• E
  • ぎゃー問題長いー
  • これ時刻の部分ってただ実装をややこしくするための要素にしかなっていないような
  • やる気をなくした
• hack
  • Bで同じ文字対についての遷移コストが複数与えられる場合を狙ってみた
  • が、全員対策できている。やたらBでWA出してる人もいるしこのケースはpretestに含まれてたのか
  • HaskellとかDelphiとか読めないですし
  • 終了間際にCで間違ってそうなのを見つけたが間に合わず

結果

• スコア：3778
• 順位：42位/613人
• レート：1705 -> 1851

Dが既知の問題だったのですぐできたのが大きかった