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

裏紙

ほぼ競プロ、たまに日記

CF 798 D - Mike and distribution

問題 Problem - D - Codeforces 問題概要 長さの数列とが与えられる。 いま、数列のindexを個選ぶことが出来る。選んだ個のindexをとするとき、次の条件を満たすように個のindexを選べ: このような条件を満たすを答えよ。 アイデア まず、は多いほうが得だ…

CF 785 D - Anton and School - 2

問題 Problem - D - Codeforces 問題概要 (と)のみで構成される文字列について、次のような長さの文字列をregular simple bracket sequences(RSBS)と呼ぶことにする: 空文字列ではない() は偶数で、前半の文字は全て(、後半の文字は全て) 例えば((()))はRSB…

CF 740 D - Alyona and a tree

問題 Problem - D - Codeforces 問題概要 頂点数の木があり、各頂点にはからまでの番号が振られている。根の頂点番号はである。各頂点はそれぞれ整数を持っている。 また、辺には重みがあり、本の辺の情報について、個目の情報は頂点とを結んでおり、その重…

CF 738 F - Financiers Game

問題 Problem - F - Codeforces 問題概要 長さの数列が与えられる。この数列を使って、LさんとRさんの2人でゲームを行う。 ゲームはLさんのターンで始まる。まず、Lさんは数列の左端からスタートし、そこから1つか2つの値を数列から取り除きその合計を自分の…

CF 701 F - Break Up

問題 Problem - F - Codeforces 問題概要 頂点辺の無向グラフがある。グラフが連結である保証はない。 いま、ある辺を削除して頂点から頂点への移動をできなくなるようにすることを考える。しかし、辺の削除の上限は2本である。辺にはそれぞれ削除のコストが…

CF 701 E - Connecting Universities

問題 Problem - E - Codeforces 問題概要 頂点数の木があり、頂点にはからの番号が振られている(グラフの情報は、各辺がどの頂点を繋いでいるかが与えられる)。このうち、個の頂点番号が指定される。それらをとする。これら個の頂点から、個のペアを作る。そ…

CF 749 E - Inversions After Shuffle

