Entries

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

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

闘神都市3 - レベル31 (この記事を編集する[管理者用])

ネタバレ要素があるので続く.

続きを読む

闘神都市3 - レベル27 (この記事を編集する[管理者用])

ネタバレ要素があるので続く.

続きを読む

Another semi live regional (この記事を編集する[管理者用])

2008年10月29日22時から5時間,10問.
[ Link ] [ LiveArchive ]
ACM/ICPC Europe Southwestern 2008.

A. Bring Your Own Horse
グラフ理論.
ある場所からある場所まで移動するのに,もっとも長い枝を短くしたい.

B. First Knight
2次元の升目上で1ターンで上下左右のどこかに移動する確率が与えられる.
最初左上にいて右下にたどり着くまでにかかるターン数の平均値を求める問題.
マップのサイズは 40 * 40 以下.平均ターン数は1000000以下であることが保障されている.

C. Postal Charges
Ad-hoc.
世界のサイズは10×10.
家の位置の座標は整数とは限らないが,座標の整数部分で 10 * 10 の区画に分けられている.
全ての家と,その家より厳密に上の区画で右の区画のにある家に道がある.
道の長さの平均値を求める問題.
ただし,長さの定義はマンハッタン距離.

区画ごとに,その区画にある家の数,重心を覚えておけば良い.

D. Randomly-priced Tickets
ワーシャルフロイド + DP.
ある場所からある場所に行きたい,使えるお金の量が与えられる.
枝を1個移動するのにかかるお金は,移動するときに決まり,1以上 R 以下の整数からランダムに選ばれる.
目的地にたどり着ける確率を答える問題.

E. The Game
DP + 超絶実装. (たぶん)
2人でいろいろとルールが面倒なゲームを行う.
2人とも最適に行動した場合の最終的なスコアを求める問題.

F. The Merchant Guild
DP. (たぶん)
n 人の人が自分が座りたい席の情報が与えられたとき,座る席を決めるアルゴリズムは番号の若い人から以下の手順を踏む.
 自分が座りたい番号以上の席で一番小さい番号の空いている席に座る
自分が座りたい番号以上の席が空いてなければ座らない.
全員が座ることができるような,自分が座りたい席の情報は何通りあるかを求める問題.
入力で,ある程度の人の座りたい席の情報が与えられて,それは固定して考える.

G. Toll Road
グラフ理論.
枝にコスト(負もある)が与えられていて,連結で木になるように枝を取ってきて,枝のコストの和を最大化したい.

H. Top Secret
円上に1000個以下の数字を並べる.
1回のステップで,それぞれの数字に対して
 右の数字の R 倍 + 左の数字の L
を足す. s ステップ後を求める問題.ただし mod 10^Xで.

I. Transcribed Books
 i = 1, 2, ... , 1000以下
 a[i] = b[i] mod N, N > b[i]
を満たす最大の N を求める問題.
ただし,任意の N に対して成り立ったり,成り立つ N > 1 が存在しない場合はそれを判定する.
gcdするだけ.ただし,微妙にintだとオーバーフローするのでunsignedで書く.

J. Wizards
Math + 多項式gcd. (だと思う)
n 次多項式が与えられたとき,それの異なるゼロ点が n 個存在するかどうかを判定する問題.
ゼロ点は複素数でも可能.

 a が重根 iff f(a) = f'(a) = 0
