Entries

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

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

UVa 11812 - Innovative Procession Management (この記事を編集する[管理者用])

Source

A Contest from BUBT, Bangladesh (2010-06-27) (blog)
UVa 11812

問題概要

ノード数100以下,枝数10000以下の有向グラフが与えられる.枝には距離がある.
始点の集合と終点(1個)が与えられたとき,最短パスがある限り,その最短パスのどれかに含まれている枝を取り除くという作業を行う.
その過程において,最短パスの長さと,そのとき取り除かれた枝を全部出力する問題.

解法

毎回ダイクストラして,シミュレーションする.
最悪ケースだとO(m^2)なのだけど,あんまり計算時間の大きくなるケースはないみたいで,十分間に合う.

UVa 11809 - Floating-Point Numbers (この記事を編集する[管理者用])

Source

A Contest from BUBT, Bangladesh (2010-06-27) (blog)
UVa 11809

問題概要

浮動小数点で,それぞれ符号ビットを除いて,指数部Mビット,仮数部がEビットとしたときの,表すことのできる最大の実数が10進数で与えられる.
MとEを求める問題.
Mは0以上9以下,Eは1以上30以下の範囲で答えが存在することが保証されている.

解法

log取って仮数部のビットを求めて,適当に条件に合うMを見つける.
計算の途中で誤差がだいぶ乗るのだけど,Mは9以下から誤差の許容範囲をだいぶ緩くしても大丈夫なことがわかるので緩くする.
(もしくは,最も一致するEとMの組みを全探索するとかでも良さそう)

UVa 11808 - Ensuring Victory (この記事を編集する[管理者用])

Source

A Contest from BUBT, Bangladesh (2010-06-27) (blog)
UVa 11808

問題概要

有理数係数のtに関する多項式f(t)と,有理数Xが与えられるので,f(X)とf'(X)を求める問題.
多項式のexpressionの長さは200文字以下.

解法

構文解析 + 多倍長有理数.
とりあえず頑張る.

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

Source

A Contest from BUBT, Bangladesh (2010-06-27) (blog)
UVa 11806

問題概要

N*MのグリッドにK人の人を配置する.
ただし,端の4辺の上にはどの辺も誰か少なくても1人はいなければいけない.
そのような配置の仕方の方法の数をmod 1000007で求める問題.
同じマスに2人以上配置することはできない.

解法

包除原理.
 すべての場合 - 上の辺に配置しない方法 - 下の辺に配置しない - … + 上と右の辺に配置しない + … + 上下左右すべての辺に配置しない
が答え.
配置できるマス目の数がXのとき,組み合わせの数でC(X,K)が配置する方法の数.

UVa 11805 - Bafana Bafanaa (この記事を編集する[管理者用])

Source

A Contest from BUBT, Bangladesh (2010-06-27) (blog)
UVa 11805

問題概要

N人の人が和になって並んでいて,最初K番目の人にボールを渡して,隣の人(番号が1増える方向)にP回パスする.
最後にボールを持っている人の番号を求める問題.

解法

足してmodを取る.
シミュレーションしても良い.

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

Source

A Contest from BUBT, Bangladesh (2010-06-27) (blog)
UVa 11804

問題概要

10人の人の名前,攻撃力,守備力が与えられる.
攻撃5人,防御5人に分けるとき,
攻撃5人の攻撃力の和を最大化する,
その中で防御5人の守備力の和を最大化する,
その中で,攻撃5人,守備5人の順番で,名前の辞書順で最小の組み合わせを求める問題.

解法

全部試して,最適なものを探す.

UVa 11803 - The Great Merger (この記事を編集する[管理者用])

Source

A Contest from Dinajpur, Bangladesh (2010-06-26) (blog)
UVa 11803

問題概要

ノード数201以下の根付き木が2つ与えられる.
その2つの根付き木に自由にノードを加えて,全く同じものにしたい.
ただし,もともとの木に対して,親子関係を崩してはいけない.(葉に新しいノードを加えることしかできない)
加える最小ノード数を求める問題.

解法

DP.それぞれの小ツリーに対して答えを記録しておく.
あとは,それから親同士の答えを求めるときに,最大重みマッチングが必要になるので最小費用流を流した.

UVa 11802 - All Your Bases Belong to Us (この記事を編集する[管理者用])

Source

A Contest from Dinajpur, Bangladesh (2010-06-26) (blog)
UVa 11802

問題概要

n!の末尾にちょうどk個だけ0が並ぶような基数bの数をmod 1000000007で求める問題.
nとkは10^15以下,n/kは500以下.

解法

k個以下0が続く場合を考えて,その後,k-1個以下0が続く場合の数を引く.
で,それは,bを素因数分解したときに,各素数に対して,その指数の範囲を考えれば良い.
n/kは500以下という制約から,計算しないといけない素数の範囲は狭い.

