Entries

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

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

コメント

[C50] Hi

おめでとうございます. このコンテスト後で挑戦してみたがは意外に難しく感じました.難易度が高いコンテストにRedCoderになれることはすごいと思いました.

[C51]

ありがとうございます.
今回のは3問目以降は普通に難しかったと思います.
なんとか赤のままでいられるように頑張りたいですね・・・.
  • 2010-06-11 16:41
  • rsujskf
  • URL
  • 編集

[C52]

> a^(phi(b)+1) = a (mod b)
これは偽みたいで (a=3, b=18など) 、

a^(phi(b)+k) = a^k (mod b)
でkが十分大きい (log bで十分) なら成り立つようです。
  • 2010-06-11 19:25
  • hos
  • URL
  • 編集

[C53]

> hos様
あ,あれ…,本当ですね,ごめんなさい.
なんで成り立つと思っていたんだろう…,ずっと勘違いしてました.
指摘ありがとうございます.
訂正しておきます.
(使うときは大抵k=phi(b)としてプログラミングしてました,今回は手を抜きましたが)
  • 2010-06-11 19:51
  • rsujskf
  • URL
  • 編集

コメントの投稿

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

トラックバック

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

Beta Round #17 (参加記録) (この記事を編集する[管理者用])

2010年06月11日00時から2時間,5問.
[ Link ]

A. Noldbach problem

1000以下の自然数nとkが与えられるので,2~nまでの素数のうち
 連続する2つの素数の和 + 1
で表せる素数がk個以上あるかどうかを判定する問題.

問題文が微妙に読みにくい,ってか,やることがややこしい.
ちゃんと読んで,普通に実装する,それだけだ.
Accept.

B. Hierarchy

ちょっと意訳する.ノード数1000以下の有向グラフが与えられる.
ノードの高さq[i]が与えられて,枝はすべて高い方から低い方に張られていることが保証されている.
最も高いノードを始点とする,有向最小全域木のコストを求める問題.

うーん,一番高いところからgreedyにプリム法っぽくやればいいんじゃないの….
がりがり….
違うよ,高いところから低いところにしか枝がないってことなので….
単に,自分に入ってくる枝のうち,最もコストの低いものを採用すれば良い.
で,自分に入ってくる枝がないノードが2個以上あると,答えは存在しない.
qの配列は使わない.
さくっ.
Accept.

C. Balance

150文字以下のabcからなる初期値の文字列が与えられる.
 i+1番目の文字をi番目の文字と同じにする
 i番目の文字をi+1番目の文字と同じにする
という2種類の操作を際限なく繰り返すことができるとき,バランスされた文字列は何種類作れるかmod 51123987で求める問題.
バランスされた文字列とは,文字列に含まれている各文字の数の差の絶対値が1以下.

DPだろうなぁ…,計算量大丈夫だろうか.状態は
 今何文字目を見てるか,Aに比べてBはどれだけ多いか,Aに比べてCはどれだけ多いか
で150*300*300ぐらいだろうか…?
うーん,まぁ,とりあえず書いてみようかな….
ある範囲は,その両脇にある文字全部に置き換えられる,と言った感じですよね?(違った,ここから暫くは嘘解法の考え方)
ってことで,計算量は150*300*300*150…?
うわー,間に合わない.
いや,まて,これだと,同じ文字列何回もカウントするよね.
え,っと,どうすればいい?
前に使った文字を覚えて置いて,それを連続して使わないようにすると,重複カウントなくなる?
メモリと計算量がさらに3倍….
えーっと…,何文字も先を一気に見るのではなくて,1文字ずつ見よう.
現在見てる文字は,前から伸ばして達成できるかどうかで,前回使った文字を分類する,前回使った文字を6種類に拡張.
がりがり.めんどい….
ようやくかけた.
サンプル1は答え2,駄目だ….
えっと,てか,サンプル下の説明見たけど,bccaとか作れないだろう…,どうやって作るの?
先に,bを伸ばしておいて,cで上書きするのか!
なるほど!
D問題へ行く….

D. Notepad

凄い意訳する.
(b-1)*b^(n-1) mod cを求める問題.ただし答えが1以上c以下で返す.
bとnは10^6桁以下,cは10^9以下.

