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言語のスパゲッティなコード

続きを読む

February 2012 Cook-off 5問目 - Equation Solver (この記事を編集する[管理者用])

Source

codechef February 2012 Cook-off 5問目
Problem Statement

問題概要

0以上10^6以下の整数a, b, cが与えられた時,以下の等式を満たす正整数の組(x, y)の数を求める問題.
 x*y = a + b*lcm(x,y) + c*gcd(x,y)
無限に存在するならそれを指摘する.

解法

まず,任意の素数pに対して,yがpを素因数にもつ は 数xがpを素因数にもつ数 以上とする.
(後で,素因数にもつ数が等しくないものは入れ替え可能なので,適当にパターン数2^kをかける)
すると,等式は,
 x*y = a + b*y + c*x
となり,yはxで書き下すことができる.
a mod x = 0でなければならないのと,yはx以上であることを考慮すると,xの取りうるパターンは多くなく,全部試せる.
コーナーケースとして,
 a = b = c = 0の時は答え0
 a = c = 0, b != 0の時は答え無限
であることに注意する.

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

続きを読む

February 2012 Cook-off 4問目 - Daily Train (この記事を編集する[管理者用])

Source

codechef February 2012 Cook-off 4問目
Problem Statement

問題概要

列車の席は6つの席ごとにグループになっていて,各車両の空席状況が与えられる.
x人分だけ,同じグループになっている席を買いたい.
パターン数を求める問題.

解法

やるだけ.

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

続きを読む

February 2012 Cook-off 3問目 - Careful Calculation (この記事を編集する[管理者用])

Source

codechef February 2012 Cook-off 3問目
Problem Statement

問題概要

正整数Nが素因数分解した形
 N = p[1]^k[1] * p[2]^k[2] * ... * p[m]^k[m] (p[i]は100000以下,k[i]は10^9以下)
で与えられる.
Nをphi(N)に置き換えるという操作を何回行うとNは1になるかを求める問題.

解法

置き換える操作は,同時に,それぞれp[k]^xを(p[k]-1)*p[k]^(x-1)に置き換えることになる.
まず,100000以下のそれぞれの素数に対して,p[k]-1を素因数分解しておく.
それぞれの素数に対して,p[k]が最初に現れるのは,何回目の操作が終わってからか?というのも計算しつつ大きい素数からその素因数が消えるまでシミュレートする.

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

続きを読む

January 2012 Cook-Off 5問目 - Zeta-Nim Game (この記事を編集する[管理者用])

Source

codechef January 2012 Cook-Off 4問目
Problem Statement

問題概要

2人でゲームをする.行動できなくなったら負け.先手必勝かごて必勝か判定する問題.
石のN個 (50以下) の山がある.
各山の石の数が与えられる.(2012以下)
最初,各山には,同じ正整数Kが設定されている.
各ターン,各プレイヤーは以下の行動をする.
 1つの山を選び,1個以上,その山に設定されている数字以下の石を取り除く.
 その山に設定されている数字は,そのとき取り除いた石の数に設定し直す.

解法

grundy numberを計算する.
(石の数, 設定された数字) がゲームの状態で,遷移する方法が設定された数字の数だけあるので,愚直に計算するとO(2012^3)かかってしまう.
しかし,(a, b)から遷移できる場所は(a, b-1)から遷移できる場所+1箇所しかないので,(a, b-1)の結果を使いまわすことでそれぞれの状態に対するgrundy numberはO(1)で計算できる.

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

続きを読む

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

Source

codechef January 2012 Cook-Off 4問目
Problem Statement

問題概要

要素数N (10000以下) の数列が与えられる.各要素は-10000以上10000以下.
その数列の連続する部分列 (N*(N+1)/2個ある) のうち,和が大きい方からk1番目,k2番目,k3番目の和を求める問題.
k1, k2, k3は1以上2012以下.(k1 ≤ k2 ≤ k3)

解法

a番目の要素から,b番目の要素の部分列を[a, b]と書くことにする.
全てのkに対して,k番目で終わる部分列[i, k]のうち,和が最大のものをpriority_queueに入れておく.
これは,sum[k] = [0, k]の和を全部計算しておき,各kに対し,sum[i]が最小となるk未満のiを見つければ良いので,最初から1回なぞることでO(N)でできる.
後は,k3回だけ,priority_queueから取り出しつつ,[i, k]を取り出したら,k番目で終わる部分列のうち,和が次に大きいものをpriority_queueに突っ込むというのを繰り返す.
これは,sum[k]をソートしておいて,次のやつを愚直に探した.(コード参照)
和が等しくなるものをちゃんともれなく突っ込めるようにソートするときなどにちゃんと工夫する.
合計で,最悪ケースでO(N*k3),平均的(希望的)にはO(N log N + k3 log N)程度.
次に突っ込むのを探すのを工夫すれば最悪ケースでもO(N log N + k3 (log N)^2)程度にはできると思うけど,そこまでやる必要はないと思う.

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

