Entries

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

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

SRM507 DIV2 EASY - CubeAnts (この記事を編集する[管理者用])

Source

TopCoder SRM507 DIV2 EASY (250pt)
Problem Statement
SRM507 DIV1 自分の参加記録

問題概要

問題文の図のように,立方体の頂点に番号をつける.
蟻が50匹以下いて,現在蟻がいる頂点番号が与えられる.
それぞれの蟻は時間1で,隣の頂点に移動する,もしくは,現在の位置に留まることができる.
全ての蟻が頂点0に移動するための最小時間を求める問題.

解法

最も遠い蟻までの距離.

C++によるスパゲッティなソースコード

続きを読む

SRM507 DIV1 EASY/DIV2 MEDIUM - CubeStickers (この記事を編集する[管理者用])

Source

TopCoder SRM507 DIV1 EASY (250pt)
TopCoder SRM507 DIV2 MEDIUM (500pt)
Problem Statement
SRM507 DIV1 自分の参加記録

問題概要

6個以上50個以下の同じサイズの正方形がある.その色が与えられる.
立方体を1個作りたいのだけど,隣り合う面の色は異なるようにしたい.
そのようにできるか判定する問題.

解法

同じ色が2個以上あっても,2個までしか使えない.
後は,使えるのが6個以上あれば作れる.

C++によるスパゲッティなソースコード

続きを読む

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

2011年05月29日01時02分から.
[TopCoder summary]

・EASY (解いた)
これは問題なく解いたが,文字列とかmapとか扱いに慣れてなさすぎる.
・MEDIUM (解けなかった)
全然思いつかなかった.
底面だけ考えて2次元だと思ってたのが敗因.3次元をイメージできるようになりましょう.
2次元で,実は考えなくても良いパターンがたくさんあるのでは,とか難しいことを考えすぎた.
ループを回して,最後だけ回さない,って典型的なやつではないですか!
・HARD (Failed System Test / TLE)
DPやるだけだと思ってやったら,計算量が怪しい感じに.
途中で,見える色以外の2つは区別せずに求めて,最後にコンビネーションをかければいいことに気づいて,計算量を1段階落とす.
それでも,微妙にTLE.
が,24,24,24,24とかなら通るし,25,24,24,25とかでも通るので,通らない一部のケースだけ埋め込めばいいんじゃないかと思ったけど,時間切れで埋め込み不足になった.
23,24,25,25が意外と時間掛かってTLE,ってのは確かに言われればそのとおりなんだけど,24,24,25,25が通るので,通ると思い込んでたので,どっちみち時間があってもTLEで死亡してた模様.
・Challenge
成績悪すぎて,どうでも良い感じだったので,適当にチャレンジして2失敗.
・DIV2 EASY (TopCoderニコ生占い [診断人さんのコミュ] )
サンプル通るの確かめずに特攻したけど,合ってて良かった.失敗覚悟だった.

Open 2011 Algorithm Qual. 3 HARD - ComplementMachine2D (この記事を編集する[管理者用])

Source

TopCoder Open 2011 Algorithm Qualification Round 3 HARD (1000pt)
Problem Statement
TopCoderニコ生オープン TCO11 Qual. 3 自分の参加記録

問題概要

01のみからなる行列で,以下の操作を考える.
 ある行より上の行に含まれる全ての要素の01を反転させる
 ある行より下の行に含まれる全ての要素の01を反転させる
 ある列より右の列に含まれる全ての要素の01を反転させる
 ある列より左の列に含まれる全ての要素の01を反転させる
この操作を繰り返して,全ての要素が0にできる行列をerasableと呼ぶ.
40*40以下の行列が与えられるので,そのerasableな部分行列の中で要素数の最大値を求める問題.
部分行列とは,行列から,最初の数行,最初の数列,最後の数行,最後の数列を取り去った行列.

解法