えーっと,答えは何だ….
答えはb^(n-1)かな?
あれ,1桁の場合違くない?
違うよ,答えは(b-1)*b^(n-1)だよ!
サンプルb=2しかねぇ….
普通にbをmod cに直しておいて,べき乗計算するだけじゃない?
nを2で割っていくのが面倒だけど…,高速にやらないと間に合わなさそうだし.
書こう,がりがり.
いや,まてよ,これ,間に合わないだろう?
nを2で割るのはnの桁を全部なぞるから1回あたり10^6の計算量.
そして,その回数はlog nなので,やる回数も10^6.
O( (10^6)^2 )ですが….
危ない,ちゃんと計算量見積もらずに書いちゃうところだった,これは嵌めだなぁ.
うーん.
いや,よく考えたら,nも周期性使ってmodで落とせるよ.
一般に,
 a^(phi(b)+1) = a (mod b)  (2010-06-11 19:53追記 嘘でした,コメント参照のこと)
が成り立つ.(結構知られていなかったみたい?)
特にbが素数のときはphi(b)=b-1なので
 a^b = a (mod b)
とかなる.勿論,一般的には
 a^phi(b) = 1 (mod b)
は成り立たない.phiはオイラーのφ関数.
phi(b)は普通にbを素因数分解すればO(sqrt(b))で計算可能.
じゃ,書こう.書いた.Accept.

C. Balance (再)

つまり…,入力文字列がabbcだったら,正規表現で書けば,a*b*b*c*にマッチするバランスされた文字列の数を求めれば良い!
状態は
 正規表現の何処まで使ったか,Aを何文字使ったか,Bを何文字使ったか,Cを何文字使ったか
でやろう.正規表現の何処まで使ったかは,ループで回すから,実際にはメモリに全部残さない.
あ,前使った文字も書いてないと,重複カウントするよ.
 正規表現の何処まで使ったか,前使った文字,Aを何文字使ったか,Bを何文字使ったか,Cを何文字使ったか
かな….
書く.めんどい….めんどい….
DP更新のループを真面目に回すと,明らかにTLEなので,ある区間の和になることを利用して,うまく和を計算しつつ使い回す用に回す.
これでオーダーが1個減る.
サンプル1は…答え7,OK.
サンプル2は…答え6,駄目….
えー.
bbと来た時に,重複してカウントしてる….
前使った文字がabcのどれだったか,って覚えておくんじゃなくて,次にbを使わなければ,次にbも使えないことにしないと重複カウントするのか….
前使った文字じゃなくて,次使える文字に変えよう.ビットで情報を持つ.
状態数がまた増えた….
書いた.サンプルは合う.
もういい,サブミット.
テストケース37ぐらいでTLE….
うーむ.
同じ文字が連続してると,例えば正規表現でb*b*なんてときは,1回しか処理しないことにする.
他にも,ちゃんと考えれば枝刈りできる場所はいくらかあるはず…だが,面倒なので,保留.
送る.あ,通った.
(後で見直すと,入力の文字列の配列の長さがたりてないんだけど,通れば正義だよね)

E. Palisection

読んでない….

Result

Cは結構通した人少ないみたい.
なんか赤くなりました.あんまり赤維持できる気がしないけど,頑張ろう.

コメント

[C50] Hi

おめでとうございます. このコンテスト後で挑戦してみたがは意外に難しく感じました.難易度が高いコンテストにRedCoderになれることはすごいと思いました.

[C51]

ありがとうございます.
今回のは3問目以降は普通に難しかったと思います.
なんとか赤のままでいられるように頑張りたいですね・・・.
  • 2010-06-11 16:41
  • rsujskf
  • URL
  • 編集

[C52]

> a^(phi(b)+1) = a (mod b)
これは偽みたいで (a=3, b=18など) 、

a^(phi(b)+k) = a^k (mod b)
でkが十分大きい (log bで十分) なら成り立つようです。
  • 2010-06-11 19:25
  • hos
  • URL
  • 編集

[C53]

> hos様
あ,あれ…,本当ですね,ごめんなさい.
なんで成り立つと思っていたんだろう…,ずっと勘違いしてました.
指摘ありがとうございます.
訂正しておきます.
(使うときは大抵k=phi(b)としてプログラミングしてました,今回は手を抜きましたが)
  • 2010-06-11 19:51
  • rsujskf
  • URL
  • 編集

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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