競技プログラミング

AtCoder Regular Contest 101 D - Median of Medians

問題 長さの数列についてで切り取られる部分列の中央値をとする。全てのについてを並べた数列について中央値を求めよ。 解法 解説そのまま。 長さがである数列における中央値は「の中にそれより大きいものが個ある整数の中で最大のもの」である。つまりの中…

AtCoder Regular Contest 058 E - 和風いろはちゃん / Iroha and Haiku

問題 長さがであり、各要素がからまでの整数である数列について、連続する部分列で和がとなるものがこの順で連続しているときを含むとする。を含むものが何通りか求めよ。 解法 ほぼ解説の通り。 を含まないものの数を考える。左から一つずつ数列の値を決定…

AtCoder Regular Contest 057 C - 2乗根

問題 の上桁がとなるような最小の正整数を求めよ。 解法 解説そのまま。 10進法でと表記されるものをとする。の上桁がとなっていることはある整数が存在しと同値。 でこの条件を満たす正整数が存在する場合、ではより範囲が広がるのでやはり正整数が存在する…

AtCoder Regular Contest 056 C - 部門分け

問題 人の社員をいくつかの部門に分けることを考える。社員との間には信頼度が定まっており、部門分けのスコアはを定数として として計算される。スコアの最大値を求めよ。 解法 を社員の集合に対する問題の答えとする。の部分集合をとして、これが一つの部…

AtCoder Regular Contest 055 C - ABCAC

問題 文字列が与えられるので、それを空でない文字列を用いて (文字列を連結したもの)と分割する方法が何通りあるかを求めよ。 解法 と分ける切れ目を全探索する。分けられた前半部分と後半部分で、prefixとsuffixがそれぞれ何文字一致しているかが分かれば…

AtCoder Regular Contest 054 C - 鯛焼き

問題 タイヤと木がそれぞれ個あり、各タイヤと木の組について相性が良いか悪いかが決まっている。相性の良いタイヤと木のみを組み合わせて全てのタイヤと木を組み合わせる方法が何通りあるか、その偶奇を求めよ。 解法 行列式を計算して2で割った余りを求め…

AtCoder Regular Contest 053 C - 魔法使い高橋君

問題 個の魔法があり、番目の魔法を唱えると気温が度上がって度下がる。全ての魔法を1回ずつ唱えるとき、この間の気温の最大値を最小化せよ。 解法 まずであるものについての昇順に、次にであるものについて任意の順番に、最後にであるものについての降順に…

AtCoder Regular Contest 061E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip

問題 個の駅が個の路線で繋がれている。各路線は一つの会社によって運営されており、同じ会社の路線を使い続ける限り料金は1である一方、違う会社の路線に乗り換える場合は新たに料金が1かかる。駅から駅まで移動するのにかかる料金の最小値を求めよ。 解法 …

SRM519 Div1 Easy - BinaryCards

問題 なんだっけ。 解法 なるほどなぁ。 コード #include"bits/stdc++.h" using namespace std; using ll = int64_t; class BinaryCards { public: long long largestNumber(long long A, long long B) { if (A == B) { return B; } ll ans = 0; while (true…

SRM518 Div1 Easy - LargestSubsequence

問題 辞書順最大の部分文字列を求めよ。 解法 大きい文字から取っていって、一番最後に取った位置を記録しておく。次の文字はそこからスタート。 コード #include"bits/stdc++.h" using namespace std; using ll = int64_t; class LargestSubsequence { publ…

AtCoder Beginner Contest 112

結果 36分22秒(3WA)で全完。89位。WAが多すぎた。 A問題 場合を分ける。 #include"bits/stdc++.h" using namespace std; using ll = int64_t; int main() { ll N; cin >> N; if (N == 1) { cout << "Hello World" << endl; } else { ll A, B; cin >> A >> B;…

AtCoder Regular Contest 052 C - 高橋くんと不思議な道

問題 個の町が個の道で結ばれている。道はタイプの二種類が存在し、タイプのコストは1、タイプのコストは(今まで通ったタイプの道の本数) + 1である。全ての町について町0からの最小コストを求めよ。 解法 タイプの道はあまり多く使わない方が良い。具体的に…

AtCoder Regular Contest 051 C - 掛け算

問題 個の整数が与えられる。「一番小さいものを倍する」という操作を回繰り返した後の整数たちを昇順に並べ出力せよ。 解法 解説PDFの通り。 がソートしてあるとして、ならばそのあと操作される整数はとなる。したがってそれ以降が何回かけられるかは簡単に…

AtCoder Regular Contest 050 C - LCM 111

問題 を個並べてできる整数を、個並べてできる整数をとしたとき、との最小公倍数をで割った余りを求めよ。 解法 を個並べてできる整数をとしたときであることがわかる。最小公倍数はであるので、をで割った余りが求まれば良い。とする。ここでは「が個、が1…

AtCoder Regular Contest 049 C - ぬりまーす

問題 頂点のグラフについて、二つのタイプの条件の下に色を塗っていくことを考える。 タイプ1:ある頂点に色を塗るとき、既に頂点に色が塗られてなければならない。 タイプ2:ある頂点に色を塗るとき、既に頂点に色が塗られていてはいけない。 タイプ1の制約は…

