Problem - C - Codeforces Difficulty: 1800 問題概要 英小文字で構成される長さNの文字列Sと整数kが与えられる．連続する2文字にはスコアが存在し，文字列のスコアは，隣接する2文字のスコアの合計である．Sをk文字まで好きな文字に置き換えることが許され…

Problem - D - Codeforces Difficulty: 2000 問題概要 待ち行列を考える．今N人の人が一列に並んでいて，レジにてサービスを受ける時間待ちをしている．ある人iがサービスを受け終わるのにかかる時間はAiである．このレジは先頭3人の内，2人選んで同時に捌く…

Problem - C - Codeforces Difficulty: 1900 問題概要 開きカッコと閉じカッコの２種類からなる文字列Sが与えられる．この文字列の部分文字列で，"対応が取れている"ものの中で最も長いものの文字列長と，その数を答えよ． ただし，"対応が取れている"文字列…

Problem - 118D - Codeforces Difficulty: 1800 シンプルなDP．多分どうやっても解ける感じの問題だが，状態数が多いのでスマートに実装を行わないと沼にハマる． 問題概要 n1人の歩兵とn2人の騎兵を一列に並べる．歩兵はk1人を超えて連続してはならず，騎兵…

考察のはじめの一歩が難しかったので記録 全体の方針 エスパーをして，最終的に座標(x,y)にたどり着くのが最適であると知っていたとする． もちろんこのような点は複数ある場合もある． では最適なゴール(x,y)に辿り着くためには，実際にどのようなベクトル…

方針は2つあり，貪欲法とトポロジカルソートを利用するものがある． 貪欲法 問題より，各人には次に対戦すべき相手リストLが与えられる． Aさんの次に対戦すべき人がBさんだったとする．Bさんの次に対戦すべき人がAさんだった場合， 試合を行う(この状態を相…

蟻本とかにあるpriority_queueを使ったダイクストラ法の計算量の見積もりがよくわかってなかったので，メモ． 詳しい実装は蟻本を見てもらうとして，問題となるコードは大体以下の通り． while(!que.empty()){ P p = que.top(); que.pop(); // (1) int v = p…

vectorのemplace_backが良さそうということに案外気付いたのでメモ vector<pair<int,int>> a; a.push_back(make_pair(1,2)); //これはok a.push_back(1,2); //これは駄目 a.emplace_back(make_pair(1,2)); //これはok a.emplace_back(1,2); //これもok!! なんでこれが許さ</pair<int,int>…

Effective STLのお勉強 第1章コンテナから コンテナの選択について コンテナライブラリは、キュー、リスト、スタックのような一般的なデータ構造をプログラマが簡単に実装することを可能とする汎用のクラステンプレートとアルゴリズムのコレクションです。(c…