Entries

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

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

music typing (仮) (この記事を編集する[管理者用])

京都大学11月祭でひっそりと展示してた気がするけど,typing maniaっぽいタイピングゲーム.

本体 (mediafire / RAR自己解凍書庫 / 24MB)
Readme.txt

自分が遊ぶ時は版権曲のデータ作って適当に楽しんでます.
そのうち一般に公開できるような曲データ作りたいなぁ.

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

2009年11月26日01時から.

Assigment

普通っぽい部屋かな.
問題が250, 450, 1000の変則セット.
1000にじっくり時間をかけれそうなセットだ.

EASY

あからさまにBFSしてください,という問題….
実装あるのみ.サブミット.

MEDIUM

適当に使えるコスト列挙してDPにしか見えない.
瞬殺できるだろー.
平面グラフという条件を忘れていて,普通にエッジの数はn*(n-1)/2以下としてサブミットしてしまった.
平面グラフだった枝の数の最大値っていくらだ?
適当に絵を書いて考えてみる….
n=5で考えて,3n-6っぽい気がする….
n=4でもOK.n=6だと…自信ないけどあってるような….
3n-6でいいや,サブミット.

HARD

うーん…?
取り敢えず,ラッキーナンバーを列挙してみる.
これからどうするんだろう….
取り敢えず,ラッキーナンバーの中から,他の物の倍数になっているのは除外してみる.
でも,包除原理すると計算量2^1000を楽に越えるぞ.
いやいや,違う,数個使ったらB超えちゃうから,殆ど使えなくて,包除原理しても大した計算量にはならないはず!
書いてみた.よゆーで間に合う.サブミット.

MEDIUM

他にも完全グラフでやってる人いるから知れないからチャレンジケース作っておこう.
…あれ,挙動がおかしい….
条件で3*i-6と書くべきを3*n-6と書いてるorz
再々サブミット.最低点の135点….
完全グラフだと思ったときに間違うテストケースとして385をゲット.

ご飯

コーディング時間は後15分.
おなか減ったのでご飯食べよう.もぐもぐ.

Challenge

MEDIUMを片っ端から開く.
結構,使える枝の数の式間違えている人がいるぞー?
でも,もっと使えないと勘違いしてる人が多い…,そりゃそうだ.
そんなテストケース作ってねー….
急いで作る.206とか360とかでいけるのか?
とか思ってたうちに他の人に全部落とされちゃった….
ノード数が2のとき,例外処理してて枝数0を忘れている人がいたのでそれだけつつく.

System Tests

HARD落ちた….あれ?
MEDIUM連敗記録は脱出したけど,いつもより駄目な感じな結果.MEDIUM最低点だし.

追記 2009-11-26 03:40

HARD落ちた元凶はラッキーナンバーのリストの最後に100000000000LLを追加したこと.
GCDとれば,普通にカウントされるぐらいに小さかった….
通ってればHARD最速だったのになぁ…,とかまぁそういうのは良くありすぎるので,通すことが難しいのがよくわかる.

カラオケログ (この記事を編集する[管理者用])

2009.11.23 21:50頃--2009.11.24 05:00頃 DAM
2部屋,滞在時平均人数7.2人ぐらい.(最高9人,最低7人)

続きを読む

LiveArchive 4549 - The Robbery (この記事を編集する[管理者用])

Source

ACM/ICPC Europe - Southeastern - 2009/2010
LiveArchive 4549

問題概要

1~nの数字が書かれた宝石箱がある.
数字kの書かれた宝石箱には,重さW_k,価格C_kの宝石がk個入っている.
合計重さW以下で価格が最高になるように宝石を選ぶと,最高価格はいくらになるか.
nは15以下.その他は10^9以下.

解法

DPだと状態数が爆発するけど,良く考えれば全探索でも最高で16!通りしかない.
枝刈り探索で間に合った.

LiveArchive 4617 - Simple Polygon (この記事を編集する[管理者用])

Source

ACM/ICPC Europe - Northwestern - 2009/2010
Another Regional Contest (NWERC 2009, 2009-11-14) (blog)
LiveArchive 4617

問題概要

2次元平面上のn点が与えられる.(nは2000以下)
それを頂点とするような単純な多角形を1つ構成する問題.
角度が180度の点があっても良い.

解法

凸方を作る時みたいに,最も上の点を左から右になぞって,あとは使わなかった点を全部右から左に追加していった.
角度でソートして順番に使うなどでも良い.

