Entries

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

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

October 2012 Cook-Off 5問目 - Tree Fun (この記事を編集する[管理者用])

Source

codechef October 2012 Cook-Off 5問目
Problem Statement

問題概要

ノード数N (50000以下) の木が与えられる.
クエリに答える問題.
各クエリ,2つ以上の要素から成るノードの集合Sが与えられる.
木からある1つのノードを取り除いて,集合Sのノードがすべて非連結にする方法の数を求める.
Sの集合のサイズの和が100000以下.

解法

とりあえず,根付き木と考えて,それぞれのノードの深さと,LCAをlog 高さぐらいで求めれるようにしておく.
|S|が2の時は,そのノード間の距離を求めて1引けば良い.
それは,それぞれの深さとLCAの深さから計算可能.
|S|が3以上の時は,答えは0か1.
該当するノードは,|S|の要素でなく,そこから|S|の各要素に1歩進んだとき,全部違う道を行くもの.
それの候補は,LCA(S[0], S[1]), LCA(S[1], S[2]), LCA(S[2], S[0])の中で,最も根から遠いものにすれば良い.
あとは,その候補の子供からは,高さの差-1だけ根に近づいて点が重ならないかを見て,それ以外の点はたかだか1個しかあってはいけない.

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

続きを読む

October 2012 Cook-Off 4問目 - Tennis Tournament (この記事を編集する[管理者用])

Source

codechef October 2012 Cook-Off 4問目
Problem Statement

問題概要

N = 2^K人の人でトーナメント戦をする.Kは30以下.
M人(10000以下)特殊能力者な人がいる.
特殊能力者の位置と,特殊能力者がそうじゃない人に勝つ確率(一律)が与えられる.
特殊能力者同士,そうじゃない者同士は勝率0.5.
特殊能力者が優勝する確率を求める問題.

解法

再帰.
各対戦について,左のツリーから特殊能力者が勝ち上がってくる確率,右のツリーから特殊能力者が勝ち上がってくる確率を求めていく.
範囲に特殊能力者がいない場所は,即座に0とすれば,O(K*M)ぐらいで解ける.

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

続きを読む

October 2012 Cook-Off 2問目 - Equalization (この記事を編集する[管理者用])

Source

codechef October 2012 Cook-Off 2問目
Problem Statement

問題概要

N要素の整数列が与えられる.Nは30以下,各要素は1以上1000以下.
以下の操作を繰り返して,全部の要素を一致させる方法を1つ求める問題.
ただし,操作回数は1000回を超えてはいけない.(最小回数である必要はない)
 素数個の要素を取ってきて,それらをすべて,取ってきた要素の平均値(整数とは限らない)に置き換える

解法

要素は何であろうとできる方法がある.
Nが素数なら全部の平均を取って終わり.
そうでなければ,Nを割り切る素数pを1つ取ってきて,配列をp個に分割して,各部分は再帰的に同じ要素になるようにしておく.
後は各要素から1個ずつ取ってきて,平均化する操作を,N/p回だけ繰り返せば良い.

続きを読む

October 2012 Cook-Off 1問目 - Buying Sweets (この記事を編集する[管理者用])

Source

codechef October 2012 Cook-Off 1問目
Problem Statement

問題概要

N個(100以下)の通帳の残高(100以下)が与えられる.
X円(100以下)のものを買う.
次の条件を満たす数Aだけ買いたい.
全部の銀行から預金を引き出さなければA個だけ買えないが,全部の銀行から預金を引き出せばA個買える.
Aを求める問題.複数あるなら最も大きいもの.存在しなけばそれを指摘する.

解法

答えの候補は,合計金額で買えるだけ買った時の数.
銀行を1つ残したら買えなくなったらいけないので,一番預金残高の大きい銀行を残してみて変えるかどうか試す.

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

続きを読む

UVa 12533 - Joining Couples (この記事を編集する[管理者用])

Source

Latin America Regional (2012-11-11)
UVa 12533

問題概要

