問題 Problem - D - Codeforces 3つのクエリに答える． 1. xをmultiset Aに加える 2. xをmultiset Aから取り除く 3. を出力する 解法1 c++のmultisetを使って二分探索をする． xorをとった値が大きくなるように上位のbitから0か1か決めていけばいい．xを反転…

問題 Problem - C - Codeforces N角形のバスがやってくる．幅Wの道路をバスにぶつからずに渡るとき，最短の渡る時間を求める問題 解法 バスを固定すると人が右上に向かって移動することと等しくなる．もしぶつからずにそのまま行けるのであればそのまま行く…

問題 Problem - E - Codeforces N個のデータと容量Kのキャッシュがある．キャッシュのアルゴリズムにLRUが使われていて，無限のクエリが飛んできたとき，最後のキャッシュの状態にそれぞれのデータが含まれる確率はいくつか． 解法 簡単に言うと，キャッシュ…

問題 Problem - D - Codeforces の部屋があり，それぞれ宝箱が置いてある．タイプの宝箱にはタイプの宝箱を開ける鍵が入っている．タイプの宝箱を開けるまでに移動する最小距離はいくつか．解法 単純にタイプごとにダイクストラを行っていたら間に合わない．…

問題 Problem - C - Codeforces 行の銀行が円周上に並んでいる．隣の銀行に送金することが可能になっている．Aさんがそれぞれの銀行に口座を持っていて，お金を預けている（または借りている）．預けているお金を隣の銀行に送金することを繰り返し，すべての…

問題 Problem - B - Codeforces 文字列が与えられる．どの部分列をとっても同じ文字列が現れないように与えられた文字列を書き換えるとき，書き換える最小の文字数は幾つか．解法 部分列は1文字だけ考えればよい．つまり，すべて違う文字になるように書き換…

問題 Problem - A - Codeforces 123456789101112...といったように数字を1から並べた列がある．番目にくる数字は幾つか．解法 1から順に数字をstringに積んでいき，番目にきた数字を出力する．ソースコード #include <iostream> #include <vector> #include <algorithm> using namespace s</algorithm></vector></iostream>…

問題 Problem - F - Codeforces AさんはBさんにある数字にその数字の長さを右に付け足して送った．しかし，送られる途中で文字の順番がバラバラになってしまった．Aさんはその数字の部分列を覚えている．送った可能性のある数字の内，その部分列を含むような…

問題 Problem - E - Codeforces 対応する括弧が存在する括弧の列が与えられる．カーソルの初期位置と R : カーソルを右にずらす L : カーソルを左にずらす D : 今見ている括弧と対応する括弧の間の括弧を消して右に移動する という操作の列が与えられた時，…

問題 Problem - D1 - Codeforces クッキーを作ろうとしている．１つ作るのに種類の材料がずつ必要である．初めにずつ持っているとする．また，のマジックパウダーも持っており，そのパウダーはどの材料にも変えることができる．作れるクッキーの最大値はいく…

問題 Problem - C - Codeforces 人の人がいる．それぞれ使える言語は１つだけである．個の映画があり，音声と字幕は違う言語が使われている．１つの映画を全員で見るとき最も多くの人が満足できる映画はどれか． 音声に満足している人が等しいならば字幕で比…

問題 Problem - B - Codeforces ロボットが体いる．それぞれのロボットに番号が付けられている． 左のロボットから順番に，「ロボットの番号を一番左のロボットの番号から自分の番号まで言う」ことを行うとき，回目に言われるロボットの番号は幾つか．制約 …

問題 Problem - A - Codeforces 火星では１年が日続く．また，地球と同じように１週間は平日が５日，休日が２日ある． １年の休日の数の最大値と最小値はいくつか．解法 ７で割り，最大値を求めるときは余りに対してできるだけ休日から割り当て，最小値を求…

問題 Problem - B - Codeforces 棒が本あり，それぞれの長さはである． それらを繋げても多角形を作ることが出来ない． 1本棒を加えるとき，多角形を作るために必要な最短の長さは幾つか．解法 の最大値をとした時， その他の棒を合わせてが得られれば多角形…

問題 Problem - A - Codeforces 直径cmの円筒があり，初めに高さcmだけ水が入っている． 毎秒mlで水を飲み，また雨によって毎秒cmだけ水かさが増すとき， 水を飲みきれるか，飲みきれるとしたら何秒かかるか．解法 が成り立つので ならば飲みきれ， が答えに…