LiveArchive 4616 - Settlers of Catan (この記事を編集する[管理者用])

Source

ACM/ICPC Europe - Northwestern - 2009/2010
Another Regional Contest (NWERC 2009, 2009-11-14) (blog)
LiveArchive 4616
PKU 3849 [問題名: Pirvate problem 20100801 H] (2010-10-02 09:45追加)

問題概要

六角格子に1~5までの数字を,ぐるぐると以下のように置いていく.
 隣り合った場所にある数字はおかない
 今まで置いた数の一番少ない数字を置く
 複数あるなら,小さい数字を置く
n番目に置いた数字を求める問題.nは10000以下.

解法

シミュレーション.実際においてみる.

LiveArchive 4614 - Moving to Nuremberg (この記事を編集する[管理者用])

Source

ACM/ICPC Europe - Northwestern - 2009/2010
Another Regional Contest (NWERC 2009, 2009-11-14) (blog)
LiveArchive 4614

問題概要

ノード数50000以下の木が与えられる.枝には距離が付与されている.
それぞれのノードkに訪れなくてはいけない回数d(k)が与えられて,
 Σ[iは全てのノード] xとiとの距離 * d(i)
が最小となるノードxを全て列挙する問題.

解法

DPする.O(n).

LiveArchive 4613 - Mountain Road (この記事を編集する[管理者用])

Source

ACM/ICPC Europe - Northwestern - 2009/2010
Another Regional Contest (NWERC 2009, 2009-11-14) (blog)
LiveArchive 4613
PKU 3846 [問題名: Pirvate problem 20100801 E] (2010-10-02 09:45追加)

問題概要

細い道がある.
左右から同時に車が進入するとぶつかるので,片方ずつしか進めない.
しかし,片方から2台進むときは,道の最中のどの点においても,10秒以上の間隔を空けなければいけない.
左右どちらに,時刻いつ辿り着いて,その車の最大スピードで道を進んだ場合の必要時間が与えられるので,全ての車が道を超えるまでの最小所要時間を求める問題.
車の数は200以下.

解法

どちら向きの車を走らせるかが決まっているなら,到着順に,出発できるならすぐ出発するのが最適.
最後にどちら側の車が通ったか,右側からきている車は後何台残っているか,左側は後何台か,を状態にDPする.
領域量O(n^2),計算量O(n^3).

LiveArchive 4612 - Fractal (この記事を編集する[管理者用])

Source

ACM/ICPC Europe - Northwestern - 2009/2010
Another Regional Contest (NWERC 2009, 2009-11-14) (blog)
LiveArchive 4612
PKU 3845 [問題名: Pirvate problem 20100801 D] (2010-10-02 09:45追加)

問題概要

2次元平面上の折れ線が与えられる.
深さ1のフラクタルはその折れ線自身.
深さdのフラクタルは,深さd-1のフラクタルの各線分を,適当に回転縮小して始点終点が合うようにして折れ線に置き換えたもの.
深さdのフラクタルで,始点から f*(深さdのフラクタルの長さ) の位置の座標を求める問題.

解法

2次元幾何実装問題.
長さが増えていく割合は一緒なので,再帰で,どこの線分に属しているかを判定していく.

LiveArchive 4611 - Divisible Subsequences (この記事を編集する[管理者用])

Source

ACM/ICPC Europe - Northwestern - 2009/2010
Another Regional Contest (NWERC 2009, 2009-11-14) (blog)
LiveArchive 4611
PKU 3844 [問題名: Pirvate problem 20100801 C] (2010-10-02 09:45追加)

問題概要

長さnの正整数列が与えられるので,その連続する部分列で,和がdで割り切れるものの数を求める問題.

解法

基本的な考え方はSPOJ 2150と同じでmod取るだけ.

LiveArchive 4609 - An Industrial Spy (この記事を編集する[管理者用])

Source

ACM/ICPC Europe - Northwestern - 2009/2010
Another Regional Contest (NWERC 2009, 2009-11-14) (blog)
LiveArchive 4609
PKU 3842 [問題名: Pirvate problem 20100801 A] (2010-10-02 09:45追加)

問題概要

7個以下の数字が与えられるので,その数字を使ってできる素数の数を求める問題.

解法

作れる数字を全部列挙して,素数であるかどうか判定するだけ.

LiveArchive 4610 - Common Subexpression Elimination (この記事を編集する[管理者用])

Source

ACM/ICPC Europe - Northwestern - 2009/2010
Another Regional Contest (NWERC 2009, 2009-11-14) (blog)
LiveArchive 4610