UVa 11801 - A Problemsetter Blind with Emotion (この記事を編集する[管理者用])

Source

A Contest from Dinajpur, Bangladesh (2010-06-26) (blog)
UVa 11801

問題概要

N種類の講義を行う.Nは1000以下.最大可能受講者数を求める問題.受講者数をSとする.
各講義の時間はx[i] * Sだけで,
a[i]だけの準備時間を使うと時間b[i]だけ講義可能な情報が手に入って,
c[i]だけの準備時間を使うと時間d[i]だけ講義可能な情報が手に入る.
b[i]はa[i]以下で,d[i]はc[i]以下で,a[i]とc[i]は100以下.
使用可能な総準備時間Mが与えられる.Mは10000000以下.

解法

各講義ごとにナップザック問題のようにDPする.
ただし,それぞれDPで計算する範囲は,必要になったら計算する,もしくは,
b[i]がa[i]以下,d[i]がc[i]以下,という条件から,答えの上界値を求めて,範囲を絞る.
すると,計算するDPの範囲の和は最大でM程度になる.
また,DPの範囲が大きくなると,その後はgreedyを用いることで高速化できそう.

UVa 11800 - Determine the Shape (この記事を編集する[管理者用])

Source

A Contest from Dinajpur, Bangladesh (2010-06-26) (blog)
UVa 11800

問題概要

与えられた4点を用いて四角形を作ったとき,どのような形になるか,以下の6種類の中から選ぶ問題.
上の方が優先度が高い.
・正方形
・長方形
・菱形
・平行四辺形
・台形
・その他

解法

やるだけ.
doubleで下手に計算したら誤差死するので,整数のまま頑張るか,うまく計算する.
点の順番6通り全部試してしまったのだけど,凸包を取るアルゴリズムを最初にかましたりすると良さそう.

UVa 11799 - Horror Dash (この記事を編集する[管理者用])

Source

A Contest from Dinajpur, Bangladesh (2010-06-26) (blog)
UVa 11799

問題概要

n人の人が,トラックを等速で走っている,その速さが与えられる.
自分が先頭にいるとして,永久に誰にも追いつかれない最小の速さを求める問題.

解法

最大値を求めるだけ.

UVa 11798 - Colorful Board 2 (この記事を編集する[管理者用])

Source

A Contest from Dinajpur, Bangladesh (2010-06-26) (blog)
UVa 11798

問題概要

20マス*20マス以下のグリッドをk色の色で塗り分ける方法の数をmod 1000000007で求める問題.
ただし,マンハッタン距離が奇数となる任意の2セルは違う色で塗られていなければいけない.
kは50以下.

解法

まず,マンハッタン距離が奇数なのを別な色で塗らなければいけないことから,市松模様状に2種類のセルに分離できる.
それぞれ種類に何種類の色を使うか,で場合分けして,コンビネーションの数をかけあわせながら足し合わせればよい.
nマスのセルを厳密にk種類の色を使って色塗りする方法の場合の数f(n,k)は
 k^n - f(n,k-1) - f(n,k-2) - … - f(n,0)
と計算できるのでDPする.

UVa 11797 - Drutojan Express (この記事を編集する[管理者用])

Source

A Contest from Dinajpur, Bangladesh (2010-06-27) (blog)
UVa 11797

問題概要

5人組がN分だけ列車で旅をする.
椅子は4人がけと1人がけで,それぞれの人が1人がけに座っていた時間の総和を求める問題.
それぞれの人は,自分が1人がけに座ったときに次に交代する人のリストを持っていて,それはサイクル上になっていて,最初から順番に適応する.
1人がけに座ると,その人はM分座り,その後,その人のリストの先頭の人と位置を交換し,リストの先頭を削除する.
交代には2分かかり,その間は誰も1人がけの椅子に座ってないとみなす.
Nは1000以下.

解法

シミュレーション.やるだけ.

UVa 11796 - Dog Distance (この記事を編集する[管理者用])

Source

A Contest from Dinajpur, Bangladesh (2010-06-26) (blog)
UVa 11796

問題概要

線分の数が50個以下からなる折れ線が2つ与えられる.
その折れ線に沿って,2人の人が,等速で始点から終点まで移動する.かかる時間は一緒.
移動中の,2人の距離の最大値 - 最小値 を求める問題.

解法

二次元幾何 + シミュレーション.
折れ曲がる時間で区切って,その間の部分で,2人の距離の最大値と最小値を求める.
最大値は,単調性より端だけ調べればよくて,最小値は解析的に求めても良いし,3分探索しても良い.