いくつかの行,列をブロックとみなして,市松模様っぽくなっていれば可能.
それを愚直に,全ての部分行列に対して判定してやるとO(N^6)になるが,これでもぎりぎり通る.(以下のコード)
オーダーを落とす方法としては,行の範囲は全探索するとして,列は始点のみ決めてやる.
市松模様になっている,とは,前の列と比べて,全てが一致するか,全てが反転していればOKなので,そうなってる範囲調べれば良い.
これで,列の終点のループが減ってO(N^5).
後は,列の始点も尺取メソッドで,一致しなかった場所まで一気に進めれば良いので,O(N^4).
全てが一致するか反転するか,というのは,ビット演算を使えばO(1)でできて,O(N^3).
だが…,O(N^5)なら余裕で通るので,それ以上に頑張る必要はない.

C++によるスパゲッティなソースコード

続きを読む

Open 2011 Algorithm Qual. 3 MEDIUM - CoinMachinesGame (この記事を編集する[管理者用])

Source

TopCoder Open 2011 Algorithm Qualification Round 3 MEDIUM (500pt)
Problem Statement
TopCoderニコ生オープン TCO11 Qual. 3 自分の参加記録

問題概要

アーケードゲーム機がN個 (50以下) ある.
最初コインをC個 (10^9以下) 持っている.
それぞれのアーケードゲームをプレイするに当たって,最初に必要なコインの数,最後に帰ってくるコインの数が与えられる.
帰ってくるコインの数は,最初に必要なコインの数より厳密に小さい.
同じゲーム機を何回もプレイして良いので,最大で何回ゲームをプレイ出来るかを求める問題.

解法

プレイできるゲームの中で,賞味の消費コイン (必要コイン-帰ってくるコイン) が少ない方からプレイすれば良い.
単純に,1回プレイごとにシミュレーションするとTLEになるので,プレイできる回数を求めて,一気に処理する.

C++によるスパゲッティなソースコード

続きを読む

Open 2011 Algorithm Qual. 3 EASY - AllButOneDivisor (この記事を編集する[管理者用])

Source

TopCoder Open 2011 Algorithm Qualification Round 3 EASY (250pt)
Problem Statement
TopCoderニコ生オープン TCO11 Qual. 3 自分の参加記録

問題概要

1以上15以下の整数がK個 (6以下) 与えられる.
その中に,約数がちょうどK-1個含まれるような,最小の正整数を求める問題.
存在しないならそれを指摘する.

解法

約数に含まれない1個を総当たりして,その他の数字のLCMを求めて,それが約数に含まれないので割り切れなければ,答えの候補.
その中で最小値をとれば良い.
が,答えの上限は,15^5ぐらいなわけで,答えを総当りで調べても良い.以下のコードは答え総当り.

C++によるスパゲッティなソースコード

続きを読む

TopCoderニコ生オープン TCO11 Qual. 3 参加記録 (この記事を編集する[管理者用])

TopCoder Open 2011 Algorithm Qualification Round 3は2011年05月25日10時02分から.
TopCoderニコ生オープンは2011年05月25日22時20分から.
[TopCoder summary] [TopCoderニコ生オープンのコミュニティ]

Qual. 3だけあって,流石にちょっと簡単になった.

・EASY (解いた)
答えの上限もちゃんと見積もらず,制限時間の足りるぐらいに,全探索した.
例外の1個を全部試して,他のLCMがそれで割り切れなければ答え候補,ってのがある意味王道なんだろうけど,TopCoder的には答え全探索が楽でいいと思う.
が,上限もちゃんと見積もらないとか,罠がないか考えてないわけで,もうちょっと考えるべきだとは思う….
・MEDIUM (解いた)
greedy.ソートで躓いて時間ロス.なにやってるの….
・HARD (解いた)
O(N^6)で,しかも一番愚直なので解いた.ケアレスミスでちょっとはまった.
もうちょっと整理したらもっと簡単にかけただろうし,O(N^5)には落とせるはず.(実際書く前にO(N^6)はかなり怪しいと思ってしまう)

Open 2011 Algorithm Qual. 2 HARD - FoxIntegerLevelThree (この記事を編集する[管理者用])

Source

TopCoder Open 2011 Algorithm Qualification Round 2 HARD (1000pt)
Problem Statement
TopCoderニコ生オープン TCO11 Qual. 2 自分の参加記録

問題概要

 s(n) := nを10進数で書いたときの各桁の和
 d(n) := s(s(…(n)…))と1桁になるまでsをnにかましてできる整数
とする.
区間[a,b]内の整数xで
 x = y * d(y)