問題概要

ノード数50000以下の完全2分木が与えられる.ノードには文字列が付与されている.
枝を張りかえて,ノード数をできるだけ減らす問題.問題文の図を参照.

解法

どっちかいうと,文字列処理+実装問題.
グリーディーに減らせば良い.

SPOJ 2320 - Manhattan [DISTANCE] (この記事を編集する[管理者用])

Source

MIT 1st Team Contest 2007
SPOJ 2320 [DISTANCE]

問題概要

d次元上のn点の座標が与えられる.
マンハッタン距離で最も遠い2点間の距離を求める問題.

解法

例えば,6次元座標の点(a1,b1,c1,d1,e1,f1)と(a2,b2,c2,d2,e2,f2)のマンハッタン距離は
 x1 = a1 + b1 - c1 - d1 + e1 - f1
 x2 = a2 + b2 - c2 - d2 + e2 - f2
として|x1-x2|と同じかそれより小さい.
符号の付け方2^(d-1)通り全て試して,「足したり引いたりした値の最大値-最小値」の最大値が答えになる.

SPOJ 1881 - Instruction Decoder [ICODER] (この記事を編集する[管理者用])

Source

NITT ACM ICPC Local Contest 2007
SPOJ 1881 [ICODER]

問題概要

Xは最初は0から65535までのどれかの数.
以下の2種類ある命令をn個こなした後,取り得る数字の数を求める問題.
 ADD k → Xを(X+k)%65536変える
 MUL k → Xを(X*k)%65536変える

解法

ADD 3, MUL 4, ADD 5ならX → 4*(X+3)+5 = 4X+17という風に結局aX+bって形で書けるので最初にaとbを計算する.
後は全部試してみる.
ちなみにbは関係ないので考えなくても良い.

SPOJ 1419 - A Game with Numbers [NGM] (この記事を編集する[管理者用])

Source

ZCon 2007
SPOJ 1419 [NGM]

問題概要

2人でゲームを行う.
最初20億以下の数字が書かれている.
順番に,その数字(の10進数表示)に使われている0以外の数字を1つ選んで引いていく.
最初に0にした人が勝ち.
先手必勝か,後手必勝かを判定して,先手必勝の場合は,最初,いくら引けば勝てるかを求める問題.

解法

10の倍数で順番がまわってきたら負ける.
引く数字は1~9だから相手は10の倍数にならないし,相手は,1の桁の数字を引いて10の倍数にして送ってくる.

SPOJ 705 - New Distinct Substrings [SUBST1] (この記事を編集する[管理者用])

Source

Base on a problem in ByteCode06
SPOJ 705 [SUBST1]

問題概要

長さ50000以下の文字列が与えられるので,その中に含まれる相異なる部分文字列の数を求める問題.

解法

SuffixArray + LCPでLCPの分だけ重複しているので減らしてやればよい.

SPOJ 530 - Divisors 2 [DIV2] (この記事を編集する[管理者用])

Source

Folklore
SPOJ 530 [DIV2]

問題概要

正整数Nの約数の個数をd(N)とかく.
1000000以下で,d(N)は3より大きくかつ
 N mod M = 0 ならば d(N) mod d(M) = 0
となるようなNを全て列挙する問題.

解法

普通に約数の個数を全部求めて,割り切れるMに対して全部チェックしてもローカルだと1.5秒ぐらいで答えが出るのでOKかと思ったらTLEだった.
よくよく考えれば,素因数分解したとき,指数に2以上の数字が出てこないもののうちでd(N)が3より大きいものを全部列挙すれば良かった.

SPOJ 384 - Any fool can do it [FOOL] (この記事を編集する[管理者用])

Source

University of Ulm Local Contest 2005
SPOJ 384 [FOOL]

問題概要

集合ってのは文字列で,
 {要素1,要素2,…,要素n}
って形のもの.要素数が0も許す.
要素は集合もしくは,1文字で{},のどれか.
200文字以下の文字列が与えられるので,それが集合かどうかを判定する問題.

解法

典型的なDP.領域量O(n^2),計算量O(n^3).

SPOJ 48 - Glass Beads [BEADS] (この記事を編集する[管理者用])

Source

ACM Central European Programming Contest, Prague 1998
SPOJ 48 [BEADS]

問題概要

長さ10000以下の文字列が与えられる.
その文字列をサイクリックに最後の文字は最初の文字になっていると思った時,どこから読めば辞書順で最小になるかを答える問題.

