fc2ブログ

Entries

SRM497 DIV1 参加記録 (この記事を編集する[管理者用])

2011年02月11日11時02分から.

Assignment

250-550-1000の少し変則セット.てか最近標準セットの方が珍しくないか?

EASY

1~N+1の数字の置換(a[0], a[1], ..., a[N])に対して,N文字の文字列Xを
 X[k] = I (a[k+1]がa[k]より大きい)
 X[k] = D (a[k+1]がa[k]より小さい)
にて定める.
文字列が与えられるので,それに対応する置換のうち,辞書順で最小のものを求める問題.
対応するものが存在しないならそれを指摘する.
Nは50以下.

とりあえず,対応しないものなんてない気がするが,多分ない.
うーんと,最初のIの場所を探して,そこを1にして,あとはIが続く限り1ずつ増やす.
後,次にIが見つかった場所からまた再開.
Dは逆順に同じようなことをやれば良い.
これで辞書順最小じゃないかな?
書いてみる.
全然違う.てか辞書順最小なわけじゃないじゃないか,サンプル1のDIで既に違うじゃねーか.
えっと,うーむ?
….
計算時間は余裕なはずだから….
k番目の数字がxに出来るかどうかを最初から全部調べても余裕だからそういう方針を立ててみよう.
それで,使わなきゃいけないのは…,自分の前は確定してるから,自分より後がずっと同じ文字だったら,
自分より大きい or 小さいものがその数だけないとダメ.
で,文字が変わったら,そこでいくらでも減らす or 増やせるから,その後はなんとでもなる.
よし,いける.
書く.サンプル合う.
サブミット.長かった….

MEDIUM

問題文に定められた形式のXHTMLが与えられる.
それぞれのタグに,colorの指定があるが,それを全部CSSでやりたいとき,最小で何個のルールを作れば良いかを求める問題.
タグの名前は,bとuとiのみ.
カラーの名前は,black, blue, gray, green, red, white, yellowの7種類のみ.
タグは,タグの名前と,ユニークな任意文字列IDと,指定したい色で,構成される.
CSSのルールは以下の2種類が利用可能.
 IDを指定して,それの色を指定する
 IDとタグの名前Nを指定して,そのIDの中にある全てのタグの名前がNであるタグの色を指定する
ルールは好きな順番で与えることができて,複数のルールが適応される場所は,最後に適応した色になる.
与えられるXHTMLは50*50文字以下.

最初に: 終始,複数のルールが適応される場所は最後に適応した色になるってのを読み落として,全てのタグに1つのルールしか適応してはいけないと勘違いした
問題文開いた瞬間嫌な感じががが.絶対めんどーなだけの問題.
問題文長いけど,思ったより問題文読みにくくない.結構簡単に読める.(これが罠だったか)
えっと,やっぱり,めんどーい.
まずは構文解析して木を作る.これをしないと始まらない.けどこれをしたら殆ど終わりか.
で,後は,自分の下のタグでそれぞれの名前について,全部同じ色だったら,一括で指定する.
そうでなければ,自分を塗って,部分木の処理を再帰でしてやる.
書く書く書く書く.苦戦しながら書く.
書いた.サブミット.
配列サイズが足りなくてリサブミットとかした気がするけど,よく覚えてない.

HARD

 X[0] = (K*A) mod N
 X[i] = (X[i-1]+K) mod N
で定めた長さB-A+1の数列の中に,lower以上upper以下の項がいくつあるかを求める問題.
A, B, K, Nは10^10以下.

まず,K*Aがlong longでオーバーフローするんですが….
で,これはどうするのだ….
あ,これ単に,K*nがupper以下になるようなnの数 (n = 0, 1, ..., N) を求めれればOKなんだなぁ.
時間ないし,MEDIUMの見直しでもしよう.

Challenge

見てるだけー.
550落とされたー,なんでじゃー.だいぶ見直ししたのに….

System tests

EASY通る.
とりあえず焦りすぎ.もうちょっと落ち着いて整理して考えないとダメ.
って,定期的に思い出してくれるのがTopCoderです.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1875-350d658f
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)