ICPC夏合宿の問題。5時間10問。 以下、通せたものは通した順に、自分がやったこととかです。 詳しい解説はwataさんのところ(http://d.hatena.ne.jp/wata_orz/20090922)とかを参照してください。

250 (SPOJ GNY07A) やるだけ 500 (SPOJ STSTRING) 文字A種で1〜L文字以下の文字列に長さ順→辞書順で番号を付けるとうまいこと変換ができるのをPKUのどっかで覚えたので、最初にCなれるものの番号を全部求めておいてlower_bound - upper_boundとかやった 1000…

250 (SPOJ CANTON) やるだけ 500 (SPOJ INUMBER) O(n^2)の幅優先だが、適当にやるとTLEするのでpairをやめるだとか枝刈りするだとかが必要 1000 (SPOJ OFBEAT) 各縦横の(極大な)線分に対して1本以上交わっているのが必要十分条件 とりあえず縦と横で独立に考…

250 (SPOJ CUBES) やるだけ a優先で列挙しても、b,c,d優先で列挙してソートしてもよい 500 (SPOJ IM) 流すだけ しかし入力に範囲外の頂点番号が入っていたりするようなので注意 1000 (SPOJ PT07D) labeled unrootedは有名なn^(n-2) labeled rootedはそのn倍 …

250 (SPOJ ASSIST) 素数と見せかけて実は違うというたぶん有名な問題 解を埋め込んだがnの上限を見誤ったりしたせいでいろいろミスったorz 500 (SPOJ PLD) Manacherまたはrolling hash 1000 (SPOJ MOD) 離散対数 後でいろいろやってみたが、JavaでO(√z log z…

250 (SPOJ CLONE) やるだけ MとNを間違えて落ちたorz 500 (SPOJ SUMSUMS) 軽い数学 オーバーフロー要注意 1000 (SPOJ FOREST2) 幾何 各区間で最も近くに見える円は、接線の長さが最小のもの Result RE + WA + WA = 0.00 5位 初敗北orz

250 (SPOJ HANGOVER) PKU1003なので有名問題 500 (SPOJ OPTM) 各ビットごとに最小カット 最小カットに使う辺を具体的に求める段階で混乱して組み終わらなかった 1000 (SPOJ MOBILE) まずはまともな行列であることを確認 3つ以上に分岐している棒は同じ高さに…

250 (SPOJ EIGHTS) やるだけ 500 (SPOJ CATM) どこかの脱出口に1ターン以上早く辿り着ければYES 1000 (SPOJ CLEVER) 普通に状態10^6×6のBFSをやるとTLE 増減するのはカーソルがあるときのみであることに注目して、置換とカーソルが乗った数字を状態にした6!×…

SPOJが導入された 250 (SPOJ TOANDFRO) やるだけ 500 (SPOJ QUEST4) 流すだけ 1000 (SPOJ COVER) 流すだけ……だとTLE 流すとき、残余ネットワーク上で2部グラフを行ったり来たりするが、 コストの性質により費用合計は最初の点と最後の点のみによって決まるの…

KMC初？の怪しい形式 A へいほうじょうよといったらおーばーふろーにちゅうい！ を覚えていればやるだけ B 埋め込むだけ C ログ開始時点からの変化の最大と最小だけ気にすればよい Result 3完で1位

250 最初、文字化けのため「A+B」というタイトルとInputとOutputのみから問題を推測する大会になってしまった 順番に調べれば間に合う 500 A==1とB>=63を処理してからBigIntegerでやるのが楽 1000 きたまささんの気持ちになりきるだけ Result 193.33 + 461.2…