https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=346&page=show_problem&problem=2504 問題 略 解法 忘れた

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=350&page=show_problem&problem=2531 問題 携帯型原子力発電機で街の各家庭に電力を供給したい。発電機からの距離がl以下の時にその家には電力が供給される。1台の…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=322&page=show_problem&problem=2267 問題 右方向にr個、左方向にq個止まる候補の箇所がある。各箇所はxiの場所にあり時間t1ｎそこに行くとmax(0, pi-t)の利益を1度…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=293&page=show_problem&problem=2013 問題 Nに含まれる桁の数値を全て含む数値をFriend Numbersと呼ぶ。範囲[A,B]の中でK番目のFriend Numbersを求めよ。 1 解法 dp…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2301 問題 シンプルなゲームをするので自分が何点差で勝つか求めよ。 1 石の数の合計 解法 αβ法でやるだけ。 注意点とか細かいルールは以下のとお…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2298 問題 m*nのグリッドがある。各マスで上下左右に移動する確率を与えるので、(1,1)から(m,n)まで行くのに掛かる時間の期待値を求めよ。 2 答え…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2306 問題 n次多項式を与えるのでそれが重解を持つかどうか判定せよ。 0 30 解法 重解を持つ条件はf(x)=0かつf'(x)=0となるxが存在することである…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2302 問題 長さnのハッシュにn個の値を線形探索で値を入れていく。もしもN-1まで開いてない場合は失敗となる。m個分はどのタイミングでどの箇所に…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2304 問題 円環の中に長さNの数列がある。この数列の各数値に対して自分自身と左側のL倍と右側のR倍を足した数値を新しい数値にするという操作をS…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=528&page=show_problem&problem=3917 問題 人がn人いて、それぞれ(xi,yi)にいる。ある人が、ある人の銃声を別の人の銃声よりも早く聴いたという情報がm個与えられる…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=528&page=show_problem&problem=3916 問題 w*hのグリッドにプールを作りたい。#のセルを.に変えるコストはd、.のセルを#に変えるコストはf、最終的な状況で#と.のセ…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=528&page=show_problem&problem=3914 問題 図のようなブロックを使って指定されたように敷き詰めることができるか？ 1 解法 まず、白のブロック数が黒のブロック数…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=518&page=show_problem&problem=3820 問題 0,1で構成されるm*n行列がある。隣り合う要素同士をswapすることによって各行、各列にある1の個数を同じにしたい。swapの…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=399&page=show_problem&problem=2962 問題 m種類の文字から構成されるn文字の文字列が与えられる。また2つの文字を合成した時にどの文字が何分でできるかの表も与え…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=399&page=show_problem&problem=2964 問題 3面ダイスが3個ある。それぞれのダイスの1,2,3が出る確率も分かっている。この3つのダイスを降る確率を適当に決め、別の3…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=399&page=show_problem&problem=2963 問題 頂点数nの木がある。各辺にはドアがあり、鍵の必要な物がある。鍵が必要なドアはC個あり、各ドアには色がついていて同じ…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=399&page=show_problem&problem=2961 問題 n頂点のグラフが与えられる。全域木の中で使ってる辺のコストの最大値-最小値の最小値を求めよ。 2 解法 辺を重み順にソ…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=399&page=show_problem&problem=2960 問題 n頂点のグラフが与えられる。そこの頂点のどこかに猿がいるので撃ち殺したい。猿を殺すために銃を撃つと、猿がそこに居な…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=399&page=show_problem&problem=2958 問題 オンラインジャッジのスコアボードの、各行と各列に何個ACがあるかの情報が与えられる。スコアボードを修復せよ。複数の…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=399&page=show_problem&problem=2957 問題 n*n行列A,Bが与えられる。A*A=Bとなるかどうか判定せよ。 1 Aの各成分は10以下。 解法 乱択アルゴリズムで解く。詳しくは…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=399&page=show_problem&problem=2955 問題 横方向と縦方向に芝をかる。それぞれの方向で、全ての場所の芝が刈られるか答えよ。 解法 英文読んでやるだけ。

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=399&page=show_problem&problem=2959 問題 AGTCからなるn文字の文字列Sがある。各文字は一文字だけ前後(AをGとかCに)に変更ができるが、隣接した物を同時に変更する…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=42&page=show_problem&problem=2121 実装：45分 デバッグ：1時間45分 問題 シャフトがn個あり、このシャフト間をベルトで結んでsからeのシャフトを結びたい。ただし…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=42&page=show_problem&problem=2122 実装：50分 デバッグ：30分 問題 めんどくさいので略。YUHAのACM-ICPC 2007-2009総集編を参照。 解法 英語を読んで、シュミレー…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=43&page=show_problem&problem=2454 問題 ウィンドウがn+1個ある。一つ外側のウィンドウがリサイズされると、内側にあるウィンドウは幅やウィンドウとの距離を一部…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=43&page=show_problem&problem=2452 問題 2*M枚のカードをルールに従って山を作るように互いに置いていく。どちらが勝ち、スコアの差分がどうなるか求めよ。 5 解法…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=44&page=show_problem&problem=2786 問題 APLのインタプリタを作れ。式は全て右から評価すること。 (例えば - / 1 2 3 は (1 - (2 - 3))=2という意味) invalidな入…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=44&page=show_problem&problem=2790 問題 H*Wの盤面があって、そこに左下から右下へ運河を作る。運河の長さを最大化せよ。 答えは一意に定まる。 2 2 解法 一行分ど…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=511&page=show_problem&problem=3723 問題 さめがめの最大得点を求めよ。 幅、高さ 色の数 解法 全探索＋枝刈りで解く。枝刈りは残ってる色の個数をそれぞれ二乗し…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=511&page=show_problem&problem=3718 問題 頂点数n、枝数mのグラフGが与えられる。グラフの辺は最初壊れていて、それを直すのにコストwiかかる。1番目の頂点からk番…