はじめに 7/12 に行われた国内予選に SleepingDragon で出ました。 チームメイトはいつもの kazuma, nakano です。 コンテスト内容 問題を読む前に bashrc に alias の設定だけする A を読むとはいなので書く 入力形式を見間違えていてサンプルが合わなかっ…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1387 解法 各分割区間と一致する場所が、「より左にある」という制約が重要で、これにちゃんと気がつけば解ける。 これによって 文字列のある位置の文字と別の位置の文字が、与えられた条…

はじめに 友人と会話してて得られた知見で、共有したいと思います。 ゼッケンドルフの定理 ゼッケンドルフの定理は 任意の正の整数が、連続するフィボナッチ数を含まないような形で、相異なる1つ以上のフィボナッチ数の和として一意に表現できる というもの…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1191&lang=jp 解法 こういう問題に対する典型的な発想として、一文字ずつ構成していく、というものがある。 つまり、A の先頭位置と B の先頭位置を決めうった後、一文字ずつ作っていって…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1158 解法 \(_{36}C_{18}\) は流石に間に合わない。 しかし、2つの領域を合同かつ連結になるように選んでいけば、探索空間はそんなに大きくないように思える（実際大きくない）。 なので、…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2682 解法 答えは 9 以下なので全探索で間に合う（えぇ…）。 前処理で、ある点に配置したときにどこが見えるようになるかを bit で管理すると判定が O(1) になる。 視線の線分が多角形内部…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2724 解法 結論を言えば、最小重み二部マッチングに帰着できる。線分の交点と端点が頂点になった有向グラフを考えると、考えるべき問題は「いくつか辺を追加することで、最小重みのオイラ…