2432 Around the world 地球上の何点かにFJの友人がいる。それぞれの友人はある緯度の位置に住んでいる。いくつかの友人のペアの間に、その間を結ぶ航空便が存在する。航空便は、移動する緯度が少ない方の向きで移動する。友人1の場所から始めて、地球一周し…
2778 DNA Sequence DNAはA, T, G, Cからなる列である。長さnのDNAで、病気因子となるDNAの部分を含まないようなものの数 mod 100000を求めよ。Aho-Corasickを用いて遷移行列を作り、バイナリ法で累乗する。
不快すぎる 250 「王の名前 ローマ数字」がたくさん与えられるので、王の名前順にソートし、同じときはローマ数字順でソートするというソートをせよ。ローマ数字を計算するのが面倒。 600 わけのわからないアルゴリズムを実行したときにある処理のステップ数…
3180 The Cow Prom 牛がたくさんいて、いくつかのペアの間にひもがある。牛のいくつのグループが適切なダンスをできるか？適切なダンスは、そのグループのすべての牛がロープを引っ張って同じ方向に回れるということである。英語を読み、強連結成分分解する…
1987 Distance Statistics Treeと同じ 1563 The Snail 木登りをしている人がいる。昼間は登る。夜は少し下がる。登れる高さは日に日に短くなっていく。木のてっぺんより高いところに到達するか、地面より低いところについてしまうまでにかかる日数を求めよ。…
4018 High security N個のパスワードが与えられる。パスワードは5文字で、各文字はA-Za-z0-9のどれかである。0例えば1,3,5文字目が同じであるような組の数は、1,3,5文字目だけを取り出してソートすることでO(N log N)で求められる。同様にして、すべての位置…
3159 Candies キャンディーを幼稚園の子供たちで分配する。いくつかの子供の間に、「BはAよりc個以上多くのキャンディーをもらわなかった」という関係がある。子供Nは子供1より最大何個のキャンディーを多くもらえたか。（キャンディーは無限にあるものとす…
2949 Word Rings word ringを、「いくつかの文字列で、i番目の文字列の終わりの2文字がi+1番目の文字列の最初の2文字に一致する（また、最後の文字列の終わりの2文字が最初の文字列の最初の2文字に一致する）ような文字列の列」と定義する。文字列の集まりが…
2964 Tourist たぶん某国のぱないアルゴリズマーは関係ない。マップ上で、左上の点から右下の点まで行ってまた帰ってくる。いくつかのマスは通れない。いくつかのマスには面白いものがある。上下左右に動けるが、経路は最短でないといけない。面白いマスをで…
3327 Cut the Cake ケーキの切断手順が与えられるからシミュレートせよ。やるだけ。vector > を使うと簡単。 1408 Fishnet 網の線が与えられるので、最も大きい網の目の大きさを求めよ。やるだけ。面倒なので魔法少女ライブラリで適当にほげほげした。 1466 …
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で…