UVa 11795 - Mega Man's Mission (この記事を編集する[管理者用])

Source

A Contest from Dinajpur, Bangladesh (2010-06-26) (blog)
UVa 11795

問題概要

ロックマン.
Nステージあって,敵を倒す順番のパターンの数を求める問題.Nは16以下.
倒した敵の武装は使える,ロックマンの初期装備と,それぞれの敵の武装で,どの敵を倒すことができるかの関係が与えられる.

解法

現在倒した敵の集合を状態としたDP.
状態数2^Nで,計算時間量O(N*2^N).

A Contest from BUBT, Bangladesh (この記事を編集する[管理者用])

2010年06月27日17時から5時間,9問.
[ Link ]

6問解いた.眠い.
解いたのは,ABCEFI.残りの3問は誰も通していない.
以下,問題別.

・A問題
全部の組み合わせを試してソートする.
・B問題
足してmod取るだけ.
・C問題
包除原理で簡単に計算できる.なんで,これタイムリミット2秒も必要なのかわからない.
・D問題
超絶幾何?
適当に,回すと収束しないかなと思ったけど無理でした.
・E問題
構文解析+多倍長有理数係数の多項式….
昔作った,多倍長有理数のライブラリ(約10KB)使ってやって,TLEっぽかったので,ジャッジテストに含まれる次数と多倍長の桁数を調べてみようとした.
次数は100次近くになることがあるっぽいけど,多倍長は30桁ぐらいで通った.
・F問題
log使って計算せずに,愚直に2で割っていってTLE.
log使って計算したとき,WA連発.
意外と精度が厳しいのと,答えの制約からEPSを1e-5とかで十分ってことに気づいて,そうやったら通った.
・G問題
謎.O(3^n)のDPとかになるんだろうか…?
・H問題
問題文の意味がわかりませんでした.
・I問題
最悪ケースでO(m^2)になるかなと思ったけど,普通に書いたら(毎回ダイクストラ)全然すぐ終わって間に合った.
最初,出力をソートするの忘れててWAもらった.あとでやろうと思ったことは忘れる.

Open 2010 Algorithm Round 2 参加記録 (この記事を編集する[管理者用])

2010年06月27日01時02分から.

Assignment

一番後ろの部屋.システムテストで焦らしプレイされる部屋.
ここで勝つとTシャツのはず.

EASY

ノード数50以下の対称な有向グラフが与えられる.
対称という意味は,aからbに枝がk本あったら,bからaにも枝がk本ある.
ノード0から出発して,全部の枝を1回以上通る閉路のうち,最短のものの長さを求める問題.

雪かきとか,問題文が一瞬読めなかった,辞書引いた….
うーん….
連結だったら,全ての枝を1度ずつ通ることできるんじゃない?
DFSでたどり着いた順にツリーみたいに思って,行って帰れば行ける.(あとで考えれば入次数 - 出次数が全部0なのでできる)
じゃー,連結かどうか確かめれば良い!
書いた.サンプル通らない….枝が出てないノードがあることもあるのか.危ない….
修正.サブミット.

MEDIUM

与えられた正整数X以上で,2つのtotally oddな整数の和で書ける最小の数字を求める問題.
totally oddとは,各桁が全て奇数.
Xは100000000以下.

うーん….
1億ならビット使って圧縮すればなんとかメモリに乗るし,全部列挙しても….
いや,そんなわけ無いだろう….
でも,totally oddの物の数はいくらだ…?
5^8 + 5^7 + … で40万ぐらい?
少ない!
が,でも,40万^2は無理だ….
列挙しなくても,Xがtotally oddの和で書けるかどうか,確かめるなら,片方決め付ければ,もう片方が存在するかどうか調べるだけなので,O(40万)で行ける.
が,それを最大で何回すればいいの…?
なんか,サンプルテストケースみると,結構な範囲で,和で書けないことがあるみたい.
うーん….
でも,答えはもっと限定されるんじゃない?
奇数+奇数なので,偶数じゃないと駄目.
後は,くり上がりがあるから…よくわからない.
でも,前の桁が0なら繰り上がりできない….
これで,判定したら,一瞬なんじゃ….
いや,でも,結構面倒だぞ,これも….
いや,まてよ!
> 列挙しなくても,Xがtotally oddの和で書けるかどうか,確かめるなら,片方決め付ければ,もう片方が存在するかどうか調べるだけなので,O(40万)で行ける.
って,和のうち,片方の数字を決めつけたら,残りの数字をX以上になるように定めれば良い.
尺取メソッドだ.
書いた.
サブミット.

HARD

W*Hの板チョコがある.
40個以下の座標が与えられる.その座標の部分のチョコは特別.
チョコを割って,全ての破片が,特別なもののみか,特別じゃないもののみか,となるようにするための最小の割る回数を求める問題.
WとHは10億以下.

