概要 有向グラフが与えられて，エッジにはコストがついている． N頂点あったら，1番の頂点からN人の人をすべての頂点に行き渡るように移動させて， そこから１番に返ってくるような，すべての人についてのコストの和の最小値を答えるという問題． 頂点も辺も…

今更だけどサブミッション用のスクリプトを公開してみる…ｗ submit 1000.cc みたいな感じでコマンドを実行すると，1000にサブミットできるだけという低機能(^p^)↓のrubyスクリプトをpku用のディレクトリに置く http://halwhite.s352.xrea.com/pku.txt ファイ…

概要 100個の町とそれをつなぐ双方向のエッジがいくつかある． すべての町に，発掘された金の量と，金をしまっておける量が設定されている． すべての金をしまえるように，金を移動したい． すべての金の移動パスの中で，一番離れているエッジの長さ，を最小…

なんか簡単な問題 main(m,h){for(gets(&m); ~scanf("%d:%d",&h,&m); m?puts("0"):printf("%d\n",h<13?h+12:h-12));} 89Bgets(&m)とかテキトウなことやってみたら動いたｗでもテキトウにやってたんじゃだめだよね… 研究室にあったショートコーディングの本読…

なんかけいたんがゴルフしてたから真似してみる！ 初ゴルフです． main(i,c){ for(scanf("%d",&c); ~scanf("%d",&c); printf("%d %d QUARTER(S), %d DIME(S), %d NICKEL(S), %d PENNY(S)\n", i++,c/25,c%25/10,c%25%10/5,c%5));} 146B（改行除く） テストケ…

概要 x^y == k (mod Z) となるyを求める． 解法 素因数分解と同じで離散対数問題を解くのは大変なんだけど，Hashtableを使うとO(√Z)で計算できるというのを初めて知った． Baby-step Giant-stepアルゴリズムと言うらしい． http://en.wikipedia.org/wiki/Bab…

概要 ホーン節とは，(n1&n2&... => p) という形をした論理式．(niもpも否定がつかない) ホーン節の論理積が与えられ，それを充足するような真理値割り当てを求める． 式の長さは，20000文字以内． 解法 構文解析をして，ホーン節の集合を求める． 右辺に変数…

概要 5x5のフィールドが与えられて，7つの連続するマスを選ぶ． マスにはHかJが書いてあって，7こ選んだとき，Jの方が多くなる選び方は何とおりあるか． 解法 まず，ダメだった解法は，25C7 = 480700 なので，全部生成して，それが条件を満たしているか，Uni…

概要 1 乳搾りをすると病原菌が混ざり合うが，Kまでは混ざってもOK． 最大何匹までokか？ 解法 DこのうちK個，混ざってもいい病原体を選んで，全部チェック． bit combinationの列挙が役に立った． // bit combination // comb(N, K) int N, K; for(int comb…

解法 変数がN a op b = c 1 と言う式が1000000個与えられる． これらの式を充足出来るか答える． 解法 2-satになる．

概要 n この数列は，1〜nの順列になっている． この数列を，任意の場所との交換だけでソートする． 最低何回交換操作をしないといけないか． 解法 順列になっているので，ある数字がどこにあるか，と言うのがすぐに分かる． そのため，1番目から順番に正しい…

概要 K個の搾乳機とC匹の牛がいる． 搾乳機はそれぞれ，1日につきM匹まで搾乳できる． それぞれの搾乳機と牛のあいだに距離が設定されている． すべての牛を搾乳するために，動かなければいけない牛の距離の，最小値を求める． 解法 ウォーシャルフロイド＋2…

概要 2進数の符号が与えられる． それらの符号が瞬時符号か答える． 解法 trieとかをつくって，ある符号が他の符号の途中の場所で終わらないか確かめる．

概要 n 海岸線から一番遠い点は，海岸線からどれだけ離れているかもとめる． 解法 コンベックスカットという，凸多角形を直線で2つに分ける操作がO(n)でできる． ある直線から距離がd離れた直線は簡単に求められるから，距離に関して2分探索すればいい．

概要 多項式2つが与えられるので，それらが恒等式か判定する． 式は，足し算引き算掛け算，変数のべき乗で，べき乗は10乗まで． 解法 いくつか値の割り当てを試して，いつでも等しい値かチェックするといいが， 10乗とか出てくるので，BigInteger必須． 本当…