となるyが存在する物の数を求める問題.
a, bは10^10以下.

解法

まず,s(n)は単にmod 9とほとんど同じ.(mod 9が0なら9になるだけ)
後は,xが条件を満たすとは,
 1以上9以下整数kが存在して,x/kが整数で,x/kがmod 9でkに等しい
ということ.
よって,kで割り切れるか,というのは2520=LCM(1,2,...,9)周期で,さらに,割った物がmod 9でどうなるかを考えると,
2520*9の周期性があることがわかる.(xが条件を満たすならx+2520*9も条件を満たす)

C++によるスパゲッティなソースコード

続きを読む

Open 2011 Algorithm Qual. 2 MEDIUM - KindAndCruel (この記事を編集する[管理者用])

Source

TopCoder Open 2011 Algorithm Qualification Round 2 MEDIUM (500pt)
Problem Statement
TopCoderニコ生オープン TCO11 Qual. 2 自分の参加記録

問題概要

1次元のマップが与えられる.
左端から右端に移動する最短時間を求める問題.
左端と右端には何もなく,1ターンで左右1マスに移動するか,現在場所にとどまることができる.
マップの各マスには,モンスター1とモンスター2がいることがある.
モンスター1は現在時間がKで割り切れるときのみ通ることができない.
モンスター2は現在時間がCで割り切れるときのみ通ることができる.
マップのサイズは50マス以下,KとCは50以下.

解法

現在時刻のmod LCM(K,C)と現在場所を状態としてBFSする.

C++によるスパゲッティなソースコード

続きを読む

Open 2011 Algorithm Qual. 2 EASY - BlackWhiteMagic (この記事を編集する[管理者用])

Source

TopCoder Open 2011 Algorithm Qualification Round 2 EASY (250pt)
Problem Statement
TopCoderニコ生オープン TCO11 Qual. 2 自分の参加記録

問題概要

WとBからなる50文字以下の文字列が与えられる.
全ての正整数kに対して,距離kの2文字をスワップすることが1回だけできる.
WW…WBB…BをWを初めに,Bを終わりにするための最小スワップ回数を求める問題.
不可能ならばそれを指摘する.

解法

最も遠い組み合わせからスワップすると考えると絶対可能であることがわかる.
また,同じ距離のスワップが2回使えないことを考えなくても,最小回数は変わらない.

C++によるスパゲッティなソースコード

続きを読む

TopCoderニコ生オープン TCO11 Qual. 2 参加記録 (この記事を編集する[管理者用])

TopCoder Open 2011 Algorithm Qualification Round 2は2011年05月19日20時02分から.
TopCoderニコ生オープンは2011年05月19日22時20分から.
[TopCoder summary] [TopCoderニコ生オープンのコミュニティ]

参加記録書くのが追いついていないので今回から省エネモード.

去年までTCO Qual.ってDIV2相当ぐらいの難易度だったと思うのだけど,今年はDIV1とDIV2の中間ぐらいで難しい.
一捻りある問題が出題されてる.

・EASY (解いた)
問題をちゃんと読め.結果的に良かったけど同じ距離のスワップは2回使えないとか見逃して,提出した後に気づいている
・MEDIUM (解いた)
問題をちゃんと読め.モンスターCも割り切れるときに通れないと勘違い.後は時間の経過の処理がわからず.
・HARD (解けなかった)
混乱しすぎ.もうちょっと頭の中を整理するべきだった….でもこれはしょうがない気もする.

SRM504.5 DIV1 HARD - TheTicketsDivOne (この記事を編集する[管理者用])

Source

TopCoder SRM504.5 DIV1 HARD (900pt)
Problem Statement
SRM504.5 DIV1 自分の参加記録

問題概要

N人 (1000以下) が一列に並んでいて,自分は先頭からM番目にいる.
以下の操作によって,1人を選ぶとき,自分が選ばれる確率を求める問題.
 列に1人しかいなければ,その人を選ぶ.
 そうでなければ,サイコロを振って,
  4がでれば,先頭の人を選んで終了
  2か6がでれば,先頭の人は選ばれなかったとして,権利をなくす
  1か3か5がでれば,先頭の人は一番後ろに並びなおす

解法

