srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

面白い

codeforces Educational Codeforces Round 16 B. Optimal Point on a Line

問題 問題概要 x座標上のnこの点が与えられる。それらの点の中から、他の点までの距離の合計が最小となるものを見つけろ。 解法 中央値は母集団の各要素から絶対距離の和が最も小さくするという意味で母集団を代表していると見ることができる(Wikipedia)とか…

aoj 0612 - Sandcastle

問題 問題概要 省略 解法 今回の問題は毎回すべての城を調べていたら、TLEになってしまう。そこで、ポイントは、「n回目の波で崩れる城はn - 1回目の波で崩れた城の周囲8方向の城に限られる」ということである。そこで、まずは、城が存在する座標をq1に入れ…

ARC 059 D - アンバランス / Unbalanced

問題 問題概要 省略 解法 アンバランスとなる文字のどんなものでも良いから、一つ出力すればいい。だから、余計な文字を含まない(最短でアンバランスな文字)ものを考えればいい。そのように考えると aa aa(:任意の文字) の2パターンがある。この2パターン以…

yukicoder No.2 素因数ゲーム

問題 問題概要 複数山の石取りゲーム 解法 まず、素因数分解をします。そして、同じ素因数の数を数える。素因数の因数のどおしをxorで計算する。すべての素因数に対してその処理を行い、その結果が0であれば、後攻の人がかつ。この問題は必勝法が存在するの…