Nノードの有向グラフを考える.(Nは10^5以下)
各ノードからはちょうど1つの枝が出ている.
Q個 (10^5) のクエリに答える問題.
各クエリは,ノードA, Bが与えられる.
各ターン,A, Bのどちらかが,枝にそって1個移動できる.
ノードが一致するまでの最小ターン数を求める.一致させられないならそれを指摘する.

解法

移動していくと,いずれループに陥る.ループは連結成分ごとに1つだけ(枝数の関係より).
そのため,同じ連結成分であれば必ず一致できる.
どのノードがループの一員かを調べておいて,ループ内のノードは順番に番号をつけておく.
ループのサイズと,ループ内のノードの番号から,ループの中では最小ターンがO(1)で求められる.
ループをルートとする木を考えて,ループに辿り着くまでの枝数と,ループに辿り着くノードの番号を計算する.
後は,LCAをdoubling等でO(log N)やO(1)求められるようにしておく.
すると,お互いLCAに移動するのが最小ターン数になる(距離はループに辿り着くまでの枝数から計算できる)し,
LCAがルートの場合,ループ内での最小距離も使えば求まる.

UVa 12532 - Interval Product (この記事を編集する[管理者用])

Source

Latin America Regional (2012-11-11)
UVa 12532

問題概要

N要素 (100000以下) の整数列Aが与えられる.各要素は-100以上100以下.
K個 (100000以下) のクエリに答える問題.各クエリは以下の2種類のうちのどちらか.
 C i v : A[i]をvに変更する
 P i j : A[i]*A[i+1]*...*A[j]が正か負か0かを求める

解法

Fenwick Treeを2つ使って,各区間の0の数,負の数の数を覚えておく.

UVa 12531 - Hours and Minutes (この記事を編集する[管理者用])

Source

Latin America Regional (2012-11-11)
UVa 12531

問題概要

アナログ時計を考える.
短針は12分毎に1回,1/60だけ回転する.
長針は1分毎に1回,1/60だけ回転する.
最初は一致していて,同時に動いた直後.
A度は短針と長針とのなす角としてありうるかどうかを判定する問題.
Aは0以上180以下.

解法

1/60ずつしか回転しないので,6の倍数でなければならない.
逆に6の倍数なら,そのような角になる時間が存在する.

UVa 12530 - Game of Tiles (この記事を編集する[管理者用])

Source

Latin America Regional (2012-11-11)
UVa 12530

問題概要

50*50以下のグリッドが与えられる.
幾つかのセルは黒く塗りつぶされていて,他のセルは白い.
2人でゲームを行う.順番に行動する.行動できなくなったら負け.先手必勝か後手必勝かを判定する問題.
 前回黒く塗ったセルの上下左右の白いセルを1つ選び黒く塗る.
 最初はどの白いセルを選んで黒く塗っても良い.

解法

各白いセルをノードと見なして,上下左右の白いセルに枝をはる.
そのようなグラフにおいて,完全マッチングが存在すれば後手必勝.
なぜなら,後手は,マッチングにそって動かせばいつでも動ける.
そうでなければ,先手必勝.最大マッチングに含まれない白いマスを最初に選んで,後は後手必勝の後手のように動けば良い.
二部グラフなので,完全マッチングが存在するかどうかは最大流などで求められる.

UVa 12529 - Fix the Pond (この記事を編集する[管理者用])

Source

Latin America Regional (2012-11-11)
UVa 12529

問題概要

2N*(2N+1)のグリッドを考える.(Nは300以下)
座標(x,y), (x+y)%2=0 に縦または横に壁がある.(問題文参照)
それを縦・横をいくつか切り替えて,すべてのセル間を移動可能にしたい.
最小でいくつ切り替えればよいか求める問題.

解法

1つ切り替えるごとに連結成分を1つ減らせるので,連結成分の数-1が答え.
DFSなどで塗りつぶしながら連結成分の数を数える.Union Findなどを使っても良い.

UVa 12528 - Environment Protection (この記事を編集する[管理者用])

Source