ループのあるDP.
NとMを状態として,O(N^2)のDPとなる.
あまりに後ろに並んでいる人はほとんど選ばれることはないので,ループは真面目に解決しなくても,適当に収束するまで100回程度ガウスザイデルっぽく計算しても通る.
以下のコードは,自分が先頭で,自分以外にN人いるときに自分が選ばれる確率でDPしている.
真面目にコンビネーションを計算するとdoubleでもオーバーフローするので,logを取って回避している.

C++によるスパゲッティなソースコード

続きを読む

SRM504.5 DIV1 MEDIUM - TheJackpotDivOne (この記事を編集する[管理者用])

Source

TopCoder SRM504.5 DIV1 MEDIUM (550pt)
Problem Statement
SRM504.5 DIV1 自分の参加記録

問題概要

N人 (47以下) の所持金 (それぞれ10^18以下) が与えられる.
自分の所持金M (10^18)も与えられる.
以下の操作を自分の所持金が尽きるまで繰り返したとき,N人の所持金をソートして返す問題.
 現在のN人の所持金の平均値より大きい最小の整数をZとする
 N人の中で最も所持金の少ない人が,所持金Zになるか,自分の所持金が尽きるまで渡す

解法

全員の所持金が等しくなったら,後は,1ずつ分配していくのだから,等しく分配すれば良い.
それまでのステップ数は実はたかだか3~4万ステップ程度なのでシミュレーションできる.

C++によるスパゲッティなソースコード

続きを読む

SRM504.5 DIV1 EASY/DIV2 MEDIUM - TheNumbersWithLuckyLastDigit (この記事を編集する[管理者用])

Source

TopCoder SRM504.5 DIV1 EASY (250pt)
TopCoder SRM504.5 DIV2 MEDIUM (500pt)
Problem Statement
SRM504.5 DIV1 自分の参加記録

問題概要

下1桁が4または7の正整数をラッキーな数字という.
N (1以上10^9以下) をラッキーな数字の和で書くとき,最小でいくつのラッキーな数字の和で書くことができるかを求める問題.

解法

10の倍数は自由に加えることができるので,基本的には下1桁のみで決まる.
ただし,数字が小さいうちは作れないこともある.
使う4の数や7の数は多く無いので,使う4の数,7の数で全探索する.
以下のコードは,DPで求めている.

C++によるスパゲッティなソースコード

続きを読む

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

2011年05月18日00時02分から.
[summary]

Assignment

SRM504がサーバ不調でノーコンテストになったので,その補填コンテスト.
日本人2名ぐらいと同じ部屋.
250-550-900と不穏な点数の問題セット.

EASY

下1桁が4または7の正整数をラッキーな数字という.
N (1以上10^9以下) をラッキーな数字の和で書くとき,最小でいくつのラッキーな数字の和で書くことができるかを求める問題.

簡単そう.
10の倍数を加えることがいくらでもできるので,小さい範囲で求めれれば良さそう.
4と7しか使えないとして,1000までDPで求める.
後は,Nを10引きながら,DP[N],DP[N-10],DP[N-20],・・・の最小値が答えでいいよね.
しかし,もしかしたら間に合うかもしれないけど,10引いていくと1億回計算するので・・・.
Nが1000以上なら1000引いていって,残りから10引いていくようにしよう.
書いた書いた.
サンプル通過したけど,色々自信なかったので,テストする.
1013の時,-1になる…,1000引いて13をチェックしてるから…,駄目じゃん.
てか,それでいいならmod 1000とればいいので,1000引いていくのは,それじゃダメだからそうしたんだろ!
2000以上のとき1000引いていってください….
修正.
もうちょっといろいろテスト.
最大ケースで間に合うよな?
N=1000000000のとき,答え0….は?
ああああ,N=0なら0個の和とか頭悪いことしてるのか.
修正.
もう大丈夫そうなのでサブミット.

MEDIUM

N人 (47以下) の所持金 (それぞれ10^18以下) が与えられる.
自分の所持金M (10^18)も与えられる.
以下の操作を自分の所持金が尽きるまで繰り返したとき,N人の所持金をソートして返す問題.
 現在のN人の所持金の平均値より大きい最小の整数をZとする
 N人の中で最も所持金の少ない人が,所持金Zになるか,自分の所持金が尽きるまで渡す