続きを読む

January 2012 Cook-Off 1問目 - Collision in Space (この記事を編集する[管理者用])

Source

codechef January 2012 Cook-Off 1問目
Problem Statement

問題概要

2次元平面上に,地球とN個 (2012以下) の惑星がある.
地球と,それぞれの惑星は上下左右のどちらかの向きに速さ1の等速度運動を行なっている.
それぞれ,最初の位置 (絶対値100以下の整数座標) と,進む向きが与えられる.
地球がどれかの惑星と衝突する最短時間を求める問題.
衝突しないならそれを指摘する.

解法

衝突する時間は0.5の倍数で,衝突するなら,たかだか時間200以内には衝突する.
なので,座標を2倍して時間を0.5ずつ進めながらシミュレーションする.

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

続きを読む

September 2011 Cook-Off 4問目 - Target Practice (この記事を編集する[管理者用])

Source

codechef September 2011 Cook-Off 4問目
Problem Statement

問題概要

N個の的が一直線上に並んでいる. (Nは18以下)
1回の射撃で,的がある場所,もしくは,もう倒れたけど的があった場所を狙うことができる.
その際に,狙った的の左の的,狙った的,狙った的の右の的,に当たる確率が与えられる.(2つ以上離れた場所に当たる確率は0)
すべての的を倒すための必要な射撃数の最小値の期待値を求める問題.

解法

ビットDP.ただし,O(N*2^N)ではTLEで通らない.
2つ以上連続して的が倒れてる場所があると2つの部分問題に別れることを利用するとO(fib[N])になる.fibはフィボナッチ数.
他にも,対称性なども利用して状態数を減らす.
今ある最も右の的の,さらに右を狙うことが可能かどうか,などを新しく状態に加えた.

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

続きを読む

September 2011 Cook-Off 3問目 - Last Digit Sum (この記事を編集する[管理者用])

Source

codechef September 2011 Cook-Off 3問目
Problem Statement

問題概要

S(N)をNを10進数表記したときに出てくる奇数+出てくる偶数*2の和とする.例は問題文を参照.
D(N)はS(N) mod 10とする.
 D(A) + D(A+1) + … + D(B)
を求める問題.
A, Bは400000000以下.

解法

D(1) + D(2) + … + D(n)を高速に求めれられれば良い.
D(k)が0になるものの数,1になるものの数,…,9になるものの数をDPで求める.

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

続きを読む

September 2011 Cook-Off 2問目 - Hotel Bytelandia (この記事を編集する[管理者用])

Source

codechef September 2011 Cook-Off 2問目
Problem Statement

問題概要

N人 (100以下) の客が来るタイミングと帰るタイミングが与えられる.
最もたくさんの客がいるとき,何人いるかを求める問題.
来るのと帰るのが同時に発生するとき,帰る方を先に行われるとする.

解法

イベント (来る・帰る) が起こる時間でソートして,シミュレーションする.

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

続きを読む

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

Source

codechef September 2011 Cook-Off 1問目
Problem Statement

問題概要

正整数N (10^8以下) が与えられる.
1回以上,好きな回数だけ,10進数表記で,最初の文字を最後にもっていく,もしくは最後の文字を最初に持っていく,という操作を行う.
先頭に0が来た場合は,即座にその0は削除される.
得られる最大の整数を求める問題.

解法

以下のパターンを全部試す.
・右にk回シフトする (k=1~8)
・左にk回シフトする (k=1~8)
・右に1回シフトした後,左に1回シフトする
・左に1回シフトした後,右に1回シフトする

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

続きを読む

June 2011 Cook-Off 5問目 - Super-plane (この記事を編集する[管理者用])

Source

codechef June 2011 Cook-Off 5問目
Problem Statement

問題概要

N個 (10000以下) の飛行機のフライトが与えられる.
フライトの情報は,出発地,目的地,出発する時間,到着する時間が与えられる.
(時差とかではなく,不思議な力で)到着する時間が出発する時間より早いこともありうる.
最初にいる場所と時間,目的地とそこにつかなければいけない時間(ちょうどか,それより前に着けば良い),が与えられた時,
時間内に目的地に辿りつけるか,つけるなら乗る飛行機の数を求める問題.
乗る飛行機は,到着した時間かそれ以降の一番早い飛行機に飛び乗ってしまうとする.
また,目的地に時間内に辿りつけたら,そこで止まる.(目的地に着いても時間内でなければまた乗る)