なので gcd( f(x), f'(x) ) を求めれば良い気がする.

闘神都市3 - レベル23 (この記事を編集する[管理者用])

闘神大会が終了してようやくOPムービーが流れたところ.
わかっちゃいたけど,これからが本番.
闘神都市2以上に本番が長そうな気がしてきた.

これから先の進捗状況は激しくネタバレ要素が含まれてしまうので次回から続きに押しやる予定.

続きを読む

闘神都市3 - レベル20 (この記事を編集する[管理者用])

4回戦(準決勝)を勝ったところまで.
1ドロップで枯渇率+2になるダンジョン(滑り台の前まで)は全て枯渇率を80以上にしてみた.
良いアイテムはなかなか手に入らないなぁ.

続きを読む

闘神都市3 - レベル16 (この記事を編集する[管理者用])

3回戦を勝ったところまで.
レベル上げがてら調べてみたけどアイテム枯渇度の最大値は90みたい.

続きを読む

闘神都市3 - レベル8 (この記事を編集する[管理者用])

やっぱり誘惑には勝てない.
予選迷宮終わって,1回戦に勝って,教会と貯水池ダンジョン探索中.

続きを読む

いよいよ (この記事を編集する[管理者用])

今日が発売日なのだけど,プレイする時間があるかどうかが問題だ….

SRM427 DIV1 (この記事を編集する[管理者用])

2008年11月26日11時から.
[ overview ] [ otinn.com summary (Japan) ]

EASY (250pt)
Math.問題文が少しだけ長い.
一年の長さと一日の長さが与えられる.
うるう年は普通の年と比べて1日だけ長い.
さて,適度に普通の年とうるう年を混ぜ合わせて辻褄を合わさなければいけない.
普通の年とうるう年のパターンの周期は最短でどのぐらいの年数になるか,を求める問題.

計算すれば gcd やら lcm やらで表すことができる.

MEDIUM (600pt)
Math + Ad-hoc.
自然数 km が入力.
最初原点で北を向いていて, G = 1 としておく.
以下の操作 ( 1, 2 ) を k 回繰り返したとき,あなたはどこにいますか,という問題.
 1. 向いている方向に dig( G ) だけ進む
 2. 右に90度向きを変えて, G := G * m とする.
ここで, dig は10進数で書いたときの各桁の総和を取るという作業を1桁になるまで繰り返す関数.

実は,
 1 <= dig( a ) <= 9
 dig( a ) = a mod 9
であることに気づけば,dig( a * b ) = dig( dig(a) * b ) であるので,周期的であることが分かる.
後は適当にやるだけ.

HARD (900pt)
DP.
高々30個の要素からなる自然数の集合と,自然数 p が与えられたとき,
集合の要素を一列に並べて,全ての隣り合う要素同士の差が p の倍数ではないのは何通りあるか,modいくらかで求める問題.

与えられた自然数を mod p の値で分類したら,同じ値になるもの同士が隣り合わなければ良いことになる.
そうなると,mod p の値が同じものが何個あるかだけが重要な情報となって,状態数は高々
 残りの要素の数(30の分割数 + 29の分割数 + … ) * 次に置けないものの種類(30)
ぐらいなのでDPで間に合う.

North America - South Central - 2008/2009 (この記事を編集する[管理者用])

中途半端だけど,取り敢えずメモしておく.
追加で問題解いたときに,また書き直すかもしれない.

9問.
Link先はLive Archive.
[ Link ]

A. Rank and File
読んでない.

B. The Extent of the Problem
読んでない.

C. Filtration
読んでない.

D. Like Water for Clay
やるだけ.塗りつぶす.
水が貯まる升目の数を求める問題.
上下左右,どれを下にするかで90度回転しながら4通り求めなければいけない.
隣接関係は8近傍.
水が貯まるマスの数を求めるのは O( マップのサイズ ) で計算可能.

E. Wandering Aimlessly
シミュレーション.
RPGの町人の歩く手順が与えられるので n ターン目の町のマップを出力する問題.
移動する先が壁や町の外に出るようなら移動しない.また,町人同士はぶつからないことが保障されている.
一連のコマンドが終わった後,元の位置に戻るなら,その一連のコマンドを連続して行う.
元の位置に戻らないなら,同じステップを逆向きに辿ってもとの位置に戻る.そしてそれを繰り返す.

各キャラごとに,
 求めるターン % ( 2 * 一連のコマンドにかかるターン数 )
ターン後の位置をシミュレーションで求める.

F. Cables ... in Spaaace!
簡単幾何 + MST.
球状の2点間の距離は表面上で考える.
n 都市の緯度・経度が与えられ,それらの全域最小木の枝の長さの和は,与えられた入力より小さいかどうかを判定する問題.

G. Patterns and Pictures
やるだけ.個人的には + 英文読解.
でかい絵はとあるパターンの連続である.
とあるパターンが入力で与えられて,そのパターンに含まれる小さな絵の面積とその数が与えられる.
でかい絵の面積が n * 36 * 36 ( n = 1, 2, 3 ) のとき,最大でパターンは何個含まれるか.

floor( でかい絵の面積 / 各パターンに含まれる絵の面積の総和 )

H. No Wormholes Were Harmed...
タイムトラベラー.
今西暦 x 年で, y 年に用事がある.
y 年に行った後, x 年に戻るためには,最低どのぐらい年齢が増えるか,を求める問題.

wormhole と呼ばれる時空を越える穴があって,
それを使って a 年後に移動した場合は floor( a / 2 ) 歳だけ年を取る.
a 年前に移動した場合は floor( a / 4 ) 歳だけ若返る.
それぞれのwormhole は入力で与えられたとある年からとある年に移動することができる.

負の枝はあるものの,負の閉路はないのでダイクストラすれば良い.

I. Tribute (Editor)
読んでない.

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

2008年11月23日20時から5時間,10問.
[ Link ]

7問解いた.解けなかったのはCとEとJ.
Bに嵌りまくってた…,もっと確り考えないといけない.
しかし,面白い問題が無尽蔵に湧き出てくるなぁ…,ICPCの季節素敵.

A. Equilibrium Mobile
文字列処理 + 超絶Ad-hoc.
これは解く過程がとても楽しかった.良問題.

高々高さ16の完全2分木が与えられたとき,全ての場所で左右にある重さの合計を等しくしたい.
最低で葉の重みを何個変えれば良いかを求める問題.
ヒントは完全2分木であることから,考えるべき木全体の重さの合計値はある程度絞られる.

B. Proving Equivalences
グラフ理論.
n 個の命題が同値であることを示すためには,最低後何回の証明を必要とするかを求める問題.
1回の証明では,AならばBなどといったことしか証明できない.
また,今すでに証明できている事柄が与えられる.

強連結成分に分解して,入次数,出次数とかに着目する.

C. Cat vs. Dog
犬達と猫達がいて,コンテストを行っている.
各々の人が次のラウンドに残したい動物1匹と残したくない動物1匹を投票する.
投票した中には犬と猫が1匹ずつ含まれる.
各々の人が満足する条件は残したい動物が残る かつ 残したくない動物が残らない.
最大で何人の投票者を満足させることはできるかという問題.

D. Disgruntled Judge
線形合同法で乱数を発生させる.法は10001.
入力は x[0], x[2], ... x[2n] で, x[1], x[3], ... x[2n+1] を出力せよという問題.

E. Easy Climb
n ステップ分の地形の高さが与えられる.
最初と最後の高さは変えられないが,他の高さは変えられる(高さを1変えるごとにコストが1かかる).
隣り合う2箇所の高さの差が d 以下となるようにするための最小コストを求める問題.

F. Sculpture
3次元空間上で xyz それぞれの軸に沿うように n 個の直方体が置いてある.
それらの直方体からなる図形の表面積と体積を求める問題.
ただし,直方体で囲まれた領域にも便器上直方体が入っていると思う.

塗りつぶせば良い.

G. Matchsticks
Greedy + Ad-hoc.もしくはDPなどでも多分可.
n 本のマッチを使って 7-segment 文字で数字を作る.
作れる最小値と最大値は幾らか.

H. White Water Rafting
内部の多角形と外部の多角形が与えられる.
内部の多角形は外部の多角形に含まれる.
内部と外部の多角形の間を一周できる円の最大の半径を求める問題.

全部の辺に対して,線分と線分の距離を求めて最小値を返せば良い.

I. Shuffle
長さ無限の数列の一部として,長さ n の数列が与えられる.
その数列は s ごとに区切れば 1 ~ s の数字が1個ずつ含まれる.
区切る場所として在り得るのは何通りか,を求める問題.

やるだけ. O( n + s ).

J. Videopoker
酷く不親切な問題.問題に定義ぐらいは書いて欲しいと思うのだが….
ポーカーの役ごとの倍率,現在の手札が与えられる.
1回だけカードの交換ができる場合,最適なカードを交換した場合のできる役の倍率の平均値を求める問題.

SRM426 DIV1 (この記事を編集する[管理者用])

2008年11月23日02時から.
[ overview ] [ otinn.com summary (Japan) ]

今回は全体的に問題文の英語が長め.
難易度的には少し簡単な問題セットかも.

EASY (250pt)
シミュレーション + α.
シャッフルの仕方とシャッフル後何番目のカードがもらえるかという情報が与えられるので,
最初のカード配置を自由に弄れるとき,得られる有用なカードを期待値の最大値を求める問題.

MEDIUM (500pt)
辺の長さに対する二分探索 or 時間に対する三分探索.
2次元平面上で等速運動を続ける鼠の初期位置と速度ベクトルが与えられたとき,
全ての鼠を捕らえることができる正方形の箱の辺の最小値を求める問題.
ただし,正方形の箱は x 軸 y 軸に沿うように置かなければならない.
箱を投下する時間は 正であればいつでも良い.

二分探索の方が面倒で実行時間も長い.
三分探索は数学的な考察がちょっとだけ必要.
また,最終的に必要な辺の長さの精度を考えて,十分なだけの精度を得なければいけない.

HARD (1000pt)
今まで見た看板の内容が順番に与えられる.
看板には,どこどこまで後どのぐらいの長さがあるかが書かれている(複数かもしれない).
今は最後の看板にいる.目的地までの距離を求めよ.
ただし,矛盾がある場合,目的地を既に通り過ぎている場合はそれを指摘せよ.

ACM ICPC::South America Regional Contest (Live) (この記事を編集する[管理者用])

2008年11月16日03時から5時間,11問.
[ Link ]

GCJ World Finalsのため参加できず.
UVaのコンテストランキング稼ぎのためには良い問題セットだったのになあ,11問もあるし.

A: Almost Shortest Path
有向グラフと始点,終点が入力.
全ての最短路の枝が含まれないような,パスのうち,最短路の長さを求める問題.
やるだけ,ダイクストラ2回やれば良い.

B: Bases
例えば9*6=42という形の式が入力.
左辺,右辺ともに,演算子は+と*のみ含まれる.
その式が成り立つのは何進数で考えればよいか.そのような基数を全て答えよ.

C: Candy
2次元の升目にいくつかのCandyが置いてある.
あるマスのCandyを取ると,そのマスの上の行,下の行の全てのCandy,そのマスの左右のマスのCandyが消える.
最高で何個Candyを取ることができるか.

DP.
まず各行について最大何個取れるか調べる.
その後,同じようなことを列に対して行う.

D: DNA Sequences
文字列が2つ与えられたとき,その文字列から k 文字以上の連続した区間をいくつか取り出して共通の文字列を作る.
その共通の文字列の最大長さは幾らか.

典型的なDP.
O( 1つ目の文字列の長さ * 2つ目の文字列の長さ * k )で通る.

E: Electricity
日付をちゃんと扱えますか,という問題.
入力データの中に,連続した日付があれば処理をするだけ.

F: Feynman
n * n の盤面で,正方形の数はいくつあるか.
k^2.

G: Pole Position
最初の順位からの相対順位が与えられたとき,最初の順位を求める問題.
最初の順位は 今の順位 + 相対順位 なので,それを埋めていくだけ.

H: Higgs Boson
2つの粒子の軌道が与えられたとき,最初に衝突する時間を求めよ.
粒子の軌道は,極座標形式で, rθ は 時間 t に関する一次関数で与えられる.

きっとやるだけ.

I: Traveling Shoemaker Problem
ある地域は最大で2個の連盟に所属している.
地域間の移動は,同じ連盟に所属していなければ移動できない.
さて,全ての地域を1回ずつ移動するルートが存在すれば,そのスタート地点として可能なもののうち最初のものを求める問題.

J: Bora Bora
シミュレーションやるだけ.Unoみたいなの.
前に捨てたカードと同じスートまたは同じ数字であれば捨てれる.
捨てるカードがなければ山札から1枚引く.引いたカードは即座に捨てれる.
Qを捨てるとプレイ順番が反転.
A, 7, 11を捨てると次の順番の人は飛ばされる上に,7だと2枚,Aだと1枚カードを山札から引かなければいけない.
最初にカードがなくなる人は誰か.
山札はプレイするのに十分すぎる量があると仮定してよい.

K: Shrinking Polygons
円周上の n 点からいくつかの点を取り除いて正多角形を作る.
最小でいくつの点を取り除けば良いか.
入力は,各点の間の弧の長さが与えられる.

可能性があるものを全て調べればよい.

Google Code Jam 2008 World Finals (この記事を編集する[管理者用])

2008年11月14日09時15分(カリフォルニア時間)から3時間,5問.
[ Link ]

実質1問も解けなかったと言って良い成績でした.
しかし,冷静になって考えても今の自分だと妥当な成績としか思えなかったので,単純に実力が足りなさすぎます.
取り敢えず,良質問題セットだったと思います.
基本的に知識は必要ない,実装も重くない,閃くかどうかが鍵となる問題達でした.
要するに頭悪いと苦しいorz

A. Juice
3種類の材料を混ぜて容量10000のジュースを作る.
飲む人が n 人いるんだけど,それぞれ材料1,材料2,材料3を幾ら以上含んでないと嫌だという情報が与えられる.
最大で何人を満足させることができますか,という問題.
n <= 5000.

segment treeを使ってごにょごにょする.
実は全探索っぽくO( n^3 ) でも通ったりする(並列化なしで).

B. Ping Pong Balls
ある場所にボールが当たると,その場所からある2方向にボールが発射される.
最初にある場所にボールを当てた場合,最終的にボールが発射された場所の数はいくらか.

色々と場合分けしながら注意深く実装すれば良いような気がする.

C. Mine Layer
マインスイーパー.
上下左右斜め直下の9マスのうち,地雷が埋まってるマスの数が書かれているマップが与えられる.
中央の行に埋められている地雷の数の最大値を求める問題.
そのようなマップに対応する地雷の配置が少なくても1つは存在することは保証されている.

実は各行の地雷の数は一意に定まる.
列の数が3の倍数ならば,2列目,5列目…の数字を足せば,前後含めて3行に埋まっている地雷の数が求まる.
列の数が3の倍数でなければ,1列目,4列目…の数字を足せば同じ.
後は,(三重対角行列の)連立一次方程式を解けば良い.

D. Bridge Builders
各場所にエッジを作るのに必要なコストは移動可能な資材置き場からの距離の最小値.
最初はエッジが全くなくて,ある資材置き場のノードからスタートして,グラフを連結にするまでに必要なコストの最小値を求める問題.

E. The Year of Code Jam
2次元マップ上に,青いマス,白いマス,どっちに塗っても良いマスが与えられる.
各青いマスに対して,
 4 - 上下左右にある青いマスの数
がスコアとして与えられる.
スコアを最大化せよという問題.

smallはDP + 枝刈り.
largeはflowで解けるらしい.

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

GCJにもっていってコンテスト中聞いていた曲リスト(一部)を晒してみる.
APACがLIST1,FINALがLIST1+LIST2.
今でもダウンロードできる曲はリンクをはってある.

続きを読む

闘神都市3 (この記事を編集する[管理者用])

GCJに闘神3の販促ムービーから主題歌録音してコンテスト中に聞こうと思っていたのにすっかり忘れてもっていけなかった.

システムみて,よくわからないけど結構楽しそうだ.
ところで,戦闘が3Dなんだろうけど,大会での対人戦も3Dなんだろうか?
販促ムービーには戦闘中の一枚絵みたいなのが出てきた気がするんだけど….
後,女の子モンスターはいるのかな?
ラッパを吹いていて,やたらと強いモンスター呼ばれると死亡確定なのとか,回避率が異様に高いモンスターとか,バリエーション豊かなのでいて欲しいんだけどなー.

SRM425 DIV1 (この記事を編集する[管理者用])

2008年11月13日01時から.
[ overview ] [ otimm.com summary (Japan) ]

EASYとMEDIUM早解き問題セット.

EASY (250pt)
1ステップで上下左右のどれかに移動するけど,その確率が与えられる.
n ステップ後まで,同じ場所に2回以上立ち寄らずに移動する確率を求める問題.
n <= 14.
全探索.粗く見積もっても2回目以降の移動は3方向しか考えなくていいので 4 * 3^13 ぐらいしか調べなくて良い.

MEDIUM (500pt)
5×5のマップに最大5人までいる.
全員が隣接してる状態になるのに必要な最小移動距離(マンハッタン距離)はいくらか.
状態数が 25C5 程度しかないのでBFSする.

HARD (1000pt)
ノード数 n の完全グラフが与えられて,それぞれの枝に確率が壊れる定義されている.
それぞれの枝が壊れるかどうか判定した後,壊れなかった枝だけ拾ってきたら全域木になっている確率を求める問題.
n <= 16.

ACM ICPC::Dhaka Regional Contest (Live) (この記事を編集する[管理者用])

[ Link ]
2008年11月08日18時から5時間30分,10問.
カテゴリをICPCにするかUVaにするかLive Archiveにするか迷ったけどUVaにする.

開始時間を勘違いしてて途中参戦.
それにしても,5問しか解けなかったのは酷すぎるなぁorz
しかし,結構難しい….

A. Find the Format String
Ad-hoc.

B. Switch Bulbs
BFSで探索.
クエリがたくさんあるけど,1回全部探索しておけば良い.

C. Schedule of a Married Man
やるだけ.
2つの区間が重なっているかどうかの判定.

D. Puzzles of Triangles
Math.
これは結構面白いと思った.
素因数分解してごにょごにょすれば答えが求まったりする.

E. Chemical Plant
読んでない.

F. Clicking Checkboxes
DP.
テストケースがたくさんあって,毎回DPで計算するとTLEもらえるので,
1回計算するだけで大丈夫な形でしておくと良い.

G. Magic Rings
謎.
幾何 + DP + 2分探索かと思ったけど実行時間が長すぎて断念した.

H. Line Chart
謎.
ACM/ICPC的にはこの問題文は大丈夫なのか….
DPかと思ったが,単純にやるとメモリも実行時間も厳しい.

I. Mobile Towers
読んでない.

J. Stopping Doom's Day
Math.解けてない.

SRM424 DIV1 (この記事を編集する[管理者用])

2008年11月06日21時から.

今回はずいぶんと簡単な問題セット.
なんだけど,準備的な問題で失敗したー.
まぁ,今回の点数と引き換えにライブラリがパワーアップしていくので良かったと思っておこう.

EASYでN=1でチャレンジできるなーと思ってたらサンプルにあったのね….
皆優秀すぎると思ったよ….

EASY (250pt)
Math.
各桁の積が与えられた数字になるような数字のうちでもっとも小さいものの桁数を答えよ.
9から2まで割っていくだけ.

MEDIUM (600pt)
ちょっと捻っただけのDP.
600ptだけど,難易度的には,いつもの500ptとさほど変わらないか,むしろ少し簡単な問題.
ただ,EASYとHARDが実装量が少なすぎるので,妥当な点数かもしれない.

コンパイルエラーで意味不明な文字列がどばーって出てきて嵌ってた.
そして,調べていくと,エラーが出ているのはプラグインが勝手に生成したサンプルを実行させるところだったので,取り敢えずArenaで全部サンプル通ること確認して提出した….

HARD (900pt)
segment tree.
自分のライブラリの似非segment treeだと最初TLEもらって,絶望の果て5分か10分ぐらいぼーっとしてしまったorz
Javaでも解けるようにできているんだから,似非とはいえCで解けないわけないと高速化してみたところ,
関数呼び出しで構造体コピーしまくってるのをポインタ渡すようにしただけで3倍高速化された….
そうだよね,そんなもんなんだよね….

よくよく考えると,似非segment tree2つ使ってたんだけど,1つで十分だったりするので,まだまだ高速化はできるはず.

サマータイム (この記事を編集する[管理者用])

次回のTopCoder SRM424は6日の午後9時から.
アメリカのサマータイムが終わったので,1時間遅くなるので注意しておこう….
アメリカのサマータイムは3月の第2日曜日から11月の第1日曜日まで.

U Calgary Local contest (この記事を編集する[管理者用])

[ Link ]
Calgary Collegiate Programming Contest 2008.
2008年11月01日20時から4時間,8問.
簡単な問題セットのコンテスト.予約投稿.

Problem A - Automatic Answer
本当に書くだけ.
入力 n に対して,
 ( n * 567 / 9 + 7492 ) * 235 / 47 - 498
の十の位の数字を答える問題.

Problem B - Blackboard Bonanza
全探索.
与えられた文字のうち,2つを選んで,適当にずらして書いても良くて,同じ位置に同じ文字ができるだけ多く来るようにしたい.
最大で何個同じ文字が同じ位置に来るか求める問題.

Problem C - Calculator Conundrum
与えられた数字を上位から n 桁のみ残しながら何回も2乗していく.
そうやってできる無限数列の中で最大の要素は何ですか,という問題.
同じ数字が2回出てくるまで計算して,今まで計算した中で最大の数字を答えればよい.
計算量が見積もれなくて心配だったけど,実際に大きなテストケース入れてもほぼ一瞬で答えかえってきたので送ったら通った.

Problem D - Demanding Dilemma
頂点数 n ,枝数 m の単純無向グラフにおいて,
n × m の { 0, 1 } 行列を次のように定める.
 i , j 成分が 1 なのは 枝 j の端点の1つが i である
さて,n × m の { 0, 1 } 行列が与えられたとき,それはちゃんと頂点数 n ,枝数 m の単純無向グラフに対応してますか,という問題.

それぞれの枝に対して,つながっているノードの数が2でなければ No .
後,全く同じ枝があれば No .

Problem E - Experienced Endeavour
あからさまに行列の r 乗を求めて下さいと書いてあるようにしか見えない問題.

Problem F - Fewest Flops
文字列を等間隔に幾つかに分けて,その中ではそれぞれ独立に並び替えることができる.
で,同じ順番にまたくっつけたとき, chunk の数の最小値はいくらか,という問題.
chunk とは同じ文字が連続している区間のことで,
 aabfhhhhysaa
だと
 (1) aa (2) b (3) f (4) hhhh (5) y (6) s (7) aa
で7個.
DPで計算するだけ.

Problem G - Grid Game
n 次正方行列 ( n <= 8 ) が与えられてゲームをする.
1ターンの行動は,先手はまだ選んでない行を選び,その後に後手はまだ選んでない列を選ぶ.
その交点に当たる数字が先手の得点.
先手は得点が大きくなるような最適戦略,後手は得点が小さくなるような最適戦略をとったとき,結果は何点か?という問題.

後手が最適戦略なので,先手が選ぶ順番なんて関係ないので, n ! 通り調べてもっとも点数が小さいのが答え.

Problem H - Hapless Hedonism
Math.
長さ 1 から 長さ n までの棒を1個ずつ,合計 n 個持っている.
この中から3本選んで三角形が作れる選び方は何通りあるか?
n <= 1000000.
O( n ) で全ての入力に対する答えが計算できる.
というか,全く同じ問題,あるいは同じ長さの棒を2本以上使って良いバージョンの問題UVaに既にあった気がする….

ミステリートWindows ~八十神かおるの挑戦!~ (この記事を編集する[管理者用])

続きを読む

Appendix

Recent Articles

ブログ内検索

Ads


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