さて,550だし,ゆっくりでもいいから確実に解くぞ.
やっぱり,全然方針がわからん.
…,が,これ,別にシミュレーションしても大丈夫な気もするが….
そんなわけないよな.
まぁ,答え検証器にもなるし,とりあえずシミュレーション書く.
その前に,なんで,入力足すだけでlong longでオーバーフローするんだよ….
単なる嫌がらせ以外の何者でもないがな…,でもこういう子どもっぽい引っ掛けもTopCoder.
…,いや,でも,なんか,どうやって書けばいいんだ?
big integer貼り付けるか…?
と思ったけど,あまりにもあんまりなんで思いとどまる.
 div += in[i] / n
 mod += in[i] % n
で最後に
 div += mod / n
とかしてみた.
後は,シミュレーション書くだけ.
で,流石に,全員の所持金が等しくなったら,一気にスキップさせる.
書いた.
さて,最悪ケースではTLEするよな?
これが最悪かな…というのを探る….
….
……….
全部間に合うな….最悪でも300msぐらい.
取り敢えず提出….
いろいろテストする….大丈夫っぽいんだが….
HARDいこ….

HARD

N人 (1000以下) が一列に並んでいて,自分は先頭からM番目にいる.
以下の操作によって,1人を選ぶとき,自分が選ばれる確率を求める問題.
 列に1人しかいなければ,その人を選ぶ.
 そうでなければ,サイコロを振って,
  4がでれば,先頭の人を選んで終了
  2か6がでれば,先頭の人は選ばれなかったとして,権利をなくす
  1か3か5がでれば,先頭の人は一番後ろに並びなおす

何人かに瞬殺されてる.900だから多少簡単なんだろうけど….
問題読む.
へ,すごい簡単なんじゃ?
えっと,N,MでDP…すると,O(N^3)になりそうな気もするな.(うまくやればO(N^2)でできるしこっちのほうが楽だった)
えっと,えっと,自分が先頭にいて,合計N人いるときの選ばれる確率でDPすればO(N^2)でいけるよな.
コンビネーションとか色々計算するとき,doubleでもオーバーフローするよな.
(師匠が,GCJ 2011 予選のD問題でコンビネーション計算してオーバーフローして落ちてたので間違いない)
ってことで,全部log取って計算して,最後にexpかまして戻す.
めんどくさい….
書いた.合わない.
えー.
添字が1ズレてるとか,色々やらかしてた.修正するのに時間かかった.
サンプルあって,N=1000も問題なく動いているように見えたので提出.遅いorz

Challenge

MEDIUMはオーバーフローしてたり,怪しいことしてる人とか,色々いそう.
HARDもコンビネーション計算してオーバーフローしてる人がいそう.
EASYは…,これはまあ,みんな大丈夫だろう.
まぁ,HARDから見ていくかな.
…,開始!
誰もコンビネーションとか使ってねぇ!
てか,皆コード短いな,何やってるんだ….
と思ってるうちに,EASYとかMEDIUMがぞくぞく落ちていく.
へ,てか,なんでEASY落ちてるの??
見ても分からん.てか,4使う回数と7使う回数でループしてる人賢すぎる.
MEDIUMを見ていく.
long longのオーバーフローとかは粗方落とされてて,みんな良さそうに見える.
あ,これ,long longで和計算してるからオーバーフローするんじゃない?
落とせた.
(実は,後で確認するとlong doubleで計算していたけど,最大近くのランダムケースいれたので落ちた)
(10^18を47とかの最大ケースだと落ちなかったらしい,怖い怖い…)
後は,見てるだけしかできなかった.

System tests

全部通った.
250のチャレンジポイントは下1桁が0のとき,0を返す人がいたという物.
てか,自分も1回それに嵌ってテストケース色々試して気づいたのだから,それを他の人がやることだって十分あることを理解しろ!
900はO(N^2)のDPでももっと賢い方法あるし,O(N^2)を100回ぐらいループ回してガウスザイデルっぽくやるだけでも通ったらしい.
いくらなんでも簡単すぎるセットな気がするけど,補填コンテストなのでしょうがないのかなぁ?
ちなみに,550のlong longのオーバーフローは,あまりにもくだらない引っ掛けで,皆怒り心頭してたけど,個人的には嫌いじゃない.