Latin America Regional (2012-11-11)
UVa 12528

問題概要

xが0以上W以下,yが-D以上0以下の領域を考える.
有理関数y1とy2が与えられる.分子分母の次数はそれぞれ8以下.
xが0以上W以下のとき,それぞれの有理関数は,
 分母は0にならない
 y1(x)はy2(x)より大きい
 y1(x), y2(x)は-Dより大きくて,0より小さい
を満たす.(つまり考えている領域を左から右に突き抜けて,お互い交わらない)
有理関数で囲まれている場所のうち,-dより大きい部分の面積がちょうどAになるようにしたい.
dを求める問題.存在することは保証されている.

解法

2分探索+数値積分.
数値積分は,台形公式とかでも十分.
出力は小数点以下5桁だが,正しく四捨五入するために,もうちょっと精度良く求めなければならない.

UVa 12527 - Different Digits (この記事を編集する[管理者用])

Source

Latin America Regional (2012-11-11)
UVa 12527

問題概要

10進数で全部の異なるような正整数を考える.
N以上M以下のそのような整数がいくつあるかを求める問題.
Mは5000以下.

解法

やるだけ.
高速化の必要ないと思うけど,5000以下の整数が条件を満たすかどうかチェックしておいて,
K以下のそのような整数の数を計算しておくと,各クエリに対してO(1)で求めることができる.

UVa 12526 - Cellphone Typing (この記事を編集する[管理者用])

Source

Latin America Regional (2012-11-11)
UVa 12526

問題概要

アルファベット小文字のみからなる単語の辞書が与えられる.同じ単語はない.
各単語の長さは80以下で,単語の数は100000以下.(単語長の総和は10^6以下)
単語を入力するとき,以下のように行われる.
 一文字アルファベットを打った時(x文字目),今まで入力された文字列をprefixとなるような単語の集合を考えて,x+1文字目が全部等しいならx+1文字目が自動的に入力される.
 自動的に入力された文字に対しても上の処理が行われる.
それぞれの単語を入力するのに必要なキーの数の平均値を求める問題.

解法

まず,入力をソートする.
後は,愚直に,各キーを押した時,それをprefixとする単語の範囲を求めながら計算していく.

UVa 12525 - Boxes and Stones (この記事を編集する[管理者用])

Source

Latin America Regional (2012-11-11)
UVa 12525

問題概要

2人でゲームを行う.
B個の箱と,S個の石を使う.(Bは100以下,Sは200以下)
箱は一直線上に並んでおり,1~Bまでの番号が付けられている.
最初に,プレイヤー2が,S個の石を,好きなように箱に割りふる.
この時,プレイヤー2が勝てるような割り振り方は何通りあるかをmod 1000000007で求める問題.
各ターンは以下のように進む.
 箱Bに石が入っていたらプレイヤー1の勝ち.石が1個もなくなっていたらプレイヤー2の勝ち.
 プレイヤー1は,石を2つの集合に分ける.
 プレイヤー2は,その集合のうち,どちらか片方の石を全部捨てる.他の石は次の箱に移動させる,(箱kに入っていたものは箱k+1に移動させる)

解法

Bに近い箱から順番に見ていく.
箱B-1には,1個までしか石を入れてはいけない.
箱B-2には,箱B-1に石を入れたら,1個までしか入れれないし,入れてなかったら3個までいれれる.
という感じに考えて,
 残り箱の数,残り石の数,この箱には最大で何個石を入れても大丈夫か
を状態としてDPする.
色々試すと,x個まで入れても大丈夫な箱に,y個入れた場合は,次の箱には2(x-y)+1個まで入れても大丈夫なことがわかる.
ナイーブにDPすると4乗オーダーだけど通る.和を適当に求めておくと3乗オーダーにできると思う.

UVa 12524 - Arranging Heaps (この記事を編集する[管理者用])

Source

Latin America Regional (2012-11-11)
UVa 12524

問題概要

