PKU
3638 Moogle いくつか点がある。そのうちのC個を選んで、それらの座標は正確に記録する。他は、C個の点のうち各点をはさむような2点の間にあるということだけ記録する。そのとき、平均誤差を最小化したい。その値を求めよ。DP。なぜかabs(double)を実施した…
3658 Artificial Lake 長方形を横にいくつかつなげたような形の水槽がある。水槽の最も低い場所の上空から、水を流していく。各部分が高さ1の水で覆われるまでにかかる時間を求めよ。stackを使って適当にやる。 1894 Alternative Scale of Notation 10進法で…
2374 Fence Obstacle Course フェンスがいくつかX軸に平行にある平面上で、原点から(S, N)までの最短距離のうちX軸方向の移動距離を求めよ。DPだが、ある位置について見るときにフェンスに邪魔されないならそのままスルーしてよくて、フェンスに邪魔されたら…
1201 Intervals いくつかの整数の区間と、それぞれに含まれるべき整数の個数が与えられる。整数の集合で、これらの区間についての制約をすべて満足しかつ、集合の大きさが最小のものの大きさを求めよ。累積和をとると線形計画問題になる。この線形計画問題は…
3251 Big Square グリッド上にJやBや*がある。*である場所１つにJを置いた後、頂点がJのみからなる最大の正方形の面積を求めよ。O(N^4)を定数倍ではやくする
2132 Cow Math 辺に重みがついているグラフが与えられる。起点から終点までの各経路について、通った辺の重みの最大公約数を考える。すべての経路について最大公約数を求めた時、それらの最小公倍数を求めよ。答えをRとして、Rがある整数iで割り切れるかどう…
3270 Cow Sorting それぞれ異なる数値をもつ牛がN頭いる。牛を入れ替えて数値の順に整列させたい。2頭の牛を入れ替える際には、2頭の数値の和だけコストがかかる。任意の2頭を入れ替えられる。コストの和を最小化せよ。巡回列らしい 3280 Cheapest Palindrom…
2430 Lazy Cows 2*Bのグリッド上に牛がN頭いる。K個の長方形を置いて牛を全部カバーしたい。面積の和の最小値を求めよ。牛をソートしておいて、左から順に見ていくが、「上段をカバー」「下段をカバー」「両方の段をそれぞれ幅1でカバー」「両方の段を幅2で…
2180 Bale Figures 立体の情報が与えられるので、その立体の表面積（地面に接している部分は除く）を求めよ。やるだけ 3182 The Grove 連続したXを一周するような経路で最も短いものを求めよ。てきとうに通る点を決めてDijkstraするだけ
3260 The Fewest Coins コインが何種類かあって、ある品物を買うのに、「払ったコインの枚数」と「おつりの枚数」の合計が最小になる方法で買いたい。おつりは最も枚数が少なくなるように返される。払うことができるコインの枚数には限界があるが、おつりで…
3622 Gourmet Grazers 牛と牧草があり、牧草ごとに値段とgreennessが決まっている。各牛は、牧草に要求する最小の値段とgreennessを持っている。牛は個性を犠牲にしたくないので、それぞれ異なる牧草を食べたい。牧草の値段の総和を求めよ。牛と牧草をあわせ…
1914 Cramer's Rule ３元１次連立方程式を解け。解き方は書いてある。やるだけ 3257 Cow Roller Coaster ローラーコースターを作る。部品はそれぞれ置ける位置とコストと楽しさが決まっている。コストをB以下にして、楽しさを最大化せよ。DP 2376 Cleaning S…
2^10記念日
3330 Dr. Podboq or: How We Became Asymmetric 木を、非対称性によってさだまる規則に従って左右入れ替えしたりせよ。まず木をidentifyするのに、文字列を使って考える。(x(xx))みたいな形は一意に木を復号できる。左の子をidentifyしたものと右の子をident…
3014 Cake Pieces and Plates M個のケーキをN枚の皿に分配する方法は何通りあるか。皿を並び替えると一致するものは同じと考える。DP。modをつかうとTLEするが使わないとTLEしない謎問題。 3761 Bubble Sort バブルソートにおいて、「ソートされていなければ…
3613 Cow Relays 重み付き無向グラフが与えられる。グラフ上のある2点をとったとき、その2点を結ぶちょうどN個の辺を経由するような経路のうち、最も重みの総和の小さいものを答えよ。まず入力の形が迷惑なのでidentifyする。 次に、辺が高々100本ということ…
3522 Slim Span グラフがある。全域木のうち、「最大の重み−最小の重み」が最小になるものについて、その値を答えよ。Kruskalを、最初の辺を動かしてやるだけ 3027 Base equality r1 やるだけ
ひさしぶりに精進
2832 How Many Pairs? グラフが与えられる。最長で長さX以下の辺のみを用いて相互に到達できる２頂点の組の数を求めよ。辺を長さでソートして、union-findを用いてその時々の答えの数を求める。最後に、クエリーごとに二分探索。 1935 Journey Bytelandには…
1708 Game 頂点と辺に色がついた有向グラフがある。2つの駒が置いてあり、駒はもう一方の駒がいる頂点と同じ色の辺だけ移動できる。同じ位置に2つの駒があってはいけない。どちらかの駒が頂点Qに着くのに最低何回移動しないといけないか。BFS 1696 Space Ant…
3071 Football フットボールの試合を2Nチームで、トーナメント形式でやる。各チームの組について、それぞれの勝率がわかっている。最も勝率の高いチームの番号を答えよ。DPで、各段階における各チームの確率を求めるだけ 3916 Duplicate Removal 題名のとお…
3984 迷宫问题 BFS 3917 Rock, Paper, Scissors じゃんけんやるだけ 3913 Gnome Sequencing simple comparison 3911 Internet Service Providers 微分 3903 Stock Exchange 最長部分増加列 3869 Headshot やるだけ 3852 String LD 試すだけ 3800 Repair Depo…
1808 Quadratic Residues pを奇素数、aを a!=p (mod p)なる整数とする。平方剰余(a/p)を求めよ。平方剰余の法則に従って計算するだけ 2415 Hike on a Graph 頂点数Nの完全グラフがある。各辺には色がついている。今、3つのピースが頂点に置かれていて、それ…
3105 Expectation [0, N)の範囲の整数を等確率で発生させる乱数器がある。得られた2つの乱数のXORをとって、新たな乱数とするとき、その値の期待値を求めよ。ビットごとに0の確率と1の確率を求めて計算するだけ
2723 Get Luffy Out いくつかの部屋を持ち、直線状にドアでつながっている部屋がある。ドアはM個ある。ドアには2つのロックがあり、どちらかを外せばドアを通れる。ロックを外すにはキーが必要である。キーは2N種類あり、Nペアに分かれている。あるキーを使…
2890 Matrix Multiplication K*Kの正方行列がある。対角成分はすべて1である。その他にM個の1である成分の位置が与えられる。K^2007において、1が何個あるかを求めよ。但し、ここでは「0+0=0,0+1=1,1+0=1,1+1=1」「0*0=0,0*1=0,1*0=0,1*1=1」とする。行列A,B…
2481 Cows 牛が何頭かいる。牛はそれぞれ範囲を持っている。牛Aの範囲が、牛Bの範囲を完全に含み、かつ完全に一致はしないとき、牛Aは牛Bより強い。各牛について、その牛より強い牛の数を求めよ。X軸に範囲の左端、Y軸に範囲の右端をとった散布図を書いてみ…
2843 Cutting Cake 正方形のケーキを切り出す。ケーキを切るときには、決められた座標の長方形を切り出すように切る。すでに切り出されてても構わず切り出す。ケーキを切ったときに、切った部分がいくつかに分かれているかもしれない。何個のつながりに分か…
1827 A Bunch Of Monsters モンスターが何体かいる。1からMまでの数字が書かれた箱もある。モンスターに箱を渡すと、モンスターは攻撃してこない。渡さなければ、攻撃してくる。モンスターごとに、渡せる箱の数値の上限がある。モンスターごとに、攻撃された…
2684 Polygonal Line Search 折れ線がいくつか与えられて、基準折れ線と合同なものを出力せよ。原点起点の折れ線に平行移動したらやるだけ
