Entries

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

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

April 2011 Cook-Off 5問目 - A Prime Conjecture (この記事を編集する[管理者用])

Source

codechef April 2011 Cook-Off 5問目
Problem Statement
codechef April 2011 Cook-Offの参加記録

問題概要

63以上1000000未満の奇数Nが与えられるので,
 N = x + y^2 + z^3
となる素数の組(x,y,z)を1組求める問題.
存在しないなら,それを指摘する.

解法

yとzに関して全探索して,N - y^2 - z^3が素数ならそれをxにしておしまい.
ちなみに,予想は数学的に証明できてないだけで,小さいケースだと全部正しい(つまり解がある)と思うと嵌る.解がないこともある.

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

続きを読む

April 2011 Cook-Off 3問目 - Internet Media Types (この記事を編集する[管理者用])

Source

codechef April 2011 Cook-Off 3問目
Problem Statement
codechef April 2011 Cook-Offの参加記録

問題概要

拡張子とメディアタイプの対応関係 (100個以下) が与えられる.
ファイル名からメディアタイプを求める問題.
拡張子とは,ファイル名の最後の「.」より後ろの部分で,「.」が含まれていない場合は拡張子なし.

解法

文字列系実装問題.やるだけ.

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

続きを読む

April 2011 Cook-Off 1問目 - The Grand Cook Off (この記事を編集する[管理者用])

Source

codechef April 2011 Cook-Off 1問目
Problem Statement
codechef April 2011 Cook-Offの参加記録

問題概要

N人のシェフがそれぞれ持っているコインの数 a[k] が与えられる.
毎ターン,コインを持ってるシェフをランダムに2人選んで戦わせる.
勝った方が,負けた方のコインを総取りできる.
最終決戦時の2人の所持コインの差の期待値を求める問題.
コインの数の和は100以下.

解法

結局2つのグループに分けて,それぞれのグループのコインの総和の差の期待値を求めれば良い.
片方のグループが1人~N-2人になる確率は等確率であることが確かめられる.
後は,今まで着目した人数と,片方のグループの人数と,現在のグループ間のコインの和の差,を状態にして,その状態に遷移するパターンが難パターンあるかをDPで数え上げれば良い.
O(N^2*C)程度.Cはコイン総和.

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

続きを読む

April 2011 Cook-Off (この記事を編集する[管理者用])

2011年04月25日01時から2時間30分,5問.
[LINK]

難しかった.1位でも3問.
3問解いて9位.結果的に早解き勝負になってしまってたので,5問目で手間取ったのが痛かった.

・1問目 The Grand Cook Off
手計算で小さいケースをやってみたところ,最終的に残る人のうち,1人に着目すると,その人が他の何人のコインを吸収しているかが
 1人~N-2人
が全部等確率になることが推測できたので,後はDPするだけ.とやったけど,それを使い忘れてあたふたしてた.
・2問目 Product of Digits Again (解いてない)
適当な範囲まで基数を全部試せばよいかと思ったけど,当然のごとくWA.
Aを求めるのもgreedyにやったけど,それでいいかどうかも不安.
・3問目 Internet Media Types
やるだけ.
全部文字列が一致するかどうか試した.
ニコ動に動画あげてみたところ,map使うんだと思ってたと言われたけど,たしかになぜそうしなかったのかわからない.
C++じゃなくてCだけど,自前ライブラリのハッシュを使った文字列のマップもどきを使えばすごい楽に解けたはず.
・5問目 A Prime Conjecture
テストケースも1000とちょっと多めだったし,3重ループを回して,全入力ケースの答えを求めようとしてしまった.
ローカルでは0.5秒ぐらいで終わるのだけど,codechef側では2秒で終わらずTLE.
素直に,1ケースずつ求めるようにして通した.1WA+手間取った時間がもったいない.

Beta Round #69 DIV1 C問題/DIV2 E問題 - Beavermuncher-0xFF (この記事を編集する[管理者用])