一次元世界.石の山がN個 (1000以下) ある.
各場所はX[i]で,そこの石の重さはW[i].(X[i]は単調増加)
石のある場所の数をK個にしたい.各場所はもともと石があった場所と一致させなければならない.
石はX軸の正方向にのみ移動可能で,移動距離×重さがコストとしてかかる.
最小コストを求める問題.

解法

ナイーブなDPだとO(N^2 K)かかってしまうが,適当に枝刈りして高速化したら通った.
想定解法はおそらくMonge性か何かを使ってO(N^2)にするのだと思う.

UVa 12523 - Lazy Professor (この記事を編集する[管理者用])

Source

XXVI Colombian Programming Contest (2012-10-21)
UVa 12523

問題概要

S人(100以下)の生徒と,N個(20以下)の科目がある. それぞれの生徒に対して,各科目のテストの点数が与えられる. 生徒の総合評価は,各科目のテストの加重平均にする. テストiの,加重平均の際の重みは,min[i]以上,max[i]以下の整数でなくてはならず, 重みの和は100でなければいけない. 重みを生徒の総合評価の平均を最大化するようにつけた時,平均値を求める問題.

解法

とりあえず,重みは全部minにしておいて,各科目について生徒の合計点が高い方から,greedyに割り振っていく.

UVa 12522 - The Imperial Problem (この記事を編集する[管理者用])

Source

XXVI Colombian Programming Contest (2012-10-21)
UVa 12522

問題概要

ローマ数字の基本的な規則から,同じ文字が4つ以上使っても良いことにした文字列が与えられる.
その文字列を同じ数の基本的なローマ数字に変換したい.
その際,文字を消したり,文字を追加することができる.
ただし,スペースを詰めることはできないし,最後にスペースが挟まっていたらいけない.
前後に文字が増えていたり,前後のスペースが消えているのは構わない.
消す回数,追加する回数を最小化した時の回数を求める問題.
ローマ数字はたぶん4999以下だと思う.

解法

数字に変換して,置き直したい文字列をとりあえず求める.
後は,2つの文字列をどの位置に対応させるかを全部試してみる.

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

Source

XXVI Colombian Programming Contest (2012-10-21)
UVa 12521

問題概要

N人(5000以下)の人をTチーム(100以下)に以下の条件をみたすように分けたい.
 1) 各チーム,リーダー1人は決まっていて,与えられる.
 2) 各チーム,メンバーの数はちょうどM=N/Tでなくてはいけない.1人は1チームのみに属すことができる.
 3) チームメンバーは,互いに友達でなければいけない.
 4) すべての友達に対して,チームメンバーではない友達は,たかだかfloor(M/2)人でなくてはいけない.
N人の人のTシャツのサイズが与えられる.
各チームはTシャツは,どのサイズが何人分必要かを求める問題.
条件を満たすチーム分けは一意に定まることが保証されている.

解法

チームを組める条件も,チームを組めない条件もやたらきついのに,解が一意に定まることが重要.
適当にやっても求まりそうで,適当に探せば良い.
条件3)より友達でなければ違うチームであることを利用して,
各メンバーに対して,属すことが可能なチームを調べて,一意に定まるならそのチームに入れる,というのを繰り返すだけで通った.
ちゃんと証明してないけど,多分4)から言えそうな気がした.

UVa 12520 - Square Garden (この記事を編集する[管理者用])

Source

XXVI Colombian Programming Contest (2012-10-21)
UVa 12520

問題概要

L*LのグリッドにN個の1*1の正方形を(グリッドに沿って)置く.
置いた正方形の周の長さの和の最大値を求める問題.
Lは10^6以下.

解法

まず,市松模様っぽくおいて行って,後はgreedyに端から周長があんまり減らないところから置いていく.
というのと,まず,全部おいた状態から,端を1マス残しつつ,内部を市松模様に抜いていって,その後,同様に端をgreedyに抜いていく.
という2パターンのgreedyのうち,周長が長い方を返したら通った.(試すとわかるけど片方ではダメ)

UVa 12519 - The Farnsworth Parabox (この記事を編集する[管理者用])

Source

