Saratov school team programming contest 2011

Codeforces Online Judge

研究室でだらだらしながら解いた。

A問題

  • 問題分が読みにくだけ。というか入力4通りしか無いんかよ。
    • 書いた。submit。Idleness limit exceeded。
    • なんぞこれ。調べてみたらinput.txtから読み込まないとダメらしいので書きなおしてsubmit。AC。

B問題

  • やるだけ。書いた。AC。

C問題

D問題

  • やるだけ。書いた。AC。

F問題

  • Eがよく分からんのでこっちに。
    • treeの直径の問題。書いた。AC。

H問題

  • 文字列の問題。
    • よく分からん。文字列を全て生成するのは無理だな。
    • 文字列は27^4くらいか。とういかこれ割当問題じゃん。
    • Dinicコピペしてきてsubmit。WA。
    • 逆辺にflowを流すのを忘れてたので修正してsubmit。AC。

G問題

  • やるだけ問題。書いた。WA。
    • よく見たら。dの計算部分がおかしかったので修正してsubmit。AC。

E問題

  • ぜんぜん分からん。n=1,3の時は0でn=2の時は1か。
    • とりあえずn=2の時だけは1を返すとしてsubmit。WA。
    • じゃあn%2=0の時だけは1を返すとしてsubmit。AC。
    • こんなんでいいのか？

J問題

  • マンハッタン距離の最小か。とりあえず全ての点は第一象限に移して良いな。
    • 最大化の方はO(nk2^k)で解けるからそれ使えばいいんじゃね？
    • どうもminとmaxの入れ替えができないんで無理っぽい。
    • 平面走査は？できそうな気もするけどめんどい。
    • 問題よく見たらマンハッタン距離じゃなくてユークリッド距離じゃん。
    • えーとボロノイ図を考えると明らかにO(nlgon)でできるけどむずそう。
    • というかこれ最近点対の問題じゃん。ググったらSpaghetti Sourceのソースコードが出てきたんで貼りつけてsubmit。WA。
    • 点が重なっている場合に死んでたので修正してsubmit。AC。

I問題

  • めんどそうな問題。
    • とりあえず8が重要そう。
    • しばらく考えた結果、上の桁から値を決めて行ってその値の時に条件を満たす列が存在するかチェックすればできそう。
    • でも実装がめんどそう…。

結果

9完 1050分 97位 2073→2042。
あんまりReginal Contestっぽくは無かった。