裏紙

ほぼ競プロ、たまに日記

Codeforces

BAPC 2017 J - Jumping Choreography

問題 http://codeforces.com/gym/101666/attachments/download/6490/2017-benelux-algorithm-programming-contest-bapc-17-en.pdf 問題概要 はじめ、数直線上に匹のカエルがいる。番目のカエルの位置はである。 カエルはジャンプによって移動することができ…

CF 938 F - Erasing Substrings

問題 Problem - F - Codeforces 問題概要 英小文字のみで構成された長さの文字列がある。これに対して、回目の操作では長さのの連続する部分列を切り取り、残った部分を連結してとする、ということをがなくなってしまう直前まで行う(つまり回数をとすると、)…

CF 958 E3 - Guard Duty (hard)

問題 Problem - E3 - Codeforces 問題概要 個の白い点と個の黒い点の座標が与えられるので、完全二部マッチングをつくりたい。マッチングさせた者同士を線分で結ぶ時に、その線分が交差しないような割り当て方を答えよ。 2点が同じ位置にある・3点が同じ直線…

CF 822 E - Liar

問題 Problem - E - Codeforces 問題概要 長さの文字列と長さの文字列が与えられる。をいくつかの部分文字列に分解して、その中から任意の個数を選んで順序を崩さないように結合させる。その結合させた文字列をと一致させるために、できるだけ結合の数減らし…

CF 809 C - Find a car

問題 Problem - C - Codeforces 問題概要 のグリッドがある。上から行目、左から列目のセルをと表す()。各グリッドには、条件に従って数字が書き込まれている。その条件とは、 に書き込むのは、このマスより左側一直線()と上側一直線()の中に現れていない正…

CF 813 E - Army Creation

問題 Problem - E - Codeforces 問題概要 長さの数列と整数が与えられる。次のようなクエリが個与えられるので、それに答えよ: クエリ : 区間 について、同じ値は個までしか選べない時に、最大で何個まで選べるか (問題を読んでもらうと分かるが、オンライ…

CF 712 E - Memory and Casinos

問題 Problem - E - Codeforces 問題概要 個のカジノが一列に並んでいる(左から番目のカジノをカジノと呼ぶ)。カジノで遊んだ時に、勝つと1つ右に移動する。このときに勝つ確率はである。負けると1つ左に移動する(勝率は)。番目の左側と番目の右側は出口であ…

CF 811 E - Vladik and Entertaining Flags

問題 Problem - E - Codeforces 問題概要 のグリッドがあり、各セルに数字がかかれている。グリッドの美しさを、連結成分の個数と定義する(同じ数字かつ上下左右のいずれかで触れていれば連結とする)。 クエリ: グリッドの左端を、右端をで切った時に残る部…

CF 835 F - Roads in the Kingdom

問題 Problem - F - Codeforces 問題概要 頂点辺の無向グラフが与えられる。辺は頂点とを結ぶ長さの辺である。 このグラフのinconvenienceを、「全ての頂点対の最短路のmax」と定義することにする。 このグラフから連結性を保ちつつ1つだけ辺を取り除く時の…

CF 877 F - Ann and Books

問題 Problem - F - Codeforces 問題概要 長さの数列と整数が与えられる。クエリ:「閉区間内の連続部分列で、その和がになるものの個数を答える」が個与えられるのでそれぞれに答えよ。 アイデア prefix sumを使えば、ある区間の和はで取ることが出来る。以…

CF 900 D - Unusual Sequences

問題 Problem - D - Codeforces 問題概要 数列について、かつを満たすような数列が何種類存在するか、で割った余りを求めよ。 アイデア まず、数列の全てのgcdがであるということは、数列の全ての要素はの倍数であるということになる。よってその和もの倍数…

CF 909 F - AND-permutations

問題 Problem - F - Codeforces 問題概要 長さの順列がそれぞれあるかどうかを判定し、ある場合はその具体例を1つ示せ。 全てのについて、かつであるような順列 全てのについて、かつであるような順列 (ANDはbitwise and(C++でいう&演算子)) アイデア pにつ…

CF 847 L - Berland SU Computer Network

問題 Problem - L - Codeforces 問題概要 台のルータがあり、何台かはコードで繋がれており、ネットワークを構成している。ルータの構造は木である。次のような情報が与えられるので、元のネットワークの構造を復元せよ: それぞれのコードとと直接繋がって…

CF 847 J - Students Initiation

問題 Problem - J - Codeforces 問題概要 頂点辺の無向グラフが与えられる。この各辺について、どちらかに向きを付けなければならない。その時に各頂点からの出次数の最大値が最小になるような割り当て方を答えよ。 多重辺や自己ループはない アイデア 各辺…

CF 782 D - Innokenty and a Football League

問題 Problem - D - Codeforces 問題概要 サッカーチームが個ある。それぞれのサッカーチームにはチーム名があり、2単語から構成されている。 各チームの省略形を3文字で決定したい。各チームに対して、省略形の候補は2種類ある: 1単語目のprefix3文字を取…

CF 871 C - Points, Lines and Ready-made Titles

問題 Problem - C - Codeforces 問題概要 2次元平面上に点が個ある。番目の点の座標はである。各点に対して、x軸に平行な線を描く、y軸に平行な線を描く、何も描かないのどれかの操作を選ぶことが出来る。 この個の点から描かれた線を平面上に描かれた画像と…

CF 765 F - Souvenirs

問題 Problem - F - Codeforces 問題概要 長さの数列が与えられる。 とが与えられ、 の最小値 を答えよというクエリが個与えられるので、それらに答えよ。 アイデア まず、絶対値を考えるのはややこしい。数列をreverseしてindexもreverseして同じクエリに対…

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