Codeforces Round#7 - simezi

直前のサーバトラブルで開始が24:45に……
今回は参加制限なくて参加者多かった所為かな？

A Kalevitch and Chess

8x8のチェスボートがある。最初ボードは真っ白で、列または行を黒く塗りつぶす操作のみができる。
ボードの色が与えられたとき、その状態にたどり着く最短の操作の回数を求めよ。

ありえない状態は渡されないので初期状態から貪欲にシミュレートしてけばおｋ.
Submit→AC.

B Memory Manager

mバイトのメモリを管理するメモリマネージャにt個の命令が与えられる。マネージャの動作をシミュレートをせよ。命令は次の3種である。

alloc n: nバイトの連続する領域を確保する。確保に成功した場合領域のID番号を出力、失敗した場合"NULL"を出力する。
erase x: ID番号xの領域を破棄する。xが不正な場合"ILLEGAL_ERASE_ARGUMENT"を出力する。
defragment: 領域をその順番をかえずにできるだけ開始方向に寄せる。

うーんと、m≦100ってことはこれも実装問？なんだかDiv制限ないのに前回のような問題セットだ……
書く。がりがり→Submit.

→WA
ILLEGAL_ERASE_ARGUMENTを出力せよって記述を見落としていた。
修正→Submit

→WA.
何だろう。ひょっとしてeraseの引数に0が与えられたりするのか。修正。
Submit→AC.

なんだこれ微妙だな。

C Line

x,yについての整数不定方程式Ax+By+C=0が与えられる。
解が存在するなら解のうち一つをスペース区切りで、存在しないなら-1を出力せよ。

問題文短い！このくらいのほうが読みやすくていいよ……
えーとなんだろうこれは。ディオファントス方程式の特別な場合？ユークリッドの拡張互除法を使えばよかった気がする。
まずはA=0,B=0の時を場合分け。

書いた。Submit

→Presentation Error.
えー？もしかして存在しないときって-1 -1を出力すんのかなあ。
修正→Submit.

→PE.
……なんぞ。場合分けをミスってるとかか……あ、A=0またはB=0のとき解なしのパターン記述忘れてるじゃないか！！
修正してSubmit.

→AC.
いけないもう4ペナルティだ。

D Palindrome Degree

与えられた長さnの文字列が回文であり、先頭[n/2]文字と末尾[n/2]文字がk-1回文の時、その文字列はk回文と呼ばれる。また、長さ0の文字列は0回文である。
Σ[1≦i≦n]（与えられた文字列の先頭からi文字目までがk回文となるような最大のk）の値を求めよ。

うーんと入力が最大5x10^6だからアルゴリズム問題かー。
O(n^2)以上だと間に合わない。O(nlog n)程度が必要？

さっぱり思い浮かばない。
愚直に実装してO(n^3)送ってみる。

→TLE(TestCase 8)
ですよねー。どうしよう。なんかメモ化とか出来ないだろうか。
今判定してる部分が回文だとすると、前半[n/2]文字が回文であることと末尾[n/2]が回文であることは同値。
お、メモ化できそう。がりがり。Submit

→TLE(TestCase 12)
ちょっと改善したぽいけどダメだ。だってこれどうみてもO(n^2)以上かかってるもんなあ。
もう時間がない。かくなる上は……
多分12のケースはaaaaa...aaaaa（aが5x10^6）とかだろどうせ。その対策してSubmitしてやれ。
先頭から連続する文字をカウントして、回文判定がその領域だったらO(1)で別処理……と。どうだろう。Submit.

→TLE(TestCase 12)
ちがうんかいorz.ああもう残り5分だ。諦めよう……

Eは問題オープンもせず。Standingを眺める。

Result

3AC、4ペナルティの88位。
何気に2桁順位は初めてな気が（今までがどんだけ酷かったの）
やっぱ４ペナは痛いなあ。。。上位見るとやっぱりみんなペナルティ少ない。

今回のセットではしょうがないような気がしないでもないが、記述ミスとかしてるのは減らす余地があるだろう。
あとアルゴリズムの勉強！！新学期も始まるし頑張ろう。