Source

Codeforces Beta Round #69 DIV1 C問題 (1500pt)
Codeforces Beta Round #69 DIV2 E問題 (2500pt)
Problem description
Beta Round #69 DIV1の自分の参加記録

問題概要

ノード数N (10^5以下) の木が与えられる.
それぞれのノードにいるビーバーの数が与えられる.(各ノード1以上10^5以下)
出発ノードも与えられる.
あるノードからあるノードに移動すると,移動先のノードにいるビーバーを1匹取り除く.
移動先にビーバーがいないと移動できない.
最終的には出発ノードに戻ってこなければいけない.
取り除けるビーバーの総数の最大値を求める問題.

解法

下から組み立てていく.
各ノードに対して,そのノードに上 (根に近いほう) から来たとして,その部分木でどれだけのビーバーを取り除けるかを求める.
また,その際に,greedyに下の部分と行ったり来たりしておき,そのノードのビーバーの残り数も求めておく.
(その上のノードと行ったり来たりするのにどれだけできるかを,上のノードの計算で使う)

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

続きを読む

Beta Round #69 DIV1 B問題/DIV2 D問題 - Falling Anvils (この記事を編集する[管理者用])

Source

Codeforces Beta Round #69 DIV1 B問題 (1000pt)
Codeforces Beta Round #69 DIV2 D問題 (2000pt)
Problem description
Beta Round #69 DIV1の自分の参加記録

問題概要

非負整数a, bが与えられる.
実数pが[0,a]の一様分布,qが[-b,b]の一様分布に従うとき
 x^2 + sqrt(p) * x + q = 0
が少なくても1つ実数解を持つ確率を求める問題.

解法

判別式p-4qが正になる確率を求めれば良い.
長方形(0,-b)-(a,b)のp-4qが正の部分の面積の割合と考えると分かりやすい.
p-4qの線分が長方形のどこの辺を通るかで場合分けが必要.
aやbが0の時は例外処理が必要で気をつける.

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

続きを読む

Beta Round #69 DIV1 A問題/DIV2 C問題 - Heroes (この記事を編集する[管理者用])

Source

Codeforces Beta Round #69 DIV1 A問題 (500pt)
Codeforces Beta Round #69 DIV2 C問題 (1500pt)
Problem description
Beta Round #69 DIV1の自分の参加記録

問題概要

7人の勇者と3匹のボスがいる.
勇者達は3つのパーティーを作ってボス退治をする.
各勇者はちょうど1つのパーティーに含まれていなければならない.
各ボスの経験値が与えられる.
n人パーティーで経験値eのボスを退治すると,1人あたりfloor(e/n)の経験値が得られる.
また,各勇者が,自分が好きな勇者のリストが与えられる.
勇者Aが勇者Bのことが好きならば(A,B)と書く.
 1) 得られる経験値が最も多い勇者と少ない勇者の差を最小化,その中で
 2) 好きな勇者とできるだけ同じパーティーにする
   つまり,(A,B)かつAとBは同じパーティー なるペアの数を最大化する
そうしたときの経験値の差と,ペアの数を求める問題.

解法

3^7通り全探索する.

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

続きを読む

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

2011年04月20日00時15分から2時間,5問.codeforcesルール
[ LINK ]

Codeforcesでは初めてのDIV1とDIV2で問題セットの異なるコンテスト.
DIV1は配点が500-1000-1500-2000-2000でした.

A. Heroes

7人の勇者と3匹のボスがいる.
勇者達は3つのパーティーを作ってボス退治をする.
各勇者はちょうど1つのパーティーに含まれていなければならない.
各ボスの経験値が与えられる.
n人パーティーで経験値eのボスを退治すると,1人あたりfloor(e/n)の経験値が得られる.
また,各勇者が,自分が好きな勇者のリストが与えられる.
勇者Aが勇者Bのことが好きならば(A,B)と書く.
 1) 得られる経験値が最も多い勇者と少ない勇者の差を最小化,その中で
 2) 好きな勇者とできるだけ同じパーティーにする
   つまり,(A,B)かつAとBは同じパーティー なるペアの数を最大化する