座標圧縮してDP?
かな…,こんなに簡単でいいのか…?
面倒だからこんなものなのかな….
あ,圧縮するにしても,40*40に圧縮したらいいけど,80*80とか120*120に圧縮したらメモリ足りないし,時間も足りなさそう.
やっぱり面倒.
そして,お腹痛くなってきた….
お花畑へ….
復帰して書く.
書いた.
ケアレスミスでサンプル通らない.
通った.
最悪ケースでも時間間に合う.
サブミット.
….
皆この問題resubmitしてるのですが…,怖い….

Challenge

500でTLE狙い…?
うーん,500は,皆やりかた違うぞ….
ちゃんと,くり上がりを見ているらしい…,それで間に合うかどうか分からないけど,多分間に合う….
250は,始点とつながってないけど,連結の場合落ちる人がいるのか.
探してみよう….
これ怪しいのではないか?
ちゃんと読もう…としてたら,他の人に落とされた.
ってことで,後は見てただけー.

System tests

HARDが落ちた.ってか結構皆落ちてる….
後で直そうとしたら,分割するときに,余分に割ってたバグ発見,でも直してもまだ間違ってる.
うーん….
(2010-06-27 12:22追記 まだ余分に割ってることがわかった…,こういうのを1回で正確に考えて,正確に実装できるようにならないとだめだなぁ…)

A Contest from Dinajpur, Bangladesh (この記事を編集する[管理者用])

2010年06月26日17時から6時間,10問.
[ Link ]

最初1時間40分ほど,サーバがほとんど落ちてて,サブミットしても反映されなかった.
そのため,1時間延長されて,5時間→6時間になった.
A以外の9問を4時間15分ぐらいで解いて,Aは放棄しました.
最初1時間40分で6問書いて,ストックしておいたのが,3問しか通らなくて泣きたくなった…,ほとんどケアレスミスだったけど.
以下は時系列順じゃなくて,問題別.

・A問題.
15パズルを解く問題.ただしサイズは50*50以下で,最短手順じゃなくて良い.超絶実装.無理….
・B問題.
どうみてもDP.
答えの最大値が16!なのに,なぜか勘違いして2^16はintに収まるよね,とか言ってWAもらった.
・C問題.
各線分上を動いているときは,単調だから端だけ調べればよいよね…と一瞬誤解した.
最小値は,間の場合もあるので,3分探索した.
小数点以下四捨五入のはずが,切り捨ててて,1回WAもらった….
・D問題.
問題文が読みにくかったけど,読んだらシミュレーションするだけ問題だった.
・E問題.
この前のTopCoderのSRM473 DIV1 HARDを彷彿とさせる問題だった.DP.
市松模様上に2つに分解して考えれる.
・F問題.
誰よりも遅くないスピードで,最も遅いスピードを求める = 最大値を求める.
問題文読むだけ.
・G問題.
2次元幾何.
相変わらずdoubleでやると誤差死.
最初に,形を正規化しておいて,doubleで計算して通した.
・H問題.
最初問題の意味を誤解した.
準備時間の方が長いのを利用して,答えの最大値を見積もって,それぞれDPする範囲を定めればいい.
・I問題.
0がk以上続くものの基数の数は,bを素因数分解したとして,その指数の取りうる範囲を調べる.
・J問題.
問題の意味を理解するのに苦戦した.
そして,最後まで,直接の上司を間接的な上司に変えても良いのだと誤解して,1 TLE, 1 WA.
DPしながら,どの子供の木をどの子供の木と対応させればよいのか,というのは,最大重みマッチングみたいな感じになって,最小費用流を流した.

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

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

A. World Football Cup

サッカーで,nチームで総当たり戦をした結果が与えられる.nは偶数で50以下.
上位n/2チームが次のリーグにすすめるとして,次のリーグにすすめるチームをチーム名のASCIIコードを使って辞書順に出力する問題.
勝つと3ポイント,引き分け1ポイント,負け0ポイント.
タイブレークは,得失点差でつけて,それでもタイなら,総得点の大きい方が上位.
それでも,進出チームが一意に定まらないようなテストケースは含まれていない.

lexicographical orderの定義が何処にもかいてない気がするんだけど….
こんな曖昧な問題文なら,そのうちclar飛んでくるだろう…,放置.

B. Checkout Assistant

n個の商品に対して,t[i]とc[i]が与えられる.
全部の商品を手に入れたいのだけど,ある商品iをc[i]円で買うと,任意のt[i]個の商品がただで手に入る.
最小コストを求める問題.
nは2000以下.

