っていうのが先週ありましたがAしか解けませんでした＼(＾o＾)／ やっぱり基本がちゃんとできてないなぁと思いました． 考察力もないし… 得意分野をつくる，っていうのが今年の目標です．最近は卒論が進まなすぎて日記＆PKUを自重しています． 卒論終わった…

概要 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…

遅くなってしまったけどとぷこだ． easyをものすごい遅く通したけれど，レートは下がらず． 一目見て簡単そうだと思ってもサンプルしっかりみて落とし所を探さないといけないなあと思った． mediumはなんか分かりそうでわからなかったなー…DPできるようにな…

概要 配列の宣言、参照、自然数の代入のみができるプログラムが与えられる。 実行したときに、配列の範囲外アクセスまたは未定義値の参照が最初に起こる行番号を調べる。 プログラムは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点の座標を決められるから、それが与えられた点の中にあるか探…

ふう！ 今日は自分的に不完全燃焼なSRMでした。全部無理やり解いちゃった感じで… でもDIV1に戻れたので、またこっちに戻ってこないように頑張ろう(^p^) Easy Desertification 概要 10*10のマップがあって、各セルは砂漠か森。 砂漠はずっと砂漠のままで、森…

やってみた。 (k+2)%4で逆向きに進めるところを工夫したつもり。 幅優先ができれば僕でも就職できるのでしょうか。 あと、お腹の幅も優先されてきて困っています。 #include<cstdio> #include<queue> using namespace std; #define rep(i,s,e) for(int i=(s),___e=(e);i</queue></cstdio>

概要 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

概要 N個の頂点とM個の辺がある無向グラフが与えられて、頂点１からすべての点に行けて、その中で最長の辺の長さが最小になるような辺の選び方を決めるという問題 解法 最小全域木を作って一番長い辺を答えればいい O(MlogM)くらい http://acm.pku.edu.cn/Ju…

概要 単語のリストが与えられて、それぞれの単語について、他の単語と区別できるような最短のプレフィックスを答えるという問題。 単語は1000個まで、各単語の長さは20まで。 何故かサンプルと合わずに放置していた問題。 友人に解き方を教えてもらって勘違…

概要 ライツアウトみたいな問題。 M行N列のフィールドで、あるタイルをflipするとその1枚と周りの4枚も同時にひっくり返る。 全部白にするためのやり方で、辞書式順序が最小のものを求める。 (1≤M,N≤15) 解法 1行目のフリップする場所を決定すると、2行目以…

概要 F種類の食べ物、D種類の飲み物、N種類の牛があって、食べ物飲み物は全種類1つづつしかなく、牛は食物と飲物の好みがある。 最大限多くの牛が好みの食物と飲物両方を手に入れられるようにしたとき、どれだけの牛を満足させられるかという問題。 解法 SRC…

概要 長さL(1≤L≤300)の文字列sと、辞書として25文字以下の単語をW(1≤W≤600)個与えられる。 sは辞書内の単語をいくつか並べたものだが、ノイズが混入している。 元の文字列をsからいくつか文字を取り除くことで復元したい。 最小限いくつ取り除けばよいか。 …

概要 トランプのカードのソートされた列がいくつか与えられて、任意の2つの列に共通してある末尾の並びを、どちらか片方にのこして削除していく。 最後にいくつのカードが残るか。 カードは全部で100,000枚まで。 解法 末尾を根にしてTrieを作って節点の数を…

PKUとかtopcoderとか解いたらなんか書きます。 続くかな。