そうしたときの経験値の差と,ペアの数を求める問題.

寝過ごした,というか起きたけど布団の中が気持ちよかったので10分近く遅れで参加.
(ホントはもっと遅れてたけど,Codeforcesの方も15分開始が遅れたので正味10分近く遅れ)
問題文なげぇ.
固有名詞出されるとそこで躓く.
これって勇者だっけ,ボスだっけ….
理解.
3^7パターン全探索するだけ.
書く.がりがり.
サンプル通った.提出.pretest passed.

B. Falling Anvils

非負整数a, bが与えられる.
実数pが[0,a]の一様分布,qが[-b,b]の一様分布に従うとき
 x^2 + sqrt(p) * x + q = 0
が少なくても1つ実数解を持つ確率を求める問題.

問題文読みにくい….
と思ったら,ストーリーはよくわからんけど,問題の意味はすんなりわかった.
えっと,とりあえず判別式だ.
判別式ってどうだっけ,根のルートの中身だから….
 p - 4q
が0以上になる確率を求めれば良い.
えっと,pを固定したら,qと確率は線形であるから….(嘘ですよ!)
p=0の時の確率とp=aの時の確率を足して2で割れば良い.
p=0の時は…,えっと…,b=0とかだったら嫌だな.
例外処理しておこう.
 a=0, b=0なら即座に0
 a=0なら即座に1/2
 b=0なら即座に1
よしよし.
じゃ,p=0の時は,1/2でよし.
p=aのときは,-4qが[a-4b,a+4b]まで動くから….
 (a+4b) / 8b
だな.
合わない.
試行錯誤.
a=0の時,最後で2で割るの忘れてた.サンプル通った.
サブミット.WA.えー.
コーナーケース間違えてるよ!
 a=0, b=0なら即座に1
でも,これはpretestにないはず.
あれ….
 (a+4b) / 8b
って確率なのに1超えないか?

aが4bを超えると,pが小さい時に線形で,そこから確率1で固定.
場合分け.
書いた.サブミット.WA.
あれ….
適当にaが大きいケースを試してみる.
1.2とか返ってきた.なんでやねん.
あ,式間違ってる.修正.
サブミット.pretest passed.
苦戦しすぎ….

C. Mushroom Strife

ノード数N (10^5以下) の木が与えられる.
それぞれのノードにいるビーバーの数が与えられる.(各ノード1以上10^5以下)
出発ノードも与えられる.
あるノードからあるノードに移動すると,移動先のノードにいるビーバーを1匹取り除く.
移動先にビーバーがいないと移動できない.
最終的には出発ノードに戻ってこなければいけない.
取り除けるビーバーの総数の最大値を求める問題.

greedyかDPか,どっちかの気がする.
が,DPだと状態数が死ぬなぁ….
うーん.
取り敢えず,行ったり来たりで消費するのは最終手段で,いける場処はできるだけ色々行ったほうが良いんだな.
で,行ったり来たりで消費するのは,子供の方からgreedyに消費していけば良い.
子供の方から組み立てて行けばいいじゃん.
書く.
ちょっとめんどい.
書いた.サブミット.WA.
あれ.
テストケースつくって試す.
行ったり来たりで消費するのを全くしてない.
変数間違ってた….修正.pretest passed.

D. Domino Carpet

ちゃんと読んでない.

E. Martian Food

ちゃんと読んでない.

Hacks

何もせず.

Results

ABC通る.
pretestがだいぶ強力だった.(のだけど,落ちてる人は時々落ちてる)

April 2011 Challenge 6問目 - Rectangles Counting (この記事を編集する[管理者用])

Source

codechef April 2011 Challenge 6問目
Problem Statement
April 2011 Challengeの参加記録

問題概要

