問題概要 長さQ( 解法 いろいろ解き方があるらしい。 自分のやり方は、各区間をpriority queueに突っ込んで、貪欲っぽく選んでいく。ただし計算量はよく分かっていない。 蟻本にはsegtreeやバケット法を使う問題として取り上げられていた。(よく分からない) …

問題概要 ジョブがN(区間に分割してバッチをいくつか作る。バッチは前から順に起動され、起動する際にS( 解法 コストの式は線形なので分割して考えることができる。後は単純なDP。式は大雑把にはdp[i] = min_{i

問題概要 Permutation(N, M)の末尾の0を取り除いたとき最下位の桁の数がいくつになるか求める問題。N 解法 2と5を分けて考えれば単なるmod 10での計算になる。2と5を全て取り除いた上での積を計算しておけばいいのだが、累積積とかを計算しようとするとMLEす…

問題概要 凸とは限らない多角形が与えられる。多角形の外側に多角形からの距離がL以上離れた囲いを作りたい。囲いの長さは最小いくつにできるか求める問題。 解法 凸包を構成して周の長さに2*L*PIを足すだけ。コード略。

問題概要 W*W(W 解法 もっとも愚直にやるとW^4。両端を固定して考えるとW^3で、通すだけならこれで十分。実はW^2で解くことができる。各行について蟻本p280の問題に落とせばよい。

問題概要 ノード数N( 頂点vにマークする。 頂点vから順に親をたどって最初にマークされている頂点を答える(頂点vがマークされてるときはvを答える)。 解法 クエリをまず全て読み込む。各ノードに対して最初にマークされた時刻と質問を受けた時刻を記録してお…

問題概要 ナップザック。

問題概要 長さL( 解法 半分全列挙は間に合わない。二部グラフの片側の最大次数2という制約が強く、ひとつ適当に決めると後はいっぺんに決まる。各連結成分毎に独立に考え、それぞれ最小値をとってやるとよい。簡潔に実装する部分がメイン。

問題概要 0 解法 積がn!になるようなのを考える。n!=Πp_i^e_i (e_i>0)と書けるとき、既約なのでp_iは全部分子にいくか分母にいくかである。なのでn以下にある素数の数を2の肩に乗せればよい。このとき分子と分母は当然異なるので分子

問題概要 ジュースの入ったボトルが2本ある。各人が交互にジュースを残り半分ずつ飲んだ。もっとも多く(単独)ジュースを飲んだ人が勝ちになる。誰が何回飲んだかという情報が与えられるので、勝った可能性のある人を全て求める問題。 解法 nが小さいので全探…

結果。 Easyは誤読で手間取ったものの気にせず書いた。愚直な解法書いてる途中で綺麗な解法に気づいたけど大分書いてしまっていたので気にせず愚直に解いた。Mediumは割と速く解法が見えたけど、ちょっと実装ミスで長引いた。Hardは実装面倒だなー、くらい。…