(問題概要) n ( 幾つかのポストカードをすでに持っている。 持っているポストカードは同じ価格で売ることができる。 価値Kを得るにはいくら追加でお金がいるか。(解法) とりあえず持ってるのは全部売って、一から考えると楽。 問題形式的には典型的ナップザ…

(問題概要) 文字列が幾つか与えられる。 すべての文字列が空になるまでどれかの文字列の先頭文字をくっつける操作を繰り返す。 辞書順最小の文字列を作りなさい。(解法) 貪欲に最小なのをとっていく。 文字列がなくなるケースはあまり嬉しくないのを考慮。 …

(問題概要) A_i = 1 for all i A_i = A_[i/p]-x + A_[i/q]-y A_nを求めよ。(n (解法) メモ化再帰。 ただし全部をmap等でメモるとMLEでセグるので、部分的にメモる。 なんかチーター本で見たような気もする。 typedef long long ll; #include <queue> #include <set> #inc</set></queue>…

※この記事はCompetitive Programming Advent Calendar Div2012 の19日目の記事です。競技プログラミングにおいて、時間内に正しい答えを出せる限り手を抜く(簡単なプログラムを書くの意)のが定石。 ということでとある問題を題材に探索っぽくして幾何で手を…

(問題概要) ２つのTAB譜の変換(解法) やるだけ。制限が色々めんどい。 最近なら250〜300で出ても驚かないレベルの内容。 #include <algorithm> #include <cstdio> #define REP(i,n) for(int i=0; i<(int)(n); i++) #include <queue> #include <set> #include <iostream> #include <sstream> using namespace std</sstream></iostream></set></queue></cstdio></algorithm>…

(問題概要) 回 ← みたいなケーキがある(真ん中に穴が空いてる) 縦と横にそれぞれ何回か包丁を入れた時に、最終的に何ピースのケーキが出来るか。(解法) 縦横で近いカットを２つづつ選ぶとそれに囲まれた四角形ができる。 後はその頂点を見て場合分け。 関数…

(問題概要) nバイトのメモリ、kバイトのキャッシュを持ったマシンを考える。 キャッシュにはメモリ上の連続したkバイトを載せることが出来る。 キャッシュを更新するには、更新前に載っていなかったバイト数だけコストがかかる。 アクセスするアドレス(a[0],…

(問題概要) 本物がspheresCount個、偽物がfakeSpheresCount個、全体からspheresCount個選んで全部正しいかを試す。 全通りを何グループかで試すとき、各グループが同じ通り数を試すには、gnomesAvailable以下で最大何グループ選べるか。 (nCk % m == 0 とな…