2次元平面上の格子点がN点 (10^5以下) 与えられる.
その格子点から4つ選んで,革変がx軸y軸に平行な長方形は何パターン作ることができるかを求める問題.
同じx座標に3点以上ないことを仮定して良い.
座標の値の絶対値は10^9以下.

解法

同じx座標に2つの点があるものを取り出してきて,そのy座標の組が一致するものが何個あるか数える.
ハッシュなりsetなりに突っ込んで数えれば良い.

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

続きを読む

April 2011 Challenge 5問目 - Number Game Revisited (この記事を編集する[管理者用])

Source

codechef April 2011 Challenge 5問目
Problem Statement
April 2011 Challengeの参加記録

問題概要

2人でゲームを行う.順番に行動し,打つ手がなくなったら負け.先手必勝か後手必勝か判定する問題.
最初正整数N (10^9以下) が書かれている.
1または2以上N未満の素数を選び,Nから引く.(N=1のときは1も選べず負けになる)

解法

取り敢えず小さい範囲で全探索してみると,n mod 4 = 1の時のみ後手必勝になることがわかる.
何故かというと,結果が分かってしまえば,例えば必勝法としては,
 2には2で返す
 4n+1には3で返す
 4n+3には1で返す
ことで,mod 4で不変にできることに気づく.(4nは素数じゃないから打てない)

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

続きを読む

April 2011 Challenge 4問目 - Gravel (この記事を編集する[管理者用])

Source

codechef April 2011 Challenge 4問目
Problem Statement
April 2011 Challengeの参加記録

問題概要

n個 (10^6以下) の山にそれぞれ最初c個 (10^9以下) の石が積んである.
やるべき操作がm回 (250000以下) 与えられるので,それを行う問題.
 u番目~v番目の山にそれぞれk個の石を加える
 p番目の山の石の数を答える

解法

Fenwick tree.
増減の配列だけ用意しておいて,各山の石の個数は,ここから左の配列の和という形にする.

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

続きを読む

April 2011 Challenge 3問目 - Graphs in Euclidean Space (チャレンジ形式) (この記事を編集する[管理者用])

Source

codechef April 2011 Challenge 3問目 (チャレンジ形式)
Problem Statement
April 2011 Challengeの参加記録

問題概要

連結なノード数 N (300以下) のグラフのそれぞれの接点までの最小距離の行列が与えられる.
三角関係式を満たす. dist[a][b] は dist[a][k]+dist[k][b] 以下.
その距離の関係をできるだけ満たすように,各ノードをd次元のユークリッド空間に埋め込む問題.
dは1以上20以下で好きに選んで良い.
座標の値は絶対値が1000000を超えてはいけなくて,整数でなければいけない.
ノードaとbの間の,与えられたグラフ上での距離をdist[a][b]として,実際に埋め込んだユークリッド空間での距離をx[a][b]とすると,
 x[a][b] / dist[a][b]
の最大値をmax,最小値をminとして
 d * max / min
がスコアになる.スコアは小さいほど良い.

解法

最初ランダムに配置,
 x[a][b] / dist[a][b] = max
となるノード対を見付け出して,そのノード間の距離を縮める,
 x[a][b] / dist[a][b] = min
となるノード対を見付け出して,そのノード間の距離を広げる,を繰り返した.
どうやらうまい埋め込む多項式時間アルゴリズムがあるらしい….

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

続きを読む

April 2011 Challenge 2問目 - Generalized Independent Sets (この記事を編集する[管理者用])

Source

codechef April 2011 Challenge 2問目
Problem Statement
April 2011 Challengeの参加記録

問題概要

ノード数n (500以下),枝数m (2000以下)の無向グラフが与えられる.
各ノードには重みf(v)が与えられており,f(v)の値は0以上1以下の実数.
サイクルで,サイクルに含まれるノードの重みの和がfloow(L/2)を超えるものを1つ出力する問題.
ただし,Lはサイクルの長さ (含まれるノードの数).
もしくは,そのようなサイクルが存在しないならそれを指摘する.
枝の両端が同じノードになっていることはないと仮定して良い.
枝(u,v)があるなら,u-v-uは長さ2のサイクルとして認める.

