Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

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

トラックバック

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

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

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

Assignment

250-450-1000の微変則セット.
よく見かける強い日本人が何人かいる部屋.

EASY

与えられた数列 (要素数50以下) が,以下の4つの等差数列を繋げたものになっているかどうかを判定する問題.
 最初は単調増加の当差数列 (要素数2以上)
 次は単調減少の当差数列 (要素数2以上)
 次は定数数列 (要素数1以上,つまり空でも良い)
 次は単調増加の当差数列 (要素数2以上)
 次は単調減少の当差数列 (要素数2以上)

Foxもふもふ.
ループ回すとき,ちゃんとどこからどこまで回すか考えないと1間違えて落ちそう,慎重に組もう.
で,左からなぞるだけでO(n)でできそうではあるのだけど,サイズも大きくないし着実に組む方法で.
どこからどこまでがどのパートに対応するのが全探索して,validなものがあるかどうかを調べる.
あ,これだと,O(n^5)なのか…,まぁ多分大丈夫だろ.
書く.
書いた.50要素で試してみても余裕で間に合う.じゃ,いける…多分.
サブミット.
見直しして次へ.

MEDIUM

200*200以下の盤面の書くセルに,それぞれ違う色の石が1個ずつ置かれている.
50セル以下,指定されたセルがある.
セルAと指定されたセルとの距離が,全て,セルBと指定されたセルとの距離と等しければ,セルAの石とセルBの石を入れ替えることができる.
距離は,x座標の差とy座標の差の大きい方で定義される.(1-ノルム)
得られる盤面はいくらあるか,mod 1000000009で求める問題.

問題文の意味が分からない,どういうことだ…?
同じ距離の石は入れ替えることができる…のかな?
えっと,それぞれのセルの状態を,各指定されたセルまでの距離のベクトルとして,
同じ状態のセルは入れ替え可能だから,同じ状態のセルの数の階乗を掛けていくだけなのでは.
そんな気がする.書いてみよう.
書いた.サンプルあったのでサブミット.これはサンプル合えば大丈夫だと思うので次

HARD

最初(0,0)にいる狐が,ちょうどR回 (1600以下) のジャンプで (Tx,Ty) に移動するジャンプパターンの数をmod 10007で求める問題.
MxとMyが与えられて,1回のジャンプでは,x軸の正方向に0セル以上Mxセル以下移動,y軸の正方向に0セル以上Myセル以下移動しなければいけない.
現在のセルにとどまるジャンプは許されない.
また,要素数50以下,各要素10の倍数の配列badが与えられて,x軸方向にも,y軸方向にも両方ともbad[k]だけ移動するようなジャンプは許されない.
Tx, Tyは0以上800以下,Mx, Myも800以下.

単純にDPしてみたら…,流石にTLEなのか.
さてどうしたものか.
x軸とy軸を分けて1次元で考えたいよね.
留まるのもめんどいから,badに0を追加して,留まることができないってのも考えないことに使用.
badがなければ,1次元ごとに分けて考えれる.
あ,わかったかも.
badを何個使うかで,包除原理で計算すれば良いのじゃないの?
良さそうだ.
書いてみよう.
…,結構面倒.
コンビネーションとかも必要なのか.
書けた.
提出.

Challenge

EASYでループの範囲を間違えている人を探す.
いないなぁ….(後々サンプル見直すと,かなり親切だったことに気づく)
何もせず.

System tests

全部通る.簡単めだったとはいえHARD通るとか珍しすぎる.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。