AtCoder Regular Contest 048 C - 足の多い高橋君

問題 高橋君には足が本あり、番目の足は本の骨が一列に繋がった構造をしている。全ての骨にまたはを書き込むことにし、任意の足2本について片方の足先から胴体を通ってもう一方の足先まで辿って読むと回文になるようにしたとき、文字の書き込み方としてあり…

AtCoder Regular Contest 047 C - N!÷K番目の単語

問題 までの整数による順列は個あるが、それらを辞書順に並べたときの個目のものを求めよ。 解法 先頭からどの数字を置くべきか決定していくが、それを「まだ使っていない数字の中で何番目に小さいものを置くべきか」を求めることによって決定していく。辞書…

AtCoder Regular Contest 046 C - 合コン大作戦

問題 人の男性と人の女性が合コンをした。男性は年収が円であり、年収が円以上の女性とカップルになりたいと考えている。女性もまた年収と相手の年収の希望を持っている。これらが同時に満たされるとカップルが成立するとき、最大のカップル数を求めよ。 解…

SRM517 Div1 Easy - CompositeSmash

問題 整数をそれぞれ2以上である数字の積に分解する操作が行える。分解して得られる整数はランダムであるとするとき、整数を作ることができるかどうか判定せよ。 解法 気合を入れて場合分けをする。 コード #include"bits/stdc++.h" using namespace std; us…

SRM516 Div1 Easy - NetworkXOneTimePad

問題 ciphertextsにある任意の数字が、plaintextsのどれかの数字にxorしたものに等しくなるようなキーの数を求めよ。 解法 各暗号化済みの数字と暗号化前の数字のxorを取るとキーとなり得る数字を求められる。それの登場回数をmapで数えておく。キーとなる数…

AtCoder Regular Contest 045 C - エックスオア多橋君

問題 頂点の木が与えられる。各辺に非負整数のコストがついているとき、頂点とを結ぶ単純パスにおいて通る辺のコストを全てxor取っていったものがある整数になるようなの組み合わせが何通りあるか求めよ。 解法 ある頂点を根と決めたとき、という単純パスと…

AtCoder Regular Contest 044 C - ビーム

問題 のグリッドにビームが飛んでくる。ビームは時刻に縦方向あるいは横方向についてあるマスを通るように飛ぶ。高橋君は任意のマスからスタートして上下左右のマスについて単位時間に任意の回数移動できる。全てのビームについての情報がわかっているとき、…

AtCoder Regular Contest 043 C - 転倒距離

問題 2つの順列について順序が入れ替わっている数字の組の個数を転倒距離と呼ぶこととする。サイズの順列が与えられたとき、ともとも転倒距離が等しい順列があるか判定し、ある場合には1つ挙げよ。 解法 まず適当な数字の置き換えをしてがという配列になるよ…

AtCoder Regular Contest 042 C - おやつ

問題 種類のおやつについてそれぞれ値段と満足度が設定されており、各種類について多くとも1つ持っていくことができる。どの1つのおやつについてもそのおやつがなければ合計で円以下になるとき持っていくことが可能である場合に、満足度の最大値を求めよ。 …

AtCoder Regular Contest 041 C - ウサギ跳び

問題 個のマスが横一列に並んでおり、マスの上には匹のウサギが右か左を向いている。ウサギは向いている方向の一つ前のマスに他のウサギがいなければジャンプしてそのマスへ移動できる。ウサギがジャンプする順番を自由に選べるとき、ジャンプの総回数の最大…

AtCoder Regular Contest 040 C - Z塗り

問題 のマス目状になっている床を一色に塗ることを考える。一回の塗る操作で、ある整数に対して「かつ」または「かつ」を満たすような全てのマスを塗ることができる。部分的に塗られている初期状態が与えられるので、全てのマスを塗る最小の操作回数を求めよ…

AtCoder Regular Contest 039 C - 幼稚園児高橋君

問題 無限に広がる二次元格子について最初から出発し、以下のような行動を繰り返す。 上下左右のうち好きな方向を決めてその方向に今まで訪問したことのない格子に到達するまで直進し、止まる 直進した回数とそれぞれの方向を与えるので最終的に止まる格子の…

AtCoder Regular Contest 038 C - 茶碗と豆

問題 個の茶碗が横一列に並んでいる。各茶碗には整数が書かれており、中には個の豆が入っている。これらを用いて次のゲームを行う。 プレイヤーは自分のターンに茶碗以外の茶碗に入っている豆を1つ選んで取り出す。 茶碗から豆を取り出したとき、茶碗,茶碗, …

AtCoder Regular Contest 037 C - 億マス計算

問題 個の数列が二つ与えられ、それぞれおよびとする。これらを用いて行列の表を、行列目にはが書き込まれるように作成する。書き込まれた数字の中で番目に大きい数字を求めよ。 解法 番目に大きい数字とは「その数字以下の数字が個以上書き込まれているよう…

AtCoder Regular Contest 035 C - アットコーダー王国の交通事情

問題 個の都市が本の道路で結ばれている。道路には長さがあり、各都市間の最短距離の総和をとする。初期状態から本の新しい道路を建設していくとき、各道路が作られた後のを求めよ。 解法 新たな道路が都市を長さで結ぶとき、各都市について最短距離を更新し…