解法

条件を満たす長さ2のサイクルがなければ,偶数長のサイクルは作れない.
また,その時,全て重みに-0.5を足したとき,無限に重みの和が小さくなるようなサイクルは存在しない.(*)
よって,長さ奇数で,重みに全部-0.5足したとき,重みの和が-0.5を超えるようなサイクルを探せば良い.
これは,ダイクストラで求めることが可能.ダイクストラは(*)の性質により無限ループに陥ることはない.
(が,長さが負の枝は有りうるので,同じノードを1回しか処理しないダイクストラではない)
現在までに奇数個のノードを経由したか,偶数個のノードを経由したか,でノード数を2倍に拡大する.

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

続きを読む

April 2011 Challenge 1問目 - Central Point (この記事を編集する[管理者用])

Source

codechef April 2011 Challenge 1問目
Problem Statement
April 2011 Challengeの参加記録

問題概要

2次元平面上のN点 (2000以下) が与えられる.
そのN点までのユークリッド距離の和が最小となる格子点を選んだ時,その距離の和を求める問題.
与えられる点の座標の絶対値は10^9以下.

解法

最初,格子点でなく,整数座標以外の点も許して,山登り法で適当に和が小さくなる方に動かしていく.
後は,その周辺の格子点を全部調べる.
想定解法は,徐々に近づくていくのではなく,3分探索を使うみたい.

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

続きを読む

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

2011年04月01日18時30分から11日間,6問.(1問はマラソン形式)
[LINK]

サーバ不調のためもともと10日間の予定が11日間になった.
全部解いたが,マラソン形式の問題が惨敗.

・1問目 Central Point
くだらないミスしてWA.座標ごとに三分探索でWA.徐々に近づけていってAC.しかし想定解法は三分探索らしい.
・2問目 Generalized Independent Sets
条件を満たす長さ2のサイクルがなければ,長さ2nのサイクルもないことに気づくのに時間かかった.
それがわかっても,それをうまく使えるようになるまでに時間がかかった.
・3問目 Graphs in Euclidean Space (チャレンジ形式)
一番比率が大きいのを小さくなるように,小さいのを大きくなるように動かしていった.上位には全然歯が立たなかった.
どうやら,効率の良い置き方を求める多項式時間アルゴリズムがあるらしい.

UVa 11986 - Save from Radiation (この記事を編集する[管理者用])

Source

A Contest dedicated to Renat Mullakhanov (rem) (2011-04-16) (blog)
UVa 11986

問題概要

N個 (10^16以下) の正常な水と,1個の毒水がある.
ねずみに毒水を飲ますと5分で死ぬ.
どれが毒水か,5分で判定するためには,最小でねずみが何匹必要かを求める問題.
1匹のねずみに何個の水を飲ませても良い.

解法

k匹のねずみがいれば,死ぬ死なないで2^kの状態を区別できる.
だから,Nの2進数での桁数.

UVa 11984 - A Change in Thermal Unit (この記事を編集する[管理者用])

Source

A Contest dedicated to Renat Mullakhanov (rem) (2011-04-16) (blog)
UVa 11984

問題概要

摂氏Cと華氏Fの変換公式は
 F = 9/5 C + 32
である.
最初摂氏C度で,その後,華氏でd度だけ上昇した.
最終的な温度を摂氏で求める問題.

解法

華氏は摂氏の5/9倍の影響しか与えないから  C + d * 5/9

UVa 11981 - Corrupted Friendship (この記事を編集する[管理者用])

Source

A Contest dedicated to Renat Mullakhanov (rem) (2011-04-16) (blog)
UVa 11981

問題概要