グリーディーでいけるのかなぁ…,いけなさそうだなぁ….
DPにしても,買う順番も考えないといけないし….
いや,ただで手に入れることのできる数をマイナスも許可すれば順番を考慮しなくていいのでは.
いいじゃん,単純なDPだった.
書いてみる.ケアレスミスでWA.その後AC.
ケアレスミスは,マイナスも許可したので,配列の途中から使うように下駄履かせたのだけど,下駄の高さを間違えてるとか….

A. World Football Cup

clarこないので,自分で送るか….
で,その間C読もう.

C. Deletion of Repeats

100000要素以下の配列が与えられる.同じ要素は最大で10個しかない.
以下の操作の繰り返しによって,要素を消していった後,残った要素を出力する問題.
 a[i..i+n-1] == a[i+n..i+2n-1]を満たすもののうち,nが最小,その中でiが最小のものを見つけてa[0..i+n-1]を消す

サンプルが理解出来ない.なんで7が残るんだろう….
ってか,clar返ってくるの早い!一瞬で返ってきてた.

A. World Football Cup
Q. What is "in lexicographical order"?
A. It is also known as dictionary order or alphabetic order

その返信じゃわからん….
AaaaチームとAAAaチームはどっちがlexicographical orderで早いのよ?
 (1) AaBbCcDd…YyZz
 (2) aAbBcCdD…yYzZ
のどちらの順番なのかわからないけど,もう両方試せばいいや…,言わないのならどっちでも通るんだろう.
書いた.(1)でWA.(2)でWA.
あー,タイブレークのルールが総得点の小さい順になってた,逆だよ….
(1)でWA,(2)でWA.
うーん,取り敢えず,文字列の扱いが怪しいので,チーム名が存在しないとか,読み込み失敗したら無限ループするようにしてみる.
TLEじゃなくてWAだった,合ってるなぁ….
 (3) ABCD…YXabcd…yz
で試しに送ってみる.AC.え….
それは,ASCIIコード順っていうのでは…,少なくても,dictionary orderだとかalphabetical orderとは言わないのでは?
とclarに送ったら,clarがポップアップで送られてきた,すげー.codeforcesいろいろ進化してるなぁ.
でも,ポップアップ消したら,見直せないのかな?
何処に書いてあるのかわからなかった.

C. Deletion of Repeats

うーん,サンプル2個目が意味不明.
5656が消えて77が消えて….
4が残るんじゃないの…? (and everything that is to the left of this repeat. を読んでないし,いろいろ勘違いしてる)
まぁ,サンプルが間違ってるとして考えてみようか….(サンプルが間違ってるとかよくあることだし…)
うーん…,同じ文字が高々10個しかないってのが大事なはずだ.
それで,部分文字列が一致する候補は,高々,文字列の長さ*50程度しかない.
で,それが,部分文字列が一致してるかどうかは,最初にrolling hashを計算しておけば,O(1)で判定可能.
だが….
 1234554321
みたいなのだと,55が消えて,44が消えて…,って感じなので,rolling hashを計算しなおさないといけない….
どうやってもO(長さ^2)になっちゃう気がする….
他の問題も読もう.
(消したとき,消した部分の左側が全部消えるんだから,実は書くだけ問題だった…)

D. Points

2次元平面上に最初何も無い状態.以下のクエリが200000個以下与えられるので,それに答える問題.
 1) 座標を指定して,その場所に点を打つ
 2) 打った点を消す
 3) ある座標よりも,x座標,y座標が両方でかい場所にある点のうち,一番x座標の小さいの,その中で,一番y座標の小さいものを求める.存在しないならそれを指摘する.

うーん….
適当にソートしておいて2分探索で,それがy座標の条件満たさないと次の点を探しに行く….
とかやると,最悪ケースで二乗オーダー….
うーん….
各点に,自分より右上で,一番左の点を覚えておくとかしたらどうだ…?
点を消したとき,全部計算し直しなので,二乗オーダー.
次の問題を読む.

E. Fairy

ノード数10000以下,枝数10000以下の無向グラフが与えられる.
全ての枝に対して,その枝を取り除いたら,2色彩色可能になるかどうかを判定する問題.

問題文が読みにくいようで,そんなこともなかった.
適当にグラフを紙に書いて考えてみる….
2色彩色可能ってのは,奇数長のサイクルが存在しないのと同値なのかな?
全ての奇数長のサイクルを列挙して,全てに含まれている枝を見つけて,それを取り除けば,2色彩色可能?
…,列挙できる気がしない.

Result

いい感じにRateが落ちました.

Aizu 1143 - Hexerpents of Hexwamp (六角沼の六角大蛇) (この記事を編集する[管理者用])

Source

ACM/ICPC Japan 2006 Domestic
PKU 3008
Aizu 1143