UVa 12018 - Juice Extractor (この記事を編集する[管理者用])

Source

Celebration for the 106th Anniversary of Fudan University (1905-2011) & Warmup for ACM/ICPC 2011 World Finals (2011-05-15) (blog)
UVa 12018

問題概要

フルーツ狩りゲームの最大スコアを求める問題.
N個 (1000以下) の果物の出現時間と消滅時間が与えられる.
好きな回数だけ,好きな時間に,「果物を取る」ことができる.
「果物を取る」と,今,出現している果物が全部消え,その際,同時に3つ以上の果物が消えると,消えた数だけスコアが増える.

解法

出現時間でフルーツをソートしてDPする.
その際,現れたフルーツを,消える時間をキーにしてヒープに入れていって,消える時間より先に進める場合は取り出していくと,
切るときに,ヒープに入ってる数が画面上にあるフルーツの数になる.
O(N^2 log N).

UVa 12017 - Imitation (この記事を編集する[管理者用])

Source

Celebration for the 106th Anniversary of Fudan University (1905-2011) & Warmup for ACM/ICPC 2011 World Finals (2011-05-15) (blog)
UVa 12017

問題概要

有向グラフが与えられる.
そのグラフにおいて,ノードaからノードbに移動できる,という性質を全て保ったまま枝を追加したり削除したりできる.
最終的なグラフの枝数の最小値と最大値を求める問題.
ノード数は1000以下,枝数は10000以下.

解法

まず,強連結成分分解する.
連結成分の中は,
 最小値:ノード数が1なら何もしない,そうでなければノード数だけ枝を使って閉路を作る
 最大値:完全グラフにする
とすれば良い.
後は,DPして,その連結成分から辿りつける連結成分を求めて,最小になるように,最大になるように枝をはれば良い.
愚直にやるとO(N^3)になるので,色々工夫したけどやっぱり最悪だとO(N^3)になりそうなコードで通った.
あんまり工夫しなくてもいけたのかも?

UVa 12016 - Herbicide (この記事を編集する[管理者用])

Source

Celebration for the 106th Anniversary of Fudan University (1905-2011) & Warmup for ACM/ICPC 2011 World Finals (2011-05-15) (blog)
UVa 12016

問題概要

2次元平面上のN点 (1000以下) が与えられる.
Q個 (1000以下) のクエリに答える問題.
各クエリでは,N個のうちのいくつかを頂点として作られた,S角形が与えられるので,
N個の点のうち,その多角形の内部もしくは周上にある点の数を求める問題.

解法

まず,適当に回転とかして,同じx座標の点をなくす.
N点をx座標の値でソートして,多角形の線分も左端のx座標の位置でソートとかしておく.
後は,尺取メソッドみたいに,その点の上にある多角形の線分の数が偶数か奇数かを求めてやる.
最悪ケースだとO(N^3)になりそうだけど,まぁ,通る.

UVa 12015 - Google is Feeling Lucky (この記事を編集する[管理者用])

Source

Celebration for the 106th Anniversary of Fudan University (1905-2011) & Warmup for ACM/ICPC 2011 World Finals (2011-05-15) (blog)
UVa 12015

問題概要

10個のURLと,それに対応する整数が与えられる.
最も大きい整数に対応するURLを求める問題.
複数あるなら全部出力する.(入力で先に来たものを先に出力する)

解法

流石にやるだけ.

UVa 12014 - Fudan Extracurricular Lives (この記事を編集する[管理者用])

Source

Celebration for the 106th Anniversary of Fudan University (1905-2011) & Warmup for ACM/ICPC 2011 World Finals (2011-05-15) (blog)
UVa 12014

問題概要

四川麻雀で現在の状態が与えられる.
1つ加えてあがれる牌を列挙して,その時の点数も求める問題.(すでに4枚使ってるものは考えない)
四川麻雀については問題文参照だが,簡単に書いておく.
 マンズ,ピンズ,ソーズのみ(字牌はない)
 3種類の牌が全部含まれてるとあがれない(絶一門にする必要がある)
 上がるには,4面子+1対子,または7対子.
 役と点数は以下
 ・基本点(あがればもらえる)1点
 ・4枚同じ種類の牌がある 種類数×1点
 ・7対子 2点 (同じ牌が4枚あるものも2組とみなして良い)
 ・清一色 2点
 ・チートイツでなく,順子がない 1点,さらに2・5・8しかないと更に2点
 ・全ての面子,対子に1か9が含まれている 2点