概要 N個の宝石があって，それぞれに価値v[i],重さw[i]が決められている． この中からK個の宝石を選んで，sum(v[j]) / sum(w[j]) の値を最大化したい． その時の，K個の宝石のidを答える． 1 sum(v), sum(w) 解法 二分探索キター！ あるxについて，sum(v[j])…

概要 お化けが３体いて，１ターンに各お化けは高々１マス動く． また，お化けは３体同時に動く． お化け同士が同じマスになったり，入れ違いになってはいけない． 必ずゴールに動かす方法があるので，最短手数を答える． マップは16x16，お化けは３体まで． …

概要 クエリーが来て，動的に２部グラフを構築，ある時点での２つgangの色の関係を答えるという操作を繰り返す問題. 点が100000,クエリーが10000くる． 解法 解法は，UnionFindに，各点の色をつけて，経路圧縮とunion時に，色の計算を行う． でも，いまいち…

概要 ラムダ式を簡約して，最簡な式に変形する問題． 解法 構文解析が書き終わって，それからどうしよう…と思って，環境とか持たせてevalとかしてみたけどうまくいかず，問題をよく見ると，簡約の仕方のルールがちゃんと書いてあるというｗ 僕の解法は，Expr…

概要 配列の宣言、参照、自然数の代入のみができるプログラムが与えられる。 実行したときに、配列の範囲外アクセスまたは未定義値の参照が最初に起こる行番号を調べる。 プログラムは1000行まで、添字は2^31-1まで。 解法 構文解析。 添字の範囲は大きいけ…

概要 全域木のslimnessを、その木の中の一番重い辺と一番軽い辺の差と定義する。 単純無向グラフが与えられるので、slimnessが一番小さい全域木を求める。 点の数はN=100個まで、辺はM=N(N-1)/2まで。 解法 辺を重さでソートして、あとはO(M^2)くらい全域木…

概要 方程式が与えられ、ニュートン法で解を求めたい。 与えられた初期値から、何回ニュートン法の反復を行うと解が得られるか求める。 1000回繰り返しても解が得られないとは、ダメって出す。 解法 構文解析してやるだけなのだけれど、なぜかWAを出しまくっ…

概要 2次元平面上に点が1000個ある。 このなかに、正方形がいくつあるか数える。 座標は整数、2点間の距離は20000以下。 解法 点をpairとかに入れて、ソートする。 つぎに、点を2つ選ぶと残りの2点の座標を決められるから、それが与えられた点の中にあるか探…

概要 V種類のアイテムの金額と、予算Dが与えられる。 D以内で購入できるアイテムの組み合わせが何通りあるか。 ただし、ある組み合わせにおいて、他にも予算内で買えるアイテムがあった場合、それを買わないといけない。 1 解法 DP…が苦手なのでメモ化再帰… …

概要 1 0 テストケースは1000個。 解法 (0,0)から見えるかどうかは、(x,y)について、gcd(x,y)==1かどうかで調べられる。 N=1からN=1000まで1ずつフィールドを広げていって、見える点の数を前もって計算する。 O(N^2logN)くらい？ たぶんもっとうまいやり方が…

概要 N匹牛がいて、それぞれ身長が与えられている。 ある牛について、自分よりインデックスが大きな範囲で、自分の背より高い牛が現れるまでの範囲の牛が見える。 すべての牛について、各牛から見える牛の数の合計を計算するという問題。 1 解法 Range Maxim…

やっととけた〜 今年の占い問題らしい。 概要 C匹の牛がいて、それぞれscoreとaidという値を持っている。 N(奇数)匹の牛を選んで、その中のscoreのmedianを最大化したい。 ただし、N匹の牛のaidの合計はF以下でないといけない。 1 解法 median候補を大きい方…

概要 １〜Bまでのボタンがある。 1つ以上のボタンを同時に押すことを組み合わせという。 ここで、組み合わせの並びを考える。 組み合わせの並びは、1回以上同じボタンを押してはいけない、押さないボタンが有ってもいい、1つ以上の組み合わせを使っている、…

概要 同じ枚数Cのカードの山が与えられて、片方のカードの山ともう片方のカードの山をカードが交互になるようにシャッフルする操作を繰り返し、目標のカードの並びを得るためのシャッフル回数を答える問題。なんかいシャッフルしてもダメなら、-1を出力する…

概要 池の数を数える問題。 解法 flood fill http://acm.pku.edu.cn/JudgeOnline/problem?id=2386