問題概要

日本語の問題文が存在するので略.(Aizu Online Judge参照)

解法

蛇の状態(頭の位置に対する各節の相対位置)を全部生成してやって,どの状態からどの状態に移れて,その際,頭の位置がどれだけ動くかというのを最初に生成する.
後は,蛇の状態と頭の位置をノードにしたグラフ上でBFSする.
また,(ニコ生放送後にやった改良点としては,)蛇の状態生成の方に時間がかかっていたので,最初にテストケースを全部読み込んで.
蛇のサイズが小さい順に処理してやって,蛇のサイズが同じ時は状態を毎回生成しないことにしたら早くなった.

Open 2010 Algorithm Round 1 参加記録 (この記事を編集する[管理者用])

2010年06月20日01時02分から.

Assignment

赤から灰色までいる部屋.TCOならでは.

EASY

アルファベット小文字からなる2つの同じ長さの文字列sとtが与えられる.
同じ文字列に変形したい.
1回の操作で,1文字を1つ次の文字,1つ前の文字に変えれる,aの前の文字はz,zの次の文字はa.
最小回数で,同じ文字列にしたとして,その文字列を求める問題.
複数候補があるなら,辞書順最小のものを求める.

1文字ずつ考えれば良い.
普通に文字の小さい方に合わせればいいのでは?
いや,z→aの部分を経由するのが最小ならaにできる!
えーっと….
ループ考えずに,2つの文字の距離が13未満なら,z→aの部分を経由できないので,小さい方,そうでなければ,aにする.
書いた.サンプル通った.サブミット.
うーん,大丈夫だよなぁ…?
次の問題に行こう.

MEDIUM

最初x=1, y=1になっている.
命令Xを行うとxにx+yが代入される.
命令Yを行うとyにx+yが代入される.
x=rとするための,命令数最小の命令列を求める問題.
複数あるなら,辞書順最小のものを求める.
rは1以上1000000以下.

うーん,いつぞやのICPCアジア地区予選(日本大会)の問題を彷彿とさせる問題だなぁ….
iterative deepening…なわけはない,これはTopCoderだ.探索な問題のわけがない.
うーん,最後 x=r, y=a だったら,前のターンはどうなるか….
逆から見れば,分岐はない!
でも,aを1000000通り試すとTLEっぽいが….
試してみよう,書いてみる.
書いてみた,TLE.
うーん,取り合えず長さだけ先に求めよう.
長さを求めるなら,ユークリッドの互除法っぽい感じでlog(r)で計算できるはずだ.
で,後は,長さ最小のものだけ命令列を求めていく.
間に合う!
いろんなケース試してみたけど,最悪で0.15秒ぐらい.
サブミット.

HARD

ノード数50以下の有向グラフ(完全グラフ)が与えられる.
何本でも良いので,ノード0から他のノードを経由してノード0に戻るパスを引く.
 引いた本数 * fee - 全てパスの重みの和
を最大化する問題.feeは入力で与えられる定数.
ただし,全てのパスを通じて,ノード0を除いて同じノードを複数回訪れてはいけない.

うーん,DP?
ノード数いくらだ,20だといいなぁ…,50じゃん….
難しくないか?
うーん….
最小費用流だ!
書く.書いた.通った.
サブミット.

Challenge

250で距離13の場合のコーナーケースでWAってる人いないかなぁ…,テストケース作成.
後は500でTLEしそうな人を狙う?
ぼけー.
皆が500を結構落としてる,ほぇー.
って,自分のも落とされた,なんだ?
あ,r=1ってあるのか…,それは見逃してたorz
ってことで,何もせずに終了.

System tests

EASYとHARD通った.
Rateが微減…,意外と軽傷で済んでよかった.
500通ってたら1桁順位だし,Rate上がったんだろうなぁと思うと勿体無いけど.
すぐに慎重さが足りなくなる,もっと慎重になれ.

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

2010年06月18日10時02分から.

Assignment

赤が多い気がするけど,普通っぽい部屋.

EASY

前に1マス進む,右に90度回転する,左に90度回転する,という命令の列が与えられる.
その命令セットを繰り返し,無限回行った時,無限に遠くに行くかどうかを判定する問題.

1回命令セットやって,原点に戻ってきたら,遠くへ行かない.
それだけか…?
いや,向きが変わってたら4回で戻ってきたりする.
4回やって戻ってくるかどうか調べたら良さそう.
…,でも,一応10回やって戻ってくることがあるかどうかを調べる.
書いた.
サンプル通らない,ってか,全部逆の結果が出てる.
あれ,boundedとunbounded逆にしたか?
してない…,なんで逆なんだ,逆にしてサブミットしてしまうか?
ダメだよそんなことしちゃ!
…ループの添字間違ってたorz
サンプル通った.サブミット.