ポン,カンしてるものは刻子とみなさなければいけない.
面子の分け方など,複数の可能性がある場合,最も点数が高いものを採用する.

解法

全ての牌の区切り方を調べてやるだけ.

UVa 12013 - Entertainment (この記事を編集する[管理者用])

Source

Celebration for the 106th Anniversary of Fudan University (1905-2011) & Warmup for ACM/ICPC 2011 World Finals (2011-05-15) (blog)
UVa 12013

問題概要

テニスをする.
自分のサーブの時の1ポイント取れる確率,自分がサーブでないときの1ポイント取れる確率が与えられる.
3セット取って,勝つ確率を求める問題.
テニスのルールは…,
 4ポイント取ると1ゲーム獲得.ただし2ポイント以上差をつけなければいけない
 6ゲーム取ると1セット獲得.ただし2ゲーム以上差をつけなければいけない
 3セット取ると勝利.
 同じゲームの間はサーブ権は変わらない.ゲームが終わるとサーブ権が変わる.
最初のゲームのサーブ権は自分.

解法

漸化式をたてて.線形方程式を解きまくる.
が,あまりに,愚直にやるとTLEした.
実は,最初のサーブ権がどっちにあっても勝率は変わらないとか,ある程度50%50%より高いと最終的には100%勝てるとかいうのは計算せずに返しちゃうとか,そういうのをやると通った.

UVa 12012 - Detection of Extraterrestrial (この記事を編集する[管理者用])

Source

Celebration for the 106th Anniversary of Fudan University (1905-2011) & Warmup for ACM/ICPC 2011 World Finals (2011-05-15) (blog)
UVa 12012

問題概要

LEN文字 (1000以下) の文字列Xが与えられる.
1以上LEN以下の全ての整数kに対して,
 Xの部分文字列で同じ文字列をk回繰り返した文字列で,最長のものの長さ
を求める問題.

解法

s文字をセットにして,s文字飛ばしに見て一致する最大長を求める,というのを全てのsに対してやる.
rolling hashを使うと,s文字をセットにする部分は,s文字セットのハッシュを使えばよくて,それはs-1文字セットのから求めれる.
O(LEN^2).

UVa 12011 - Complete the Set (この記事を編集する[管理者用])

Source

Celebration for the 106th Anniversary of Fudan University (1905-2011) & Warmup for ACM/ICPC 2011 World Finals (2011-05-15) (blog)
UVa 12011

問題概要

0以上2^16未満の整数の集合が与えられる.
OR,AND演算で閉じるためには,最小でいくつの要素を追加すればよいかを求める問題.

解法

正しいのかどうかよく分からない回答で通った.
まず,入力の全部のORを取ってできる数字,ANDを取ってできる数字が入ってなければ追加する.
後は,全ての数字に対して作れるかどうかを判定する.
異なる2桁のビット情報を見て,それと一致するのがもともとの集合に含まれてなければ作れない,それ以外は作れる.
なので,全ての桁の組に対して出現するビット情報を最初にメモしておく.
O(16^2*2^16).

UVa 12010 - Boring Homework (この記事を編集する[管理者用])

Source

Celebration for the 106th Anniversary of Fudan University (1905-2011) & Warmup for ACM/ICPC 2011 World Finals (2011-05-15) (blog)
UVa 12010

問題概要

N個 (80以下) の異なる整数 (1~Nまで) を順番に二分探索木に突っ込む.
その時の木の形のアスキーアートを出力する問題.

解法

木を作ってお絵かきするだけ.

UVa 12009 - Avaricious Maryanna (この記事を編集する[管理者用])

Source

Celebration for the 106th Anniversary of Fudan University (1905-2011) & Warmup for ACM/ICPC 2011 World Finals (2011-05-15) (blog)
UVa 12009

問題概要

入力は500以下の整数N.
N桁の非負整数Xで,任意の正整数kに対して X^k の下N桁がXになるものを列挙する問題.

解法

