Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

ad-hoc

Codechef March Cook-Off 2014 - ABC-Strings

問題文 : ABC-Strings概要 : 文字列 $S$ の部分文字列 $t$ であって, $t$ の中の A の個数, B の個数, C の個数が等しい物の個数を数えよ.制約 : $1 \leqq |S| \leqq 10^6$ $S$ は A, B, C だけからなる文字列である.

KOJ 0021 - MAX Sequence

問題 : MAX Sequence

Codeforces 353D - Queue

問題文 : Queue概要 : 長さ$n$ の文字列があり, 'M' と'F' から構成されている. 1 ターンの間に次の動作を行う : "MF" という部分文字列を"FM" に置き換える.文字列が"FF.....MM" という形になるのは何ターン後か?$n \leqq 10^6$

Josephus Permutation

問題文 : Josephus Permutation解法 :アルゴリズムイントロダクションに乗っていた問題を実際にコードに起こしたもの. ヨセフスの芋の軌跡をたどったものを出力する問題. 愚直にm % n 個先までたどる線形リストなどではO(n^2) となり. TLE するだろう. そこ…

JOI春合宿 2009-day2 Contest

問題文 : コンテスト解法 : まずは, 国C の得点を最大化する. これは, 得点が不明なチームの降順に点数を2 つ(若しくは足りない分)取れば良い.次に, 国C の順位を最大化する. これは, 二分探索を行なって位置を定めてやれば良い. (X 位になれる -> X + 1 位…

IJPC # 3 C - Honest Fox and Dishonest Man

問題文 : しょうじききつね と うそつきにんげん解法 : はじめに"正直者の人数" をもととしたグループを作ると, それが正しい可能性のあるグループは高々O(√N) 個しかできない. 明らかに嘘を付いている人物がいれば, その人を使って正直者かどうかの判定を行…

JOI 春合宿 2012-day4 Chinese

問題文 : 中華料理解法 : 委員 a が 料理 b を食べるとき, 理事長の前にある料理はb - a となる. このような料理たちを通る最小手順を, すべてのありうる開始地点について考える問題である. これを考えるにあたって, 折り返しはたかだか1 回で良いことに注意…