解法

シミュレーションする.
同じ飛行機に2回乗ると後はループするので到着不可能と判定する.
次に乗る飛行機を探すのは,二分探索することで,O(N log N).

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

続きを読む

June 2011 Cook-Off 3問目 - Correctness of Knight Move (この記事を編集する[管理者用])

Source

codechef June 2011 Cook-Off 3問目
Problem Statement

問題概要

チェス盤 (サイズは8*8) の座標はa~hまでと1~8までをくっつけて,a7とかh3のように表す.
次の形式で座標が2つ与えられる.
 座標-座標
その座標間はナイトがちょうど1回で移動できる関係にあるかどうかを求める問題.
座標が不正,もしくは,形式が不正ならそれを指摘する問題.
各行ごとにテストケースを処理する.

解法

やるだけ.改行文字やスペースの処理に注意.

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

続きを読む

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+手間取った時間がもったいない.

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 (チャレンジ形式)
一番比率が大きいのを小さくなるように,小さいのを大きくなるように動かしていった.上位には全然歯が立たなかった.
どうやら,効率の良い置き方を求める多項式時間アルゴリズムがあるらしい.

February 2011 Challenge 6問目 - Rush Hour (この記事を編集する[管理者用])

Source

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

問題概要

箱入り娘パズル.
12*12以下の盤面に,1*2または1*3または2*1または3*1の車が26種類以下配置されている.車にはユニークなアルファベットが割り当てられている.
aの車は横2マス,縦1マスであることが保証されている.
aの車を右端に移動するまでに必要な最小ステップ数を求める問題.
横長の車は横にしか,縦長の車は縦にしか動かせない.1度に動かすマス数は任意だが,車を飛び越えたり,他の車と重なるように動けない.
答えは10以下であることが保証されており,テストケースはランダムに生成される.(意地の悪い人工的なテストケースはない)

解法

枝刈り全探索DFSで通った.(想定解法はIDA*らしい)

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

続きを読む

February 2011 Challenge 5問目 - Milestones (この記事を編集する[管理者用])

Source

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

問題概要

二次元平面上のN個 (10000以下) の点が与えられる.
最も多くの点がのっている直線の上には何個の点がのっているかを求める問題.
N個の点は,二次元平面上に7個の直線があって,そのどれかの直線上にあると仮定して良い.(7個の直線は与えられない)

解法

ある点を原点に平行移動して,各点までのx軸からの角度 mod πを求めて,それが等しいものが同じ直線上にのっているとみなせる.
最初に選ぶ点は全ての点を選ばなければいけないはずだが,少なくても答えはN/7以上であるので,適当にいくつか選ぶと十分に高い確率で正しい答えが見つかる.

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

続きを読む

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

Source

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

問題概要

n個 (10以下) の正整数 x[k] が与えられる.
ある数字Zがx[k]の和で表せれるとは,
 Z = (x[1]+x[1]+…) + (x[2]+x[2]+…) + …
と書けること,つまり,非負整数y[k]が存在して
 Z = Σx[k]*y[k]
となること,である.
この問題でやるべきことは以下の2つ.
 x[k]の和でかけない最大の正整数を求めること.ただし存在しないならそれを指摘する.
 10^7個以下の整数が与えられ,それらの内,何個がx[k]の和で書けるか調べること.
x[k]はそれぞれ10^7以下で,x[k]の中に少なくても1つは10^5以下のものが存在する.

解法

最小のx[k]をXと書くことにする.
aがx[k]の和で表せるなら,a+Xも当然x[k]の和で表すことができる.
よって,a = 0, 1, ..., X-1 に対して,a+m*Xがx[k]の和で表すことのできる最小のmを求めることを考える.
 Z = a+m*X
が表せるなら,
 (Z+x[k]) mod X + floor( (Z+x[k])/X ) * X
も表せるので,ノードaからノード(Z+x[k]) mod Xにコストfloor( (X+z[k])/X ) - mの枝を張る.
こうしてできたグラフ上でダイクストラすることで,全てのaについて,a+m*Xが表すことのできる最小のmが求まる.
後は適当にやるだけだが,タイムリミットの設定が微妙に厳しめなので,できるだけ効率のよいコードを書くと良い.

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

続きを読む

Appendix

Recent Articles

ブログ内検索

Ads


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