N個 (10^5以下) の招待状がある.
招待状を受け取った人は,自分用に1個確保し,自分の友達1人選んで残りの招待状をすべて渡す.
もう友達がいないなら,自分を招待してくれた人に残りの招待状をすべて返す.
返された場合も,まだ招待していない友達を1人選んで招待状をすべて渡す.
こうやって,最終的にN人の人が招待状を1枚ずつ持っている状態になった.
招待が成立した数と,招待された人の中で,確実に友達同士ではない組の数を求める問題.

解法

とりあえず,招待が成立した数はN-1でいい.
まず木を作る.
後は,それぞれ,あるノードの,子供Aの木のノード数,子供Bの木のノード数,…,を調べて,Aの木のノード数*Bの木のノード数などを足していく.
愚直にやると,子供が多いとTLEなので,子供の木Aと,それ以外の子供の木のノード数の和をかけて足していく.

UVa 11980 - Mad Scientist (この記事を編集する[管理者用])

Source

A Contest dedicated to Renat Mullakhanov (rem) (2011-04-16) (blog)
UVa 11980

問題概要

問題文で与えられたC++のコードと同じ出力をするコードを書く問題.
ただし,問題文で与えられたコードではTLEする.

解法

超絶adhoc.
最初にres1を求める.これを上の桁からビットがどうなってるか調べていくことで求まる.
res2はDPっぽくやって求めた.うまく説明できない.

UVa 11979 - Hamming Base (この記事を編集する[管理者用])

Source

A Contest dedicated to Renat Mullakhanov (rem) (2011-04-16) (blog)
UVa 11979

問題概要

N進数 (2以上2000以下) のM桁 (10以下) の数字がN個与えられる.先頭に0があっても良い.
各数字が,それぞれ,ある桁に同じ数字を持たないようにしたい.
1回の操作で,ある1つの数字のある桁を選び,それを+1するか-1することができる.
(ただし0の桁を-1することはできないし,N-1を+1することもできない)
最小操作回数を求める問題.

解法

各桁ごとに別々にやれば良い.
結局全部の数字を1回ずつ使わなければいけないので,greedyにやる.

UVa 11978 - Fukushima Nuclear Blast (この記事を編集する[管理者用])

Source

A Contest dedicated to Renat Mullakhanov (rem) (2011-04-16) (blog)
UVa 11978

問題概要

2次元平面上の単純な多角形と,円の中心が与えられる.(5000角形以下)
円と多角形の共通部分の面積が,多角形の面積のp%以上となる最小の円の半径を求める問題.

解法

2分探索 + 三角形と円の共通部分の面積.

UVa 11977 - Story of Tomisu Ghost (この記事を編集する[管理者用])

Source

A Contest dedicated to Renat Mullakhanov (rem) (2011-04-16) (blog)
UVa 11977

問題概要

n! (nは10^5以下) が少なくても下t桁 (1000以下) が0となるような最大の基数を求める問題.
存在しないならそれを指摘する.

解法

各素数pに対して,n!に素因数としてpがk個含まれるとしたら,基数がpのfloor(k/t)乗の倍数まで良い.
後はその値をかけていくだけ.

A Contest dedicated to Renat Mullakhanov (rem) (この記事を編集する[管理者用])

2011年04月16日18時から5時間,10問.
[ Link ]

rem氏追悼コンテスト.
時事ネタとして,福島原発関係の問題が2問.
問題は簡単なのから難しいのまでバランス良かった気がする.
忘れてて1時間遅れで参加.A, B, C, D, E, H, Jの7問解いた.

・問題A (解いた)
最大値を求める問題なのに,途中で満たす数を求める問題と勘違いし始めて泥沼.
・問題B (解いた)
円と三角形の共通部分のライブラリは昔作ってたライブラリセットにしか用意してなくて,昔それをつかってWAになったことがあった.
そして,今回もWA.
円と直線の交点を求める部分だけ,新しいライブラリに差し替えたら通った.誤差死かな?それとも昔のライブラリはバグってた?
・問題D (解いた)
うまく書けなかったり,バグりまくったりした.
でも,TLE解が与えられてることもあって,それを使ってデバッグして最終的には一発で通せたのは良かったか?

