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://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2289 問題 略 解法 解説通りにてきとうに多めに候補点を取れば良い。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2287 問題 略 解法 同じ高さの水槽で連結成分を作って有向グラフを作る。あとは各クエリに対して、その時間まで高い水槽からいっきに水を流す。

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=364&page=show_problem&problem=2507 問題 n個の電球がある。集合Siのon/offを切り替えるという操作をm回行い最初のv個だけがついてる状態にしたい。ただし、Si=Sj…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=322&page=show_problem&problem=2266 問題 M*Nの盤面で図のように矩形の障害物がK個ある中で宝物を目的の場所まで動かしたい。宝物はR個の連結した矩形で表される。…

http://codeforces.com/problemset/problem/121/E 問題 n個の数値の列に対して、区間にd足す操作と区間にlucky numberが何個あるか聞くクエリがm個あるので実装しろ。 1 数列の数値が10^4を超えることはない。 解法 配列の平方根分割。

http://codeforces.com/problemset/problem/121/C 問題 n桁のk-th permutationはlucky numberがlucky numberの位置に何個あるか答えよ。 1 解法 k

http://codeforces.com/problemset/problem/121/B 問題 n桁の数値dが与えられる。k回、1-originでdのx桁目が4でかつx+1桁目が7である最小のxの部分を探す。そのような箇所が見つかる度に、xが偶数の場合はx,x+1桁目を4に変え、奇数の場合は7に変える。最終的…

http://codeforces.com/problemset/problem/121/A 問題 xより大きい最小のlucky numberをnext(x)と書くことにする。求めよ。 l 解法 同じ数になる部分をまとめて処理する。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1292 問題 線分と円弧でコマの輪郭を与えるのでその重心を求めよ。またその重心がコマの内側かどうか判定せよ。 線分、円弧の個数 座標の絶対値 解法 解説に書いてあるように円弧を線分で近似すれ…

研究室でだらだらしながら解いた。 A問題 問題分が読みにくだけ。というか入力4通りしか無いんかよ。 書いた。submit。Idleness limit exceeded。 なんぞこれ。調べてみたらinput.txtから読み込まないとダメらしいので書きなおしてsubmit。AC。 B問題 やるだ…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1294 問題 図のように折れ線でn個の点を結んでいく。ただし、途中の線分には2つ以上の点が乗っていなければならない。折れ曲がり回数の最小値とその時の線分の長さの合計の最小値を求めよ。 n 解…

First AC狙いでやっぱり後ろか見ていくことに。 I問題 うまい扇の取り扱い方ってあったっけ？ モンテカルロ法とかεずつ動かして試すくらいしか思いつかんなあ。 H問題 夏合宿に似た問題があった気がする。 今見ているノートの切れ端を2つとどこまで見たかで…

250 括弧を対応させる問題。ここってdiv2じゃないですよね…。 書いた。submit。 500 問題文が異常に読みにくい。 サンプルを見るとn=[nlow,nhigh]の大きさの正方形を動かしてその内部に含まれうる点集合の数は？という問題っぽい。 …。long longで返せとか言…

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

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&page=show_problem&problem=2850 問題 街の各ビルの四隅のどこかに警備員を立たせる。警備員同士は糸電話を使って連絡を取り合う。しかし糸電話は糸がピンと張っている状態でないと機…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&page=show_problem&problem=2532 問題 ユーザがU人、映画がM個ある。各ユーザは各映画に対してという評価を下した。この評価からユーザと映画の傾向を知るため、変数を用意する。 はと…

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=13&page=show_contest&contest=285 90分遅れくらいで参加。 B問題 やるだけ。 なんかmodを取るとか書いてなかったけど実は多倍長ゲー？ 多倍長のライブラリを貼りつてsubmit。AC。 C問…

目標はGoogleから賞金をもらうくらいで。 問題を読むフェーズ A問題 なんか見たことのある問題だなあ。冬合宿のHull Marathonっぽい。しかしk大きすぎだろ。 B問題 (x^x)%Cでフェルマーの小定理使うと見せかけて、Cが素数じゃないし、上に掛かる奴ってCの余…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2307 問題 頂点数n、辺数mの有向グラフが与えられる。各頂点には文字列が書かれている。グラフをwalkしたときに訪れた頂点の順番で文字列を連結した物を考える。そうしてできた文字列で回文になっ…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2257 問題 略 解法 解説通りにAhoCorasickを使った。メモリ制限がきつかったんで状態をmapで保持＋dpし終わった所はclearするようにした。

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

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2270 問題 略 解法 解説に書いてある通り、永続データ構造を使った。二部探索木と言うよりかは頂点の数値を1〜nに圧縮して、セグメントツリーっぽく保持した。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2268 問題 略 解法 解説に書いてある通り、深さは2*lognくらいまでしか見ず、fftで畳み込み計算を行った。

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