解法

サイクリックに長さを2倍にして,最後に番兵として大きな数字を入れて,SuffixArray作ってみれば良い.

SPOJ 29 - Hash it! [HASHIT] (この記事を編集する[管理者用])

Source

SPOJ 29 [HASHIT]

問題概要

文字列からハッシュを計算して,それを配列に格納していく様子をシミュレーションする問題.

解法

実装問題.やるだけ.

SPOJ 27 - Sorting Bank Accounts [SBANK] (この記事を編集する[管理者用])

Source

SPOJ 27 [SBANK]

問題概要

数字からなる長さ22文字の文字列が100000個以下与えられるので,それを辞書順で何が何個あったかを出力する問題.

解法

ソートするだけ.
制限時間が厳しいっぽいことが書いてあったのでTrieでも作ろうかと思ったけど,普通にint配列にしてソートするだけでAcceptされた.

Another Regional Contest (NWERC 2009) (この記事を編集する[管理者用])

2009年11月14日16時から5時間,10問.
[ Link ]

寝坊して45分遅れぐらいで参戦.
なんとかGとJ以外の8問解いた.
GはAcceptが0で,JはAcceptが1なので,まぁまぁかな.
GとJを除くと,簡単めな問題が多いかな.

Aは与えられた数字を使ってできる素数の数を求める問題.全部作ってチェックするだけ.
Bはノードに文字列が付与された完全2分木が与えられる.枝を張りかえてノード数を減らす問題.
適当にハッシュで判定しようとして上手くハッシュ作れなくてWAもらった.
愚直に判定やるとノード数最大50000でO(n^2)になっちゃうので駄目っぽいと思ってたんだけど,1秒台で通った.
Cは連続する部分列でdで割り切れるものの数を求める問題.前SPOJか何かで解いた記憶がある.たぶんこのブログの何処かに書いてる.
Dはフラクタル.2次元幾何+再帰.実装問題.
EはDP.どっち向きの車が次に進むかが決まっていたら,到着順に,進めるようになったら即座に進むのが最適.
最後にどちらの側の車が走ったか,両側の車があとどれぐらい残っているか,でDPすれば良い.
領域量O(n^2),計算量O(n^3).
FもDP.O(n).適当にルートを決めてやると,ルートから計算すると上手くいく.
Gはわからん.
Hはシミュレーション.6角座標を問題文に書かれている通りに数字を埋めていけばよい.
てか,カタンって,数字は中心から並べていくけど,資源の配置は並べ方違うのではなかったっけ…?
Iは幾何.点が与えられるので,それを頂点となる単純な多角形を作ってくださいという問題.
上をなぞって,その後下をなぞって凸包を作る方法があるけど,それの上だけなぞって,後は右から使わなかった点を全て追加していく感じで解いた.
Jはヨーロッパリージョンではお馴染みのワームホールの問題.単純にダイクストラしてTLEもらった.

LiveArchive 4513 - Stammering Aliens (この記事を編集する[管理者用])

Source

Europe - Southwestern - 2009/2010
SWERC 2009 (One more ICPC Regional Contest, 2009-11-07)
LiveArchive 4513

問題概要

長さ40000以下の文字列が与えられる. その中で,部分文字列としてm個以上現れるものの最長の長さと,それが現れる一番右の場所を求める問題.

解法

長さに対する2分探索.
長さを決めつけると,m個以上現れる部分文字列が存在するかどうかは,rolling hashを使うとO(文字列全体の長さ)で求めることができる.

LiveArchive 4512 - Happy Telephones (この記事を編集する[管理者用])

Source

Europe - Southwestern - 2009/2010
SWERC 2009 (One more ICPC Regional Contest, 2009-11-07)
LiveArchive 4512

問題概要

電話を開始した時刻,通話の長さのログが与えられる.通話の数は10000個以下.
100個以下のクエリが与えられて,それぞれのクエリに対して,ある時刻の区間に対して,通話している数を求める問題.

解法

全部チェックしても十分間に合うのでやるだけ.

LiveArchive 4510 - Slalom (この記事を編集する[管理者用])

Source

Europe - Southwestern - 2009/2010
SWERC 2009 (One more ICPC Regional Contest, 2009-11-07)
LiveArchive 4510

問題概要

初期地点と,x軸に平行な線分がn個与えられる.(nは1000以下)
初期地点は,もっともy座標の値が大きい.
初期地点から,その線分を全て通るような経路のうち,長さ最小のものの長さを求める問題.

