less<>を使えばよい。 問題 (名, 姓)のpairがたくさんあってset >に格納されている。 (Alice, Acer) (Anna, Cork) (Bella, Bread) (Bella, Field) (Cherry, Card)名が一つ与えられたときに姓が辞書順最小の人を見つけたい。 例えばBellaが2人いるが、Bellaの…

SnackDown 2017 Online Elimination Round Cleaning the Space (SPCLN)https://www.codechef.com/SNCKEL17/problems/SPCLNこの問題は https://www.codechef.com/problems/RINと同値。問題設定や変数名を変えただけ。Editorialもある。 解法 最小カット問題と…

SnackDown 2017 Online Elimination Round Prefix XOR (PREFIXOR)https://www.codechef.com/SNCKEL17/problems/PREFIXOR https://www.codechef.com/viewsolution/14319736 問題 非負整数列A[1]..A[n]が与えられる。次のオンラインクエリに答えよ (l, r)：次…

SnackDown 2017 Online Elimination Round 解法案 Black Nodes in Subgraphs (BLACKCOM)https://www.codechef.com/problems/BLACKCOM/ https://www.codechef.com/viewsolution/14319524 問題 入力でN頂点の木が与えられる。各頂点は白か黒のどちらかの色が塗…

講義に出席した。顔を拝むのが目的。 Tarjan先生 我々が毎日書いているUnion-Findや強連結成分分解（lowlinkのやつ）の証明やらアルゴリズムやら考えたすごい人。 1時間の講義でZip Treeをマスターしよう。 Zip Tree 二分探索木の一つ。詳細な解説は講義に出…

Chef and Digits Problem Code: DGTCNT 各数字が出現した回数を覚えるような桁DPで攻めると駄目。 数字の集合S subset {0,...,9}を決めたとき、F(S, N):=#{Sに含まれる数字の出現回数が条件に一致するような0超過N以下の数}を求める。このときSに含まれない…

TopCoder Marathon Match 93 CrossStitchに参加した。 問題概要 クロスステッチと呼ばれる刺繍を作る。 入力で模様が与えられる。各色の糸ごとに布の表と裏を交互に移動して一筆書する。 表の糸の長さは入力で固定、裏の糸の長さをなるべく短くせよ。 図１枚…

c++0x書き始めた。データ構造書くたびに検索するのも効率悪いので覚える。 実態を持つ データが小さいときはあり。しかし特にサイズが大きい配列を持つと良くない、局所変数にしづらい。 template<int SIZE> struct Array { int d[SIZE]; Array() { // primitive型の場</int>…