MEDIUM

円周上に等間隔に1000000個以下の点がある.
100000個以下の点を赤く塗る.
赤く塗られた点だけからなる直角三角形の数を求める問題.
赤く塗る点の集合は,逐次,乱数で生成して,すでに塗られている点が指定されたら,時計回りにまだ塗られていない直近の点を塗る.(問題文参照)

えーと,どんな場合に直角三角形なるのか?
って,2点が直径の場合だよ!
あれ,簡単じゃないの?
尺取メソッドなり何なりで,直径になる点の組みを見つけてあげて,その間の点の数を足していけば良い.
書こう!
乱数で,同じ点が生成されたらどうするんだ…?塗られていない次の点を見つけて塗るのか….
こっちのほうが難しいじゃないか!
愚直にかいたらO(n^2)だ.
えーと…,取り敢えず,愚直に書いて,後で直す.
直角三角形のカウントは…,尺取メソッド必要ないよ,配列に入れてなめていけば良い.
簡単すぎる…,乱数生成をうまくやる問題っぽい.
一応,Arenaで最悪ケースっぽいの入れてみる,TLE.
うーん,どうしようか….
次の塗られてない場所を,それぞれ配列で格納しておいて,union findの時みたく,適当に更新していけば良いんじゃない?
えっと深くなるけど再帰呼び出ししても大丈夫か…?
10万回なら行けるはず,100万回はアウトだけど.
書いてみよう.サンプル合う.自分で作ったテストケースもTLEにもsegmentation faultにもならない.
サブミット.

HARD

30*30以下のチェス盤で,10種類以下のルークを置くパターンの数 mod 1000000009を求める問題.
違う種類同士のルークは,互いに攻撃出来る場所においてはいけない.
チェス盤の行数,列数,各種類のルークの数が与えられる.
ルークは縦横に無限に動けるコマ,将棋でいう飛車.

ルークの動き方ってなんだっけ,ノートを見る,飛車か.
DPの匂い…,あんまり難しくなさそう.今日は残り時間もあるし,これは解ける!
30*30ってなんでこんなに小さいんだろう….
えっと,違う種類のルークは同じ行,同じ列に配置できないから….
ある種類のルークを配置したら,行数と列数の小さくなった同じ問題に帰着できる.
単純なDPじゃん…,こんなに簡単でいいのか.
書く.
n個のコマを,ちょうどr行c列だけ使う置き方のパターンの数っていくらだ?
包除原理より,
 C(r*c,n) - C((r-1)*c,n) - C(r*(c-1),n) + C((r-1)*(c-1),n)
とかじゃない?
合わない…,あ,使わない行,列の選び方もあるか.
 C(r*c,n) - r*C((r-1)*c,n) - c*C(r*(c-1),n) + r*c*C((r-1)*(c-1),n)
これか?
違う….
え…,あー,こんなに単純じゃないよね….
てか,結構サブミットはされてるけど,思ってたほどじゃない,そんなに簡単でもなかったのか?
どうしよう.
これもDPすればいいか?
混乱してきたので,一番原始的な方法で書く,たぶん大丈夫だろう.
 dp[残りの行][全部の列][すでに使った列][残りルーク]
で,30*30*30*30のメモリ,大丈夫.
書く.
よし,サンプルの答えあった.
30行30列で,10種類のルークがそれぞれ10個とかでも間に合う.
いける!
嘘だっ!!
残りルーク30じゃないよ…,上限900だよ….
間に合わない,ってかメモリたりてない.
残り12分,やばい,時間がなくなってきた….
普通に,ちょうどr行c列消費するk個のルークの置き方の数をdp[r][c][k]として
 dp[r][c][k] = C(r*c,k) - ∑[a,b=1,2,...] dp[a][b][k]
みたいなのでいいのでは….
サンプルあった.
いろいろテストして大丈夫そう.
サブミット.

Challenge

500の乱数の作り方でTLEになりそうな人を狙い打つしかない.
全部先に取られた,後は見守るだけでした….
流石に,みんなちゃんと計算時間考えて書いてました.

System tests

全部通った.
1年5ヶ月ぶりぐらいにHARD通った,ちょっと嬉しい.
でも,問題が簡単だった,時間かけすぎってことで,普通な順位.
Rateは少し上がった.

Open 2010 Marathon Round 1 - Planarity (この記事を編集する[管理者用])

2010年05月20日02時から,4週間.
(TCO非参加者,Round 1免除者用に,Marathon Match 61として同じ問題で同時に開催)

Source

Problem Statement
standings
standings (Matathon Match 61)

問題概要