XXVI Colombian Programming Contest (2012-10-21)
UVa 12519

問題概要

ノード数100以下の有向グラフを考える.
枝が与えられるが,(u, v)の枝がコストxと与えられた場合,vからuへはコスト-xで移動できる.
コストの和が0でない閉路が存在するかどうかを判定する問題.

解法

コストが正の閉路が存在するなら,逆にたどればコストが負の閉路も存在するので,負の閉路が存在するかどうかを調べれば良い.
ワーシャルフロイドして対角成分が負になるものがでてくるかどうかを調べた.

UVa 12518 - LCD Extravaganza (この記事を編集する[管理者用])

Source

XXVI Colombian Programming Contest (2012-10-21)
UVa 12518

問題概要

0~9までの数字を3*3のグリッドに書いたときは問題文の図のようアスキーアートに書く.
それを大きなサイズで書くときは,問題文の図のように書く.
N文字 (10000以下) の数字が問題文の図のように左から右へ書かれていて,それぞれの文字と文字サイズが与えられる.
M個 (1000以下) の座標が与えられるので,そこのアスキーアートの文字を求める問題.

解法

まず,各文字について始まるx座標を求めておいて,クエリのx座標から,何文字目なのかを2分探索する.
あとは適当に求める.

UVa 12517 - Digit Sum (この記事を編集する[管理者用])

Source

XXVI Colombian Programming Contest (2012-10-21)
UVa 12517

問題概要

L以上R以下の整数を全部10進数で書く.(Rは10^9以下)
出てくる数字の和を求める問題.

解法

各桁ごとに見れば周期性があるのでそれを用いて桁ごとに数える.

UVa 12516 - Cinema-cola (この記事を編集する[管理者用])

Source

XXVI Colombian Programming Contest (2012-10-21)
UVa 12516

問題概要

R*Cの映画館の座席を考える.(26*99以下)
コーラを置く台は,客席の左右に1つずつあるか,右は右の席の人と共通だし,左は左の席の人と共通なので,すでに左右の人が使ってれば使えない.
すでに入場してる人の座席リストと,それらの人が左右どちらの台を使っているかが与えられる.
今入った人の座席リストが与えられるので,その人達はすべての人が台を使えるように割り当てることが可能かどうかを求める問題.

解法

Greedyに左の人から座らせていって,自分の左が使えるなら左を使い,そうでないときだけ右を使うようにしていく.
誰か使えない人がでてきたらダメ.

UVa 12515 - Movie Police (この記事を編集する[管理者用])

Source

XXVI Colombian Programming Contest (2012-10-21)
UVa 12515

問題概要

M個の0,1のみからなる文字列X[i]が与えられる.(Mは1000以下,文字列の長さはそれぞれ100以下)
Q個 (500以下) の文字列Y[i]が与えられるので,それぞれについて,M個の文字列の中で最も似ているものを求める問題.
似ているというのは,以下で定義される距離が最も小さいもの.
 X[i]の部分文字列でY[i]と同じ長さの中で,ハミング距離の最小値
答えが複数存在するなら,その中で最も最初に登場した文字列を返す.

解法

20個ぐらいをひとまとめに見てあげて,ひとまとめの中のi文字目が1なら2^iを足すという風に1つの整数として扱う.
何個ビットが立っているか,2^20まで計算しておけば,20文字までハミング距離がO(1)で計算できるようになるので,だいたい愚直にやるより20倍ぐらい早くなって通る.

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

Source

XXVI Colombian Programming Contest (2012-10-21)
UVa 12514

問題概要

2次元平面上のL*Lの正方形(ケーキ)を考える.
その内部にC個の点(チョコチップ)がある.(Cは5000以下)
K個の直線が与えられる.(その直線でケーキを切り刻む,Kは50以下)
そのピースに乗ってる点の数 / そのピースの面積 の最大値を揉める問題.
(チョコチップの最も割合の大きいものの割合)

解法