Nが2以上の時,答えは高々2つしかなくて,それはNが十分でかい時の答えの下N桁を取ってくれば良い.
N=500の時まで計算して,答えを埋め込んだ.

Celebration for the 106th Anniversary of Fudan University (1905-2011) & Warmup for ACM/ICPC 2011 World Finals (この記事を編集する[管理者用])

2011年05月15日18時から5時間or24時間,10問.
[ Link ]

見た目簡単そうなセットだったけど,意外とそうでもなかった.
5時間では間に合わなかったけど,最終的には全部解いた.

・問題A (解いた)
埋め込んだけど,いいんだよね…?
・問題C (解いた)
嘘解法っぽいので通してしまったかもしれない.正しいのかな?
・問題E (解いた)
最初収束するまで回すとかやって駄目だった.
連立一次方程式にしたけど,TLE.
なので,丸めると,明らかに確率が0とか1になる場合は,問答無用でそれを返してたのだけど,
その時,%で返すはずが1を返してて1%とかなってて死んでた.
ちょっと酷すぎるミス.
・問題F (解いた)
絶一門状態じゃないと上がれないのを読み落として苦戦.
それ以外はやるだけだし,意外と実装も大変じゃない.
が,取り敢えず,問題文が長すぎるのが大変.
・問題J (解いた)
最初,問題の意味を勘違いしてた.その後,3つ以上でポイントが2つ以上と勘違いしてた.
heap使ってDPした.O(N^2 log N).
同じタイミングに出現するフルーツの処理を忘れててWAをもらった.

UVa 12008 - Emotional Bishop (この記事を編集する[管理者用])

Source

World Finals Warmup II (2011-05-07) (blog)
UVa 12008

問題概要

サイズ R*C (10^9 * 10^9以下) のチェス盤の上で,ある場所からある場所にビショップが移動する最短ターン数を求める問題.
不可能ならそれを指摘する.ビショップは斜めにいくらでも動けるコマ.

解法

まず,x+yの偶奇が違うと不可能.
1手で行けるケースは例外処理として書いておく.
後は,基本的に,短い辺の方端までいって,もう片方の端まで移動しながら,どんどん進んでいく感じ.
で,行き過ぎたら,適当に調整できるので,どれだけいけば行き過ぎれるかを求める.

UVa 12005 - Find Solutions (この記事を編集する[管理者用])

Source

World Finals Warmup II (2011-05-07) (blog)
UVa 12005

問題概要

c (10^14以下) が与えられるので,
 c = ab + (a+b)/2 + 1
の整数解(a,b)の数を求める問題.

解法

 4c-3 = (2a+1)(2b+1)
とかになるので,4c-3を素因数分解して,2つに分ける分け方を求める.

UVa 12004 - Bubble Sort (この記事を編集する[管理者用])

Source

World Finals Warmup II (2011-05-07) (blog)
UVa 12004

問題概要

ランダムな1~Nのpermutationをバブルソートするとき,swapされる数の期待値を求める問題.(分数の形で求める)
Nは100000以下.

解法

任意の2要素に関して,それらがスワップされる確率1/2.
後は期待値の線形性より,それを足すだけ.

UVa 12002 - Happy Birthday (この記事を編集する[管理者用])

Source

World Finals Warmup II (2011-05-07) (blog)
UVa 12002

問題概要

一直線上のテーブルに皿がN個 (500以下) 置かれている.
皿の大きさが与えられる.
テーブルを1回左から右に移動する際に,
 (1) 皿を無視する
 (2) 今,皿を持ってなければ,その皿を持つ
 (3) テーブルの皿が,今持っている一番上の皿のサイズと同じか小さければ,今持っている一番上の皿の上に追加できる
 (4) テーブルの皿が,今持っている一番下の皿のサイズと同じか大きければ,今持っている一番下の皿の下に追加できる
ということができる.
最高で何個の皿を持つことができるかを求める問題.

解法

最初に取る皿は全探索する.
後は,その皿より大きい物と小さい物に分けて,それぞれLIS (最長部分列) を求める.
最初の皿と同じサイズの皿を,大きいとみなすか,小さいとみなすかは両方試して良い方を採用した.

Appendix

Recent Articles

ブログ内検索

Ads


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