解法 変数が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必須． 本当…

卒論発表も終わったのですが，あまりにひどい卒論だったため，卒業資格が与えられるのか非常にビクビクしながら日々を過ごしています． これで卒業できたの？（´・ω・｀）卒論中にこっそりやった問題がいっぱい溜まっているので，覚えてるのをごっそり書きま…

卒論終わったー┗(^o^ )┓三 っていういまさらな日記です．ふぅ！

っていうのが先週ありましたが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行目以…