問題 Problem - E - Codeforces 問題概要 からまでの数を並べた長さの順列がある。1回だけ以下の操作を行う: 全ての区間個のうち、区間(から)をランダムに選ぶ。そして、その区間の長さをとし、その区間に対して、シャッフルを行う(つまり、通りの並び替え方…

CF 733 F - Drivers Dissatisfaction

問題 Problem - F - Codeforces 問題概要 個の町と、それらを双方向に結ぶ道が本ある。それぞれの道に対して、ドライバーの不満度がある。 この不満度を下げるために、その道に対してコストがかかる(つまり、ある道の不満度をだけ低下させるためにはだけかか…

CF 733 E - Sleep in Class

問題 Problem - E - Codeforces 問題概要 段の階段がある。各段は、下から順に番号がからまで付けられており、その各段にはupかdownかのどちらかが書かれており、その段にいるときに進む方向を示している。そして、そこから移動した瞬間に、その段の示す方向…

CF 732 F - Tourist Reform

問題 Problem - F - Codeforces 問題概要 頂点辺の無向グラフがある。このグラフは連結であり、多重辺や自己ループは存在しない。さて、この辺を全て有向辺に変更することを考える。有向辺に変更した後のグラフ上で、を「頂点を始点としたときに訪れることの…

CF 732 E - Sockets

問題 Problem - E - Codeforces 問題概要 台のコンピュータがあり、それぞれ番目のコンピュータは電力を必要とする。今、会場には個のコンセントがあり、番目のコンセントは電力を供給できる。そして、を満たすときに限って、番目のコンピュータと番目のコン…

CF 716 D - Complete The Graph

問題 Problem - D - Codeforces 問題概要 頂点辺の無向グラフがある。辺にはそれぞれ重みがあり、その重さは正の整数である。いくつかの辺の重みがわからなくなってしまったので、その辺に重みを付け直したい。ただし、頂点から頂点への最短経路はでなければ…

CF 682 D - Alyona and Strings

問題 Problem - D - Codeforces 問題概要 アルファベットの小文字のみで構成される文字列があり、長さはそれぞれである。今、の中から共通部分を持たず、それぞれが空ではない部分文字列を個選ぶ。そして、その選んだ個の部分文字列が、の中にも同じ順番で現…

CF 711 D - Directed Roads

問題 Problem - D - Codeforces 問題概要 番から番まで番号が振られた個の街がある。この街の間には本の有向辺があり、それらは番の街から番の街へ伸びている()(つまりそれぞれの街から1本ずつ有向辺が出ており、自己ループはない状態))。 今、自由に何本で…

CF 677 D - Vanya and Treasure

問題 Problem - D - Codeforces 問題概要 のグリッドとして表される宮殿の中にいる.それぞれの部屋の中には引き出しがあり,上から行左から列の位置には番の引き出しがある.番の引き出しには,番の引き出しを開けるためのカギが入っており,番の引き出しは…

CF 653 D - Delivery Bears

問題 Problem - D - Codeforces 問題概要 街で熊を雇って運び屋業をすることにした.街は頂点が個,辺が本ある有向グラフとして表される.各辺には耐えられる重量が決まっている.1回の配達を,1頭の熊が頂点から頂点へ運搬する際のパスとして表現する. 今…

CF 670 F - Restore a Number

問題 Problem - F - Codeforces 問題概要 ある数字があり,それにの桁数を合わせて書いておいた紙があったが,桁の順番がめちゃくちゃになってしまった.(例:として3342が与えられる時,その桁数は4なので紙には33424と書かれるがその順番が入れ替わって3434…

CF 676 E - The Last Fight Between Human and AI

問題 Problem - E - Codeforces 問題概要 多項式が与えられる.初期状態ではこの多項式の係数は全て未定になっている. 人間とAIがゲームをする.まずはじめに,ある整数が与えられる.そして,AIが先手となりゲーム開始となる.ターンごとに,そのターンが…

CF 670 E - Correct Bracket Sequence Editor

問題 Problem - E - Codeforces 問題概要 Correct Bracket Sequence(CBS)という文字列のみに対して動作するテキストエディタを考える。CBSとは、(と)の2種類の文字のみで構成される文字列であり、全てのカッコの開閉が1つ1つ対応付けられているものである((…

CF 631 D - Messenger

問題 Problem - D - Codeforces 問題概要 メッセージの履歴から自分が指定した文字列を検索したい。メッセージは特殊な形に圧縮されて送信される。そのフォーマットはというペアの列によって表される。ここで、は数字、は英小文字であり、そのペアによってと…

CF 632 C - The Smallest String Concatenation

問題 Problem - 632C - Codeforces 問題概要 個の文字列が与えられる。この個の文字列を全てを結合させることを考える。その中で辞書順最小となるものを求めよ。 文字は全て英小文字 文字列の長さの合計はを超えない。 アイデア これは割と典型なテクらしい…

CF 635 C - XOR Equation

問題 Problem - C - Codeforces 問題概要 2つの正の整数に関して、との和を、とのビットごとのXORをで表す。とが与えられる時、の組としてあり得る組合せの数を求めよ。 アイデア まず、に関しての全探索はサイズ的に間に合わない。そこで桁DPで試みる。 小…

CF 628 D - Magic Numbers

問題 Problem - D - Codeforces 問題概要 10進表記の数字を考えて、上から数えて偶数桁目の数が全てdで、奇数桁目の数がdではないものをd-magicであるという。a以上b以下の数字のうち、mの倍数かつd-magicであるものの個数をで割った余りを求めよ。ただし、a…

CF 626 D - Jerry's Protest

問題 Problem - D - Codeforces 問題概要 Harryを記録係として、AndrewとJerryは2人でゲームをする。ゲームは3ラウンドで構成され、ラウンドごとに以下のことを行う: 正の整数が書かれたボールが個入った袋からAndrewとJerryはボールを1個ずつ取り出し、そ…

CF 624 D - Array GCD

問題 Problem - D - Codeforces 問題概要 長さの数列を考える。この数列に対して2つの操作を行うことを考える: 連続している部分の除去(の区間の値を取り除く)、これを区間の長さがの時にのコストで行う 1つの要素の値を1だけ増加または減少させる、これを…

CF 611 D - New Year and Ancient Prophecy

年末に言ってたGoodBye2015の出来なかったやつ。 問題 Problem - 611D - Codeforces 長い数字の列を区切って数列としてみた時に、その数列が単調増加になっている(例見れば分かる)組合せの数。 問題概要 Limakは昔の予言が記された秘密の巻物を見つけた。秘…

CF 608C - Chain Reaction

問題 http://codeforces.com/contest/608/problem/C 概要 n個のビーコンがあり、i番目のビーコンはは数直線上のa[i]の位置におかれ、b[i]の威力を持っている。このビーコンが作動すると、a[i]の位置から左側だけ、b[i]以内の範囲のものを破壊する。(これによ…

CF 606C - Sorting Railway Cars

問題 http://codeforces.com/contest/606/problem/C 1~nまでの数字が1個ずつランダムに並べられている。これを昇順にソートしたい。1回の操作で、ある要素を先頭、または最後尾に移動させることが出来る。ソートするまでに必要な操作の最小回数は何回か。 ア…

CF 553A - Kyoya and Colored Balls

今回(やっと)Codeforcesに初参加した。1:30から2時間も考えてられず,70分くらいたったあたりで「もうやめて寝よう」ってなりました。最初の2問だけ解いて,この問題につまづいたので自分で文字に起こすことで理解を深めたい。こういう系の問題(というかDP)…