http://poj.org/problem?id=3411 問題 N頂点、辺数mの有向グラフが与えられる。各辺は頂点cに行ったことがあるならばコストPi、そうでないならばRiで通れる。頂点1から頂点Nまで行く最小コストを求めよ。 N,m 解法 たどり着いた街が同じ場合はn歩までしか歩…

http://www.spoj.pl/problems/QTREE3/ 問題 頂点数nのツリーが与えられる。以下の2つのクエリを捌け。 頂点iの色を反転させる。(初期状態は白) 頂点1からvまでで黒い頂点で頂点1に最も近いものを答えよ。無い場合は-1。 n クエリの数 解法 ツリーのdfs順序(…

http://www.spoj.pl/problems/QTREE/ 問題 頂点数Nのツリーが与えら、次のようなクエリがq個与えられるので処理しろ。 i番目の辺の重みをtiに変更する。 頂点iと頂点jを結ぶパスの中で最大の重みを答える。 N qはたぶん数万 解法 ツリーを鎖に分解して考える…

なんとなく後ろから見ていく。 J問題 x番目の要素をO(logn)で取り出せる二部探索木があれば楽勝な気が。 I問題 DP臭い でも1周して戻ってくるのをどこで使うかで厄介になってくるなあ そんなもん初めに全部使ってしまえばいいじゃね？ 書いた。合わん。「や…

http://codeforces.com/problemset/problem/117/C 問題 トーナメントグラフが与えられるので長さ3の閉路があるか判定せよ。ある場合はその閉路を一つ出力せよ。 頂点数 解法 強連結成分分解で閉路を見つける。後は閉路の部分の1頂点を取り出し、その閉路から…

http://codeforces.com/problemset/problem/117/D 問題 1からnまでの数列がある。この数列に対して奇数番目の数値を前半に、偶数番目の数値を後半に移動させる操作Fを再帰的に作用させる。この変換によってできた数列をbとする。各クエリに対して を求めよ。…

A問題 エレベータで上下に動く問題。 s=fに注意してやるだけ。 書いた。pretest AC。 B問題 (a*10^8+b)%modが0にならないようにする問題。 mod回ループ回すだけじゃん。 書いた。pretest WA。 aの上限を入れ忘れた。pretest WA。 よく見たらmod-(a*10^8+b)%m…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1070&lang=jp 問題 略 解法 dequeを6個使う。数列の前半部分、後半部分を保持するのに2個。最大値・最小値×前半・後半で4個。 数列は中央で折って、(n+1)/2と(n+1)/2+1番目の数値をdequeのfrontに…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1064&lang=jp 問題 略 解法 書いてある通りに実装するだけ。

3度目の参加 day1 いつもどおりと思わせておいてjava challengeが追加＋所外研修の場所が東大生協になってた。 day2 hosさんとchokudaiさん作成の問題セット。 FでWA出しまくって体力を削られた。 というか0が入っただけでコーナーケース増えすぎ。むしろコ…

原案はいる君が7問、私が3問。testerは私といる君。いもすさんは問題文担当という振り分けにしました。私は原案を6問程度提出したけどセットの都合上3つは今回使わないことになりました。 testerとして全問解いた時の感想は「考えるのは楽だけど実装が重く一…

250 subsequenceの中で辞書順最大を見つける問題。 n=50なんでループ回すだけやないか。 書いた。submit。 500 Convex Sequenceという名前がヒントになってそう。 Greedyにやれば良さそう？ 書いてみた。なんか4番目のテストケースが合わない。 数値を改善す…

問題 桁を全て足すとSになって、掛けるとになる数値の和を求めよ。 0 0 解法 まず、どの数値をどのくらい使ってp2,p3,p5,p7を作るかを全探索する。p5,p7は5,7しかなく、p2,p3は4,6,8,9の数を決めれば一意に定まるので100^4/12弱ある。数値の数を決めたら、あ…

問題 大きさNの数列Sが与えられる。別の大きさNの数列TでS,Tをソートした際にT[i] 解法 S,TをソートしてT[i]再帰を用いればO(n^2logn)計算可能。 とeditorialに書いてあった。 全体からbadなのを引くのと、コンビネーションを使う際にgoodな所に同じ数値がで…

問題 ルセット、きつね、うさぎ用の入り口がある迷路が与えられる。彼女らは自分専用の入口からランダムに一つ選び迷路の中へ入る。中に入った後に3人の移動距離の合計が最小になるように落ち合う場所を決めその場所へ行く。移動距離の合計の期待値を求めよ…

250 ボールが弾性衝突する問題 しかも12個しかボール無いんで向きを全通り調べてsubmit。AC。 この問題ボールが10万個とかでも解けそうな気がするんですが。 450 コインの価値を決めて支払うコインの枚数を最小化する問題。 全探索で行けるんじゃね。なんか4…

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…