Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2011年01月26日01時から2時間,5問.codeforcesルール
[ LINK ]

A. Square Earth?

1辺の長さがn (1000以下) の正方形の周上の2点のx,y座標が与えられる.
周上しか移動できないとして,2点間の距離を求める問題.

DQみたいにトーラス世界での距離を求める問題?
いや,サンプル見る限り違うな….
ああ,周上しか移動できないんだ.
書くだけだ.
原点から反時計回りに移動するのにかかる距離に変換して,引いて,周の半分より大きければ周 - 距離に補正…と.
サブミット.

B. Martian Architecture

n個 (100000以下) の箱があって,最初は空.
m回 (100000以下) の操作を行う.
 箱番号aにx個石を入れて,箱番号a+1にx+1個石を入れて,…,箱番号bにx+b-a個石を入れる (xは1000以下)
k個 (100個以下) の箱番号が与えられて,その箱に入っている石の数の合計を求める問題.

うーん,問題が読みにくい.けど,なんとなく理解.
愚直にシミュレーションしたら間に合わないしなぁ….
どうにかやってうまく求めれるはず.
….
あれ?
kが小さいから,選ばれた箱だけ全部計算したら間に合うんじゃ….
書く.間に合いそう.サブミット.
(もちろんうまく計算する方法もあります)

C. Array

nが与えられる.(nは100000以下)
要素数nの数列で,各要素1以上n以下で,単調非減少,または単調非増加なものは何通りあるかmod 1000000007で求める問題.

問題の意味が分からない.
あ,わかった.
えっと,普通にDPやったら,O(n^2)でダメだよなぁ….
とりあえず,包除原理で,単調非減少のもの + 単調非増加なもの - 全部同じ数のもの が答えになる.
から,単調非減少だけ求めればOK.
うーん.普通にコンビネーションで求めれそうだ.
どこで1増やすか,と考えると普通に重複組合せの数だ.
書く.
サンプル合った.サブミット.

D. Journey

n*m (1000*1000以下) のグリッドが与えられる.
ところどころに障害物がある.上下左右に動ける.
障害物のない場所で,ランダムに始点と終点 (始点と終点は同じでも良い) を選んだとき,その2点間の最小距離の平均値を求める問題.
障害物は,各行,各列にはたかだか1個までしかなく,障害物は斜めに接していることはない.

はてさて,そんなに難しくなさそうだが….
単純に始点と終点が同じ行か列に選ばれて,その間に障害物があるときのみ2だけ迂回しないとダメで,ほかはマンハッタン距離でいいのでは.
マンハッタン距離の平均はとりあえず求めておいて損はない.
書く.
行と列に分離して求める.がりがり.
あとは,同じ行に選ばれて,その間に障害物がある確率とか求めて足す.
がりがり.
サンプル通った.
こんなに簡単でいいのか…?
まぁ,自信ないけどサブミット.
最後数分ぐらいでHackされた.するんだったらもう少し早くやってよ!
うーん,考える.
あ,なるほど.

 S...X...
 ......XT

Sが始点,Tが終点,Xが障害物.
とかでも迂回しないとダメ.
うおおおおお.修正ー.
直った,サブミット!pre test WA.時間切れ.

E. Chess

障害物のある無限に広いチェス盤が与えられる.
障害物は座標の絶対値が10以下の部分にしか無い.
原点からナイトがKターン以内で辿りつけるマスの数をmod 1000000007求める問題.
Kは10^18以下.

原点付近にしか障害物がないから,原点付近を全探索して,あとは適当に….
って,何となく思うけど,ちゃんとやろうとすると全然わからないよ?
うーん,諦めよう.

Hacks

Cで,茸さんが勘違いしてるっぽかったのでとりあえず落としておく.
あとは,なんか (res*2 - n)%mod みたいなことして,マイナスになりそうな人がいた.
マイナスになるケースを全探索して探して落とす.
次々マイナスになるコードがサブミットされてくる….
片っ端から落とす.
A問題でコード誤読して1失敗.
合計5成功1失敗.

Results

ABCは無難に通る.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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