読者です 読者をやめる 読者になる 読者になる

h_nosonの日記

競プロなど

Codeforces Round #367 (Div. 2) D. Vasiliy's Multiset

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

Codeforces Round #365 (Div. 2) C. Chris and Road

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

Codeforces Round #363 (Div. 2) E. LRU

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

Codeforces Round #355 (Div. 2) D. Vanya and Treasure

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

Codeforces Round #353 (Div. 2) C. Money Transfers

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

Codeforces Round #352 (Div. 2) B. Different is Good

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

Codeforces Round #352 (Div. 2) A. Summer Camp

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

Codeforces Round #350 (Div. 2) F. Restore a Number

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

Codeforces Round #350 (Div. 2) E. Correct Bracket Sequence Editor

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

Codeforces Round #350 (Div. 2) D1,D2. Magic Powder

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

Codeforces Round #350 (Div. 2) C. Cinema

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

Codeforces Round #350 (Div. 2) B. Game of Robots

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

Codeforces Round #350 (Div. 2) A. Holidays

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

Codeforces Round #349 (Div. 2) B. Coat of Anticubism

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

Codeforces Round #349 (Div. 2) A. Pouring Rain

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