2012-01-01から1ヶ月間の記事一覧
問題概要 長さN( 解法 いくつできるかを二分探索で求め、その答えを利用して復元すれば良い。heapを使ってgreedyにやってもできるらしい(計算量は多分一緒?かしこいheap使えば計算量落ちるかも)
問題概要 半径Rの円がある。この中に、半径rの円をn個詰めて、それぞれが交わらず、かつ半径Rの円周に接するように配置することができるか求める問題。 解法 キチキチにn個詰められるような半径がいくつになるかを一次方程式で求めることができる。後はrがそ…
結果。 Tシャツが懸かった回。解ける問題を順当に解いただけといういつもの結果。 開始直後Aを読むと一目幾何の手計算っぽい問題。とりあえず放置してBを見ると本文全部読むまでもなく実装系な問題。こういう問題に取り組んで時間を消費してしまうととても悲…
問題概要 ある2つが繋がったという情報や、ある2つは繋がっているかどうかというクエリが来るので処理する。 解法 入力の制限がかかれてなかったり、入力の終了読み取りが面倒だがunion findするだけ。
問題概要 N( 解法 union findする。蟻本p.85。
問題概要 x=0からx=L( 解法 蟻本p.73に載ってる問題。今までに通過した補給所のうちもっとも燃料の多いところを利用することにすれば良い。 ソース略。
問題概要 UVa-10037, ZOJ-1877, POJ-2573 : Bridgeと同じで、出力形式が若干異なる。
問題概要 人名のペアがF( 解法 union findでマージするときに数も足し合わせる。stringの処理が重くならないように注意。
問題概要 長さL( 解法 [from, to)型のメモ化再帰。ひとつの状態から、どこを切るかを全部試す。
問題概要 N( 解法 即数列検索。O(sqrt(N))で求められるらしい。テストケースが1000個と多くて微妙に不安になるけど何とか通った。
問題概要 N( 解法 トポロジカルソートするだけ。辞書順最小とかはあらかじめ降順にソートしておけば良い。
問題概要 3とかかれたカードがN枚、2とかかれたカードがM枚ある。これらからK枚選んで一列に並べて数を作る。その際に、出来上がった数は2進数表記で末尾に0がK以上ないといけない。そのような数のうち、最小のものを求める問題。ない場合はその旨出力する。…
問題概要 3*3のmod10なライツアウトを解く。 解法 mod 2なライツアウトと同様に先頭の桁に関して全探索する。
問題概要 3*3のmod 10なライツアウトがある。解答のコマンド列が与えられるので初期盤面を復元する問題。 解法 5近傍に1ずつ配る。
問題概要 1~3999の整数が与えられる。ローマ数字で書くのにマッチ棒が何本必要か求める問題。 解法 各桁毎に置き換えるだけ。もうすこしDRY原則を意識して書くべきだった。
結果。 簡単な三問だけ解いて終わってしまったのが残念。 A,B,Cはひたすらやるだけの問題。D,E,Fのどれを解くかという話になって、DがDPで行けるかと思ったけど多倍長使えば楽に書けそうだったのでそれに取り組んだ。問題文を誤読していて(KぴったりをK以下…