http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2861 問題 食べ物がN種類あり、それぞれの価格は2^0円,2^1円,2^2円、…2^(n-1)円となっている。L種類まで食べれる時、価格の合計がM番目になる食べ物の選び方をすると価格はいくらになるか？ 1…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1801 問題 EKG Sequenceという数列がある。この数列の初項は1、2項目は2である。m項目はm-1項目と共通の素因数を持つ数値でまだ数列に出現していない最小の数値である。数値nは何項目に出現す…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3228 問題 文字列Aとクエリがn個与えられる。クエリには2つのタイプがあり、1つ目のタイプのクエリは文字列siが文字列Aの中に何回出ているかを数える物で、2つ目はoverlapを考えない場合の数…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3396 問題 3頂点シュタイナー木のコストを求めよ。 解法 3頂点シュタイナー木なので分岐する箇所を全通り試せば良い。

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3405 問題 整数Nを素因数分解したい。図のようにNを素因数分解する時に2つの数値ずつに分けることを繰り返して計算を行う。分解の仕方は何通りか？ 2 答えは64bit signed integerに収まる。 …

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3560 問題 n人の人がいて掲示板に発言を書きこんでいく。それぞれの人はsignatureと発言を持っている。掲示板に発言を書きこむのは直前の発言をした人以外で出てきた人である。次に書きこむ確…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3552 問題 半径Rの円盤に半径rのドリルでn個の穴を開ける。重心を求めよ。 0 解法 穴がかぶることが無ければ普通に重心の公式で求めれば良い。穴がかぶってしまうので穴の形を考えて厳密に面…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3559 問題 矩形の毒沼がn個ある所でスタートからゴールまで行きたい。毒沼に入らず(境界含む)にゴールまで行くには最低何回曲がらないといけないか答えよ。 0 座標 解法 座標圧縮してダイクス…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3555 問題 h*wの盤面のアイスクライマーで一番上にたどり着くまでの最小の時間を求めたい。ルールは以下のとおり。 左右に進むのにt1かかる 敵がいる場合は無理 進んだ先に足場がない場合も無…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3558 問題 略 解法 答えは[tex:\sum_{a=1}^{n-1}\sum_{x=1}^{{\rm floor}*1ので間に合う。 *1:n-1)/a)}(n-ax)]となる。高速化するためにまず内側のsumを等差数列の和の公式で展開する。外側の…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3557 問題 略。 解法 答えは(n - m + 1)Cmになる。考え方としてはn個の中からm個を選ぶが、連続した物は取らないように(m-1)を引いておく感じ。 分母と分子の両方にpの倍数が入っていることが…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3556 問題 略。 解法 答えは(2^m-1)^nになる。考え方としては1が含まれる集合、1は含まないが2が含まれる集合、…とやっていけば良い。

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3554 問題 部品の工作機械が3台あり、作りたい部品がn個ある。それぞれの部品は各々の工作機械で作るのに必要な時間が分かっている。3台の工作機械を同時に動かし始め、途中で全く止めずに作…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3551 問題 n-1人の普通の人と1人の吸血鬼がいる。一日ごとにある二人が出会ってその二人が吸血鬼と普通の人であった場合、その普通の人は確率pで吸血鬼になる。全員が吸血鬼になるまでの日に…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3549 問題 略 解法 答えが大きくなるのは少ないのでmod10^xで愚直に計算。long longでは収まらない奴が稀にあるっぽいんでそこだけは多倍長で計算した。(m=64,n=781251でのみ答えが10になる。…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3548 問題 h*wの黒と白で塗られた盤面がある。これに対してa>=bという条件の下で図のようにn*mの白い正方形を書いていく。Helenはある長方形をt時間である色に塗ることができる。しかし目的の…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3541 問題 ボタンがn個直線上に並んでいる。各ボタンは押してからTi秒後に元に戻ってしまう。全てのボタンを押した状態にするにはどの順番で押せばよい？ 1 1 解法 左右の端を持ったDP。dp[lr…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3545 問題 n個の文字列siが良いDNAとして重みwiを持っている。長さlの遺伝子の良さはその遺伝子がsubstringとして含んでいる文字列のwiの合計となる。遺伝子の良さの最大値を求めよ。 1 1 wi …

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3544 問題 n*mのマスに順番にq個の図形が書かれていった。既に色が塗られいた場所に後から色塗ると上書きされる。最後の状態で各色のセルは何マスあるか答えよ。 1 1 1 解法 長さが短い方を縦…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3540 問題 W*Hの場所にn個長方形の古いマシンがある。そこに1*mの新しいマシンを置きたいのだが置ける場所は何通りある？ 1 0 1 古いマシンは重なっていない。 解法 平面走査。ならし計算量で…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3543 問題 長さn+1の順列で各公差がqi(+,-もしくはどちらでも良いのどれか)である場合、そのような順列は何通り存在するか？ 1 解法 dpで考える。dp[i][j]は長さi+1の順列で最後が数値jで終わ…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3547 問題 会社にはn人いて、i番目の人には給料がi^4だけ支払われている。nと互いに素な番号の人をクビにしたら給料はいくら削減できる？ 1 解法 n^4の総和はググって調べる(On Siteでも頑張…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3542 問題 バイナリエディタのビューアを作れ。 文字サイズ 解法 やるだけ。addrも16進数にすることに注意。

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3527 問題 頂点数Nで全頂点で入次数が1のグラフが与えられる。ある頂点に神社を建てるとFの信仰心が得られる。しかし、親ノードにも神社を建てる場合はF+Gの信仰心になる(負になる場合もある)…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3521 問題 アイスバリアを張って弾を止める。まず座標(sx,sy)に半径rのアイスが置かれる。次にアイスと接触している弾はその点を中心としてl×lの正方形のアイスになる。アイスになった弾に接…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3524 問題 頂点数n、辺数mのDAGが与えられる。DAGの頂点iでは重さtwi、価値tviの商品が無限個買える。ナップサックが重みwまで耐えられる時に商品の価値の合計が最大になるようにする。この時…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3525 問題 三次元空間に重み付き点が1000個あるんである大きさの直方体を動かして、その中に入る点の重みの合計を最小にしろ。 -1000 0 解法 x,yはソート+尺取メソッドで消す。残るzはSegment…

http://acm.zju.edu.cn/onlinejudge/showContestProblems.do?contestId=328 東方回。なんとなく出てみた。 Aya 3クリークができないように辺を最大何本引けるか？ 4,5,6頂点くらいで試してみたけど、よう分からん 2部グラフで考えればいいんじゃね？ 証明し…