Algorithm
3184 Finicky Grazers 牛を動かして、牛と牛の間の距離を最大化せよ。このとき、牛と牛の間の距離はある整数DまたはD+1になっていないといけない。DP 1741 Tree 木の上で、距離がK以下になる2点の組み合わせは何通りあるか求めよ。IOI2011「Race」と解法はほ…
1724 ROADS 辺に距離とコストがあるグラフが与えられる。コストの和をK以下の経路の中で、距離が最短のものを求めよ。[頂点][使ったコスト]でDijkstra 1986 Distance Queries 木が与えられる。2頂点間の距離を求めるクエリをK個オフライン処理せよ。Tarjan …
250 なにかがN個あり、1〜Nの番号がついている。「平方数番目のものをすべて取り除き、元の番号順に1から順に番号を付け直す」行為を1個になるまで行う。最後に残ったものは最初何番目だったか。よくわからないので再帰を使って解いたらNが1,000,000,000のと…
1185 炮兵阵地 中国語が読めないが、フィーリングと図から察するに、「フィールド上のPとなっている点に兵士をできるだけ多く置け。但し、兵士の上下左右２マスには他の兵士がいてはいけない」ということになるだろう。DP。M箇所それぞれについて、あと何行…
twitterで出した問題 問題：k の想定解法。
絶望
問題 ある国のコインは、次のような単純な規則に従っている。 それぞれのコインは、正の整数の価値を持つ。 価値1のコインが存在する。 任意のコインの価値は、それより価値の低いコインの価値の整数倍である。 ある金額を払う時、これらのコインを使って何…
2587 Airline Hub 地球上の空港の位置が緯度経度で表されている。ある空港をハブ空港としたい。 その空港から他の空港までの距離の最大値を最小にする空港の緯度経度を求めよ。やるだけ。距離は大圏距離ではなくユークリッド距離であることに注意。 3386 Hal…
1236 Network of Schools http://wikiwiki.jp/pku/?1236%20Network%20of%20Schools の通り強連結成分をみつけて、適当 1958 Strange Towers of Hanoi ハノイの塔っていう有名なパズルがあるが、タワーを4つにしたときの最小手数を求めよ。問題文中に解法が書…
問題 魔法少女回。魔法少女が呪文を唱える。呪文は0,1からなる文字列である。最初のK個の呪文(A[0]..A[K-1])は決まっている。i>=Kのとき、A[i] = A[i-1] + A[i-K-1] + A[i-2K-1] + …（i-nK-1>=0の限り繰り返し）である。呪文Sを、A[N]の[lo, hi]の部分とする…
300 グリッド上に石が何個か乗っかっている。今、方向を選んで、その方向にすべての石を1マス動かすという操作ができる。落っこちた石は棄てる。残りの石をちょうどK個にするために必要な操作の回数の最小値を求めよ。残りの石は長方形状の場所に収まること…
問題 高々21*21の盤面が与えられる。各マスは'.'か、アルファベットが書かれている。アルファベットは21種類のうちどれかである。今、この盤面上で「パス」を考える。パスは、iマス目がi+1マス目に隣接している(1 解法 まず、パスの定義に「互いに異なる」と…
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を持っている。牛は個性を犠牲にしたくないので、それぞれ異なる牧草を食べたい。牧草の値段の総和を求めよ。牛と牧草をあわせ…
大変に下らないミスをしてけっこう時間かかった。 入力はどんなに自明な場合でも最後まで読みましょう わりとシンプルに実装できた気がする。 本選のとき通らなかったのは右いったり左いったりが複数回あるときの可能性を無視したてめという可能性が大。 #in…
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本ということ…
3012 A Number from Yanghui Triangle パスカルの三角形上の数値を、桁揃えの0を入れた上で並べたものをMで割った余りを求めよ。(10K+1)N mod Mを求めるだけ。 3213 PM3 行列A,B,Cがある。Cは、計算機がA*Bを計算した値である。しかし、計算機はたまに計算ミ…