グラフが与えられるので,枝はまっすぐな線分でつながれているものとして,平面上にノードを配置して,枝の交わる回数を少なくせよ,という問題.
ノード数は10以上100以下,枝の数はノード数の2倍以上5倍未満.

自分の解法

最初ランダムにノードを配置する. その後,制限時間が終わるまで,以下の操作をする.
ランダムに1個の点を選んで,ランダムな場所に移動させて,交わる枝の数が減るなら,それを採用する.
連続で,何回も採用されないと,ときどき採用してみる.

自分の提出コードは記事の最後に載せています.

最終Full Submit直前のExample Submitの結果.

Example scores:
0) 44.0
1) 39.0
2) 4198.0
3) 550.0
4) 635.0
5) 60.0
6) 3374.0
7) 565.0
8) 205.0
9) 3040.0
参加記録

以下,時系列順のログです.

続きを読む

Beta Round #17 D問題 - Notepad (この記事を編集する[管理者用])

Source

Codeforces Beta Round #17 C問題
Problem description
Beta Round #17の自分の参加記録

問題概要

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

解法

bはmod cで考えれば良い.
b^nはそのうちnに対して周期phi(c)になることを用いてnも大きければmod phi(c)で落とす.
phiはオイラーのファイ関数.

C言語のスパゲッティなコード

続きを読む

Beta Round #17 C問題 - Balance (この記事を編集する[管理者用])

Source

Codeforces Beta Round #17 C問題
Problem description
Beta Round #17の自分の参加記録

問題概要

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

解法

要するに,例えば,入力文字列がabbcだったら,正規表現で書けば,a*b*b*c*にマッチするバランスされた文字列の数を求めれば良い.
状態を,
 正規表現の何処まで使ったか,次に来ることのできる文字種類,Aを何文字使ったか,Bを何文字使ったか,Cを何文字使ったか
としてDPする.

C言語のスパゲッティなコード

続きを読む

Beta Round #17 B問題 - Hierarchy (この記事を編集する[管理者用])

Source

Codeforces Beta Round #17 B問題
Problem description
Beta Round #17の自分の参加記録

問題概要

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

解法

ノードに入ってくる枝のうち,最も小さいコストの枝を採用する.
入ってくる枝がないノードが2個以上あると不可能.

C言語のスパゲッティなコード

続きを読む

Beta Round #17 A問題 - Noldbach problem (この記事を編集する[管理者用])

Source

Codeforces Beta Round #17 A問題
Problem description
Beta Round #17の自分の参加記録

問題概要

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

解法

やるだけ.

C言語のスパゲッティなコード

続きを読む

SPOJ 6773 - Dinostratus Numbers [DINONUM] (この記事を編集する[管理者用])

Source

SPOJ 6773 [DINONUM]

問題概要

3*3の行列で,各要素はそれぞれ異なっていて,上,左の要素の倍数になってなければいけない.
1048576以下の自然数が与えられたとき,その数字が右下になるような行列が存在するかどうかを判定する問題.

解法

 1 a ab
 c ac abc
 d acd abcd
の形に限定して,与えられた自然数を4つの積でかいて,上手く行列の要素が全て異なるようなa, b, c, dが存在するかどうか全部調べてみた.

SPOJ 6772 - Happy Coins [HC] (この記事を編集する[管理者用])

Source

The 7th UESTC Programming Contest
TJU 3249
SPOJ 6772 [HC]

問題概要

一直線上に,○か×かのマークが100000個以下書いてある.
○の人と×の人が順番に行動する.
それぞれ,2つの連続するマークを1つのマークに置き換えることができる.
2つの連続するマークが同じだったら,○に置き換わり,違ったら×に置き換わる.
最後に1個残るとき,どっちのマークが残るかを求める問題.
お互いの人は,自分のマークを最後に残すように行動する.

解法

×のマークの個数の偶奇は変わらないので,最初×のマークが奇数個あれば必ず最後に残る.

SPOJ 6738 - Nice Quadrangles [CHEFMAY] (この記事を編集する[管理者用])

Source

CodeChef May Challenge
SPOJ 6732 [CHEFMAY]

問題概要

2次元平面上の格子点が30000個以下与えられるので,次の条件を満たす四角形の作り方のパターンの数を求める問題.
4点は軸上になく,それぞれ第1象限,第2象限,第3象限,第4象限に1個ずつあって,面積が整数.

解法

面積は半整数で,面積の計算には座標の値を掛けたり足したり引いたりすれば求めるので,面積が整数になるかどうかは各座標のmod 2の値しか関係しない.
なので,第k象限の点を,x座標 mod 2, y座標 mod 2の4種類に分類して,全部まとめて扱う.

Appendix

Recent Articles

ブログ内検索

Ads


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