解法

それぞれの線分の端点に移動するのに必要な長さをDPで計算する.
上手く計算しないと,O(n^3)になっちゃうけど,点を角度でソートしたりして,O(n^2 log n)ぐらいで書いた.
ACもらえるけど,遅いので,もっと良い方法があるのかもしれない.

LiveArchive 4507 - Darts (この記事を編集する[管理者用])

Source

Europe - Southwestern - 2009/2010
SWERC 2009 (One more ICPC Regional Contest, 2009-11-07)
LiveArchive 4507

問題概要

最初自分の持ち点はn.(nは501以下)
順番にダーツを投げて,当たった場所に書かれている数字だけ点数が引かれる.
ただし,マイナスになる場合は引かれない.
2人で交互に投げて,先に0点になったほうの勝ち.
的に書かれている得点は1~20で,図に書かれた通り.
プレイヤーAは,ランダムに何処かに当たる.
プレイヤーBは,隣接3つのうちどれかに等確率当てることができるので,勝率が高くなるように選ぶ.
それぞれのプレイヤーに対して,そのプレイヤーが先行の場合の勝率を求める問題.

解法

典型的なDP.
ループする場合は,ちゃんとそれを考慮して計算する.( x=ax+b → x=b/(1-a) )

LiveArchive 4505 - Working at the Restaurant (この記事を編集する[管理者用])

Source

Europe - Southwestern - 2009/2010
SWERC 2009 (One more ICPC Regional Contest, 2009-11-07)
LiveArchive 4505

問題概要

机にお盆を置く場所は2か所しかない(重ねることは可能).
 机に1枚ずつ合計m枚お盆を置く
 机から1枚ずつ合計m枚お盆を取る
という操作の列が与えられるので,机からお盆取られるとき,最も古いお盆から順番に渡すようにする方法を1個提示する問題.
 机にあるお盆を1枚ずつ合計m枚移動する
という命令も付け加えて良い.

解法

お盆が来たら,パイルBに取り敢えず全部積み重ねる.
お盆を渡すときはパイルAから渡して,パイルAが空になった瞬間,パイルBのお盆を全てパイルAに移動させる.

LiveArchive 4504 - Trick or Treat (この記事を編集する[管理者用])

Source

Europe - Southwestern - 2009/2010
SWERC 2009 (One more ICPC Regional Contest, 2009-11-07)
LiveArchive 4504

問題概要

2次元平面上に50000個以下の点がある.
最も遠い点までの距離が最小となるような,x軸上の点のx座標と,最も遠い点までの距離を求める問題.

解法

x座標の位置で3分探索.
最も遠い点までの距離で2分探索とかでも良いらしい.

Aizu 2168 - Luigi's Tavern (この記事を編集する[管理者用])

Source

ICPC OB/OGの会 2009 夏合宿 3日目
Aizu 2168

問題概要

勇者と戦士と僧侶と魔法使いがそれぞれ50人以下いる.
同じパーティー内の勇者と戦士,戦士と僧侶,僧侶と魔法使いはそれぞれ仲が良くないとダメ.
僧侶がいないパーティーは戦士と魔法使いはいなければいけない.
全てのパーティーに勇者はいなくてはいけない.
戦士のいないパーティー,僧侶のいないパーティー,魔法使いのいないパーティーはそれぞれ,N_W, N_C, N_M以下でなければならない.
仲が良い人のリストが与えられたとき,最大で何個のパーティーが作れるか求める問題.

解法

まず,N_W人の戦士などを追加して考える.
追加した人は全て仲が良いが,追加した僧侶は,追加した戦士,魔法使いと仲が悪いとすれば良い.
後は,
 (ソース) - 勇者 - 戦士 - 僧侶 - 魔法使い - (シンク)
といったグラフを作って最大流を流せば良い.

Aizu 2166 - Erratic Sleep Habits (この記事を編集する[管理者用])

Source

ICPC OB/OGの会 2009 夏合宿 3日目
Aizu 2166

問題概要

毎晩深夜0時に寝る.
睡眠時間は決められていて,その周期T日.
ただし,カフェインを取ることによって,周期をリセットして,睡眠時間を調整できる.
与えられた,仕事を全部こなすために必要なカフェインの量の最小値を求める問題.
Tは30以下,仕事は100日先程度まで与えられている.

解法

現在何日目か,現在の睡眠時間の周期を状態としたDP.

Appendix

Recent Articles

ブログ内検索

Ads


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