凸多角形カット.
途中でできたピースのうち,内部に点が乗ってないものは無視して良い.
が切る回数が50なので,破片は大して増えないので無視しなくても多分良い.(無視しないほうが良い?)
直線上に点が乗ってるとか,そういうケースを考えなくても通った.

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

Source

The 8th Hunan Collegiate Programming Contest Semilive (2012-10-14)
UVa 12511

問題概要

1000要素以下の整数の配列A, Bが与えられる.
各要素は1以上100000未満.
A, Bに共通する増加列の中で最小のものの長さを求める問題.

解法

数字を圧縮して,各数字に対して,各場所から右にある最近の場所を求めておく.
後は,最後に増加列として使ったAの場所,Bの場所を状態にDPする.
状態数は見た目O(1000^2)だけど,そんなに多くない気がする.

UVa 12510 - Collecting Coins (この記事を編集する[管理者用])

Source

The 8th Hunan Collegiate Programming Contest Semilive (2012-10-14)
UVa 12510

問題概要

r*cのグリッドが与えられる.(10*10以下)
スタート地点,障害物,岩,コインがある.
岩は5個以下,コインは10個以下.
最大で何個のコインを広いことができるかを求める問題.
上下左右に移動でき,岩は,各岩につき,1回だけ押して移動させることができる.
移動させた先は何もないマスで無くてはならないし,グリッドの外に押し出すこともできない.

解法

岩押す方向は4^5通り,岩を押す順番は5!なので全通り探索できる.
コインを全部拾えたら枝刈りすると超速くなった.

UVa 12509 - Tin Cutter II (この記事を編集する[管理者用])

Source

The 8th Hunan Collegiate Programming Contest Semilive (2012-10-14)
UVa 12509

問題概要

無限に大きい紙に縦か横に切込みをn回入れた.(nは100以下,座標は非負整数で10000以下)
穴が開いた部分は取り除く.
紙が切れている部分の長さを求める問題.
穴が開いている部分はその周の長さで,切り込みだけが入っている部分は切り込みの長さ.

解法

座標圧縮して,切り込み部分を移動できないとして,到達できる切り込みの長さをDFSなどで求める.

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

Source

The 8th Hunan Collegiate Programming Contest Semilive (2012-10-14)
UVa 12507

問題概要

ノード数N,枝数Mの無向グラフが与えられる.同じ頂点間に枝が複数あることもある.
Nは16以下,Mは100以下.
ノードには人口が,枝にはコストが付与されている.
枝は全部壊れていて使えないが,コストだけ支払うと復活して使えるようになる.
コストは最大でKまでしか使えない.
ノード1の連結成分の人口の総和の最大値を求める問題.

解法

ノード1の連結成分を状態として,ダイクストラする.

UVa 12506 - Shortest Names (この記事を編集する[管理者用])

Source

The 8th Hunan Collegiate Programming Contest Semilive (2012-10-14)
UVa 12506

問題概要

n個の文字列が与えられる.nは1000以下.文字列の長さの合計は1000000以下.
それぞれの文字列をprefixだけ残して,残りを削除したい.
ただし,そのprefixが他の(元々の文字列)文字列のprefixになっていてはいけない.
最終的な文字列の長さの和の最小値を求める問題.
元々の文字列が,他の文字列のprefixになっていることはない.

解法

ソートして,前後の文字列とかぶらないところを消す.

UVa 12505 - Searching in sqrt(n) (この記事を編集する[管理者用])

Source

The 8th Hunan Collegiate Programming Contest Semilive (2012-10-14)
UVa 12505

問題概要

20文字以下の0,1からなる文字列Xと,1000000以下の正整数nが与えられる.
nを2進数表示で,小数点以下を書いた時,Xが部分文字列として現れる最初の場所を答える問題.
答えが100以下であることは保証されている.

解法

120桁程度,2進数表示で小数点以下を求めれば良い.
2分探索みたいに,多倍長を使って,両辺2^pしながら,2乗してnを超えるかどうかを調べていくと1桁1桁決まっていく.

Appendix

Recent Articles

ブログ内検索

Ads


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