UVa 11976 - Time Deposit (この記事を編集する[管理者用])

Source

Huge Easy Contest II (2011-04-09) (blog)
UVa 11976

問題概要

平日とは月曜~金曜,休日とは土日のこと.
ただし,例外リスト (200日以下) で与えられるものはそれを優先する.
ある区間に含まれる平日の数を数える問題.
与えられる日付は1975-01-01から2025-12-31まで.

解法

範囲がそんなに広くないので,1日1日それが平日かどうか判定する.

UVa 11975 - Tele-loto (この記事を編集する[管理者用])

Source

Huge Easy Contest II (2011-04-09) (blog)
UVa 11975

問題概要

ビンゴゲームに似たゲームをする.
1~75までの数字が書かれた5*5の盤面が与えられる.
ひかれるボールのリスト (75個以下) が与えられたとき,それぞれの盤面のスコアを求める問題.
絵に書かれた4パターンが当たりで,黒くぬられた場所に該当するボールが全部制限時間内にひかれた場合に,その分のスコアが手に入る.
左からそれぞれ35個以内,40個以内,45個以内,75個以内にパターンに該当しないとダメ.
それぞれのスコアは入力で与えられる.

解法

やるだけ.

UVa 11974 - Switch The Lights (この記事を編集する[管理者用])

Source

Huge Easy Contest II (2011-04-09) (blog)
UVa 11974

問題概要

N個 (15以下) のランプと,M個 (100以下) のスイッチがある.
最初ランプは全部ついている.
M個のスイッチそれぞれに対して,どのランプの集合が対応しているか与えられ,そのスイッチを押すと,そのランプの集合に含まれるランプ全ての状態が反転する.
最小で,何回スイッチを押すことで全部のランプを消すことができるかを求める問題.不可能ならそれを指摘する.

解法

状態数2^NでBFSする.

UVa 11973 - Sierpinski Carpet (この記事を編集する[管理者用])

Source

Huge Easy Contest II (2011-04-09) (blog)
UVa 11973

問題概要

問題文の図のようにフラクタル図形を作る.図の縦横の長さは1.
ある点の座標が与えられるので,その座標は長さ 3 / 3^n の白い正方形に属すというnを求める問題.
与えられる座標は,0より大きく1未満で,小数点以下6桁までしかない.

解法

x, yの各座標を3倍して,整数部が両方1になると,一番大きい白い正方形の中.
後は,さらに,その小数部を3倍して,その整数部が両方1になると,次に大きい白い正方形の中,
というのを繰り返す.
doubleなどで計算すると誤差死するので,整数で計算する.

UVa 11972 - Round Trip (この記事を編集する[管理者用])

Source

Huge Easy Contest II (2011-04-09) (blog)
UVa 11972

問題概要

ノード数N (100以下),枝数M (1000以下) の無向グラフと始点のノードが与えられる.
同じ枝を2回以上使わずに,始点ノードから移動して,帰ってくることができるノードを全部求める問題.

解法

要するに,同じ枝を使わないそのノードまでの経路が2パターン以上あれば良い.
最大流を流す.

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

Source

Huge Easy Contest II (2011-04-09) (blog)
UVa 11971

問題概要

長さNの棒のK箇所 (50以下) をランダムに選び,その場所を切り,その棒を使ってK+1角形を作れる確率を有理数の形で求める問題.

解法

Nの値に関係なく,答えはKのみに依存する.
小さなケースでモンテカルロして答えを推測した.

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

Source

Huge Easy Contest II (2011-04-09) (blog)
UVa 11970

問題概要

正整数N (10^9) 以下が与えられるので,
 X / sqrt(N-X)
が正整数となる整数Xを全部列挙する問題.

解法

N-Xが平方数になるXに関して全部調べる.

Appendix

Recent Articles

ブログ内検索

Ads


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