http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4872 問題 点がN個あるので辺が交差しないユークリッド最小全域木を求めよ。 1 解法 クラスカル法かプリム法を使って最小全域木を求めるだけ。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4871 問題 高さの違う高層ビルをN個建てる。ただし、i 解法 DP[n][pos]を考える。DP[n][pos]はn番目までのビルを置いたときにhi

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4870 問題 区間がN個あるジェットコースターがある。ある人がこのジェットコースターに乗るのだが、怖さの閾値Lを越えない範囲でなるべく楽しみたい。ある区間で目を開けているとFi楽し…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4869 問題 長さNの数列がある。そのsubstringの総和の最大値を求めよ。 1 解法 左端から見ていって、総和が負になったら0にもどす。これをしていって最大になった物が答え。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4868 問題 leading 0が許された数値がある。その数値を回文にするためには最小いくらの数値を足さなければならないか？ 2 解法 左側半分を固定してそれに合わせるように右側半分を足して…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4867 問題 すべての要素が1か0で構成されたN*M行列がある。その中の正方形で全て1で構成される最大の正方形の辺の長さを求めよ。 1 解法 ヒストグラムの長方形の最大面積を使って求めた…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4866 問題 三角形がある。AB,BC,CAからθずらした直線を考える。θを適切に設定した時にその3っつの直線は一ヶ所で交わる。その場所を求めよ。 解法 頑張って手計算するか三分探索で求める…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4865 問題 N*Mの行列がある。各成分は[0,100]の値になっているか空欄になっている。各列の和と各行の和を与えるので元の行列を復元せよ。ただし、値が一意に定まらない箇所は-1と答えよ…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4864 問題 f(x):=xの2進数表記で1の個数という関数を考える。Ni=f(Ni-1)とするとこの数列は1に収束する。このとき、初めて1になったiをKとする。[LO,HI]の区間でK=Xとなるような数値は何…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4863 問題 Nチームが参加しているコンテストが開催された。各チームに風船をK個配りたいのだが、部屋Aからの距離はDA、Bからの距離はDBとなっている。各部屋には風船がA個、B個ある時、…

PetrとかEgorとかRAVEmanとかと一緒の部屋 300 Hanakoですか… 問題の意味を理解するのに結構時間がかかった 任意の3っつを選んでどんな順番でも同じものになればいいんじゃないの？ 書いた。サンプル通った。サブミット。 500 サイコロを転がす問題 部室のサ…

laycurseさんとかsky58さんとかと一緒の部屋 250 状態がループする期待値の問題か いつも通り、無限等比級数の和の公式を使えばいいんじゃないの 普通に書いた。なんか確率の合計が0.5になってるんでとりあえず2倍したらサンプルと一致 提出。もう15分以上た…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4862 問題 一部が緑、赤に塗られたn*mのボードがある。ボードの各マスには数値が書かれている。そのボードにハイパーナイトを置いて行き、ハイパーナイトが置かれているマスの数値の合計…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4859 問題 256人が戦うトーナメントが複数回ある。ある人が複数のトーナメントでw回勝って、l回負けた。その人が平均どのくらいのラウンドまで進んだかを求めよ。 0 解法 まずl=0でwが8…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4858 問題 [1,k]の数値を使ったn*nの行列A、Bがある。Aの行列の一か所を選び[1,k]の数値に変えるという操作を繰り返してBの行列にする。ただし、数値を変化させたときに対象行列となって…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4857 問題 [1,m]の整数で表現される長さnの数列がある。普通のstackでpush,pop,topを使って与えられた数列を再現することにする。最低何回のpushが必要か？ 1 解法 DPで解く。dp[use][le…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4856 問題 8*8のフィールドに障害物と2*2の4っつの箱がある。初期状態から上下左右の方向に重力をかけて箱を動かしていく。いくつの状態に遷移しえるか？ 解法 やるだけ。初期状態は(基…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4855 問題 N次元で各次元がフィボナッチ数となっている超直方体がある。あるN次元の超直方体を作るためには最低何個の超直方体が必要か？ 1 1 解法 greedyにやるだけ。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4854 問題 A-Zのおもりと天秤ばかりがある。各おもりの重さは文字をアスキードコードで表したときに1が出てくる個数*500+0が出てくる個数*250となる。(ただし、leading 0の部分は除く)。…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4853 問題 n個の数値がある。0以外の数値の個数-0の個数を答えよ。 1 解法 英語を読むだけ。

250 問題を読む。というか図を見ればだいたい何をやりたいか分かるな ちょっと考えると、あるindexを使う方法は2通りしか無いんで2SATに落ちる とりあえずdfsで書いた。サンプルも通った。 よく考えるともっと計算量減らせるなあと思いつつ、最大ケースを試…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4825 問題 s/(n+1)をせよ。 1 1 解法 英語をしっかり読むだけ。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4823 問題 n*nの行列上で二人でゲームをする。各プレイヤーは自分の手番で行列の一番右の列か一番下の行の総和が偶数の場合にその列を消すことができる。列を消せなくなったプレイヤーが…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4822 問題 木がある。葉同士の距離を与えるので葉以外の頂点が何個あるか求めよ。 3 答え 解法 大前提として葉同士の距離が決まっていると木自体が決定できる。なので、実際に木を復元し…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4821 問題 R*Cの各グリッド上にゲームセンターがある。各ゲームセンターは一つのゲームを提供し、そこをホームにしているゲーマーがいる。各ゲーマーは全ての種類のゲームをプレイしたい…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4820 問題 数値がn個ある。長さ1の区間(左端は含み、右端は含まない)で全ての数値をカバーしたいのだが、何個の区間が必要か？ n 解法 greedyにやるだけ。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4819 問題 プログラミングコンテストがN個、問題がM問ある。各コンテストでは使える問題とコンテストで使用する問題の数が決まっている。同じ問題は使わないという条件下で最大何個のコ…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4818 問題 線分がN個ある。([0,L],0)のどこかを中心とした線分と交わらない円を書きたいのだが半径の最大値はいくらになるか？ 1 0 -20000 解法 円の中心を(x,0)とした時の半径の大きさ…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4817 問題 式を与えるのでパースして計算せよ。ただし、0除算、計算途中で90桁を超える、負の数になる場合はErrorと出力せよ。 演算子の個数 解法 パースして、多倍長整数を使って計算す…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4816 問題 幅m、高さnの行列がある。行列の各列を掛けた時に最大となる列はどこか？ 1 1 行列の各数値は32bit-signed integer 解法 負の数を扱える多倍長整数で解いた。負の数を別処理し…