AtCoder Regular Contest 040 C - Z塗り

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

SRM515 Div1 Easy - RotatedClock

問題 時計の長短針の角度を与えるので時刻として正当なものを出力せよ。 解法 回して12通り試す。 コード #include"bits/stdc++.h" using namespace std; using ll = int64_t; class RotatedClock { public: string getEarliest(int hourHand, int minuteHan…

SRM514 Div1 Easy - MagicalGirlLevelOneDivOne

解法 各に対して、が偶数なら適当に式をいじると必ず可能であることがわかる。奇数だけのときはがであるかどうかで判定できる。 コード #include"bits/stdc++.h" using namespace std; using ll = int64_t; class MagicalGirlLevelOneDivOne { public: strin…

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

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

AtCoder Regular Contest 038 C - 茶碗と豆

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

AtCoder Regular Contest 037 C - 億マス計算

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

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

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

AtCoder Regular Contest 034 C - 約数かつ倍数

問題 正整数が与えられる。の約数であり、かつの倍数でもあるような整数の個数を求めよ。 解法 求めるものは結局の約数の個数である。これはまでの数字を素因数分解し、登場する素因数の数を数えていくことで求めることができる(約数の個数の公式)。各素因数…

SRM513 Div1 Easy - YetAnotherIncredibleMachine

問題 枚の板について長さと設置できる上下限位置が与えられる。また個のボールが各座標に落とされる。板に一つもボールが落ちないような板の配置方法が何通りあるか求めよ。 解法 ボールが落ちる位置について累積和を取って、各板が設置可能な範囲を二分探索…

SRM512 Div1 Easy - MysteriousRestaurant

問題 日間営業するレストランで夕食を食べることを考える。レストランは常に種類のパターンを用意しているが、ある曜日にあるパターンの夕食を食べると、同じ曜日には同じパターンの夕食した食べられない。日目の番目のパターンに対するコストを与えるので、…

AtCoder Regular Contest 033 C - データ構造

問題 数の集合に対する以下のクエリを処理せよ。 タイプ1 : に数を追加する。 タイプ2 : に含まれる数のうち番目に小さい数を答え、その数をから削除する。 解法 「番目に小さい数⇔それ以下の数が個以上追加されている数のうち最も小さい数」と考え、ある数…

AtCoder Regular Contest 032 C - 仕事計画

問題 個の仕事があり、番目の仕事は時刻に始まりに終わる。時刻が重ならないようにできるだけ多くの仕事をこなすことを考えたとき、こなす仕事の種類を選び方が複数ある場合は辞書順最小のものとして構築せよ。 解法 として後ろから求めていく。遷移は仕事を…

AtCoder Beginner Contest 109 参加ログ

結果 10分ちょっと遅れてスタートし、24分ほどかけて全完。Dでアホみたいな2WA出してペナルティ食らったのは反省。 A - ABC333 脳みそを使いたくなかったので愚直にやった。コード #include"bits/stdc++.h" using namespace std; using ll = int64_t; int ma…

AtCoder Regular Contest 031 C - 積み木

問題 全て高さが違う個の積み木が1列に並べられている。隣り合う積み木を交換する操作ができるとき、一番高い積み木から順に左右へ低くなっていくような状態へ変化させるのに必要な最小の操作回数を求めよ。 解法 一番大きな積み木から位置を確定させていく…

SRM511 Div1 Easy - Zoo

解法 一番身長が高いもの以外、ある数字を言う動物は1匹か2匹。0から最大値までそれ以外が出てきたらおかしく、また一度1になってから再び2になるのもおかしいのでそれも弾く。それ以外2匹のときはどっちかを選べるので×2,最後が1だったらさらに×2をすれば答…

SRM510 Div2 Medium - TheLuckyGameDivTwo

解法 最初に以下の数字の中でLucky Numberはいくつあるかを計算しておき、両者が選べる数字の範囲について全探索すればいい。 コード #include"bits/stdc++.h" using namespace std; using ll = int64_t; class TheLuckyGameDivTwo { public: int find(int a…

AtCoder Regular Contest 030 C - 有向グラフ

問題 頂点辺の有向グラフが与えられる。各頂点にはアルファベットが一つ書かれている。 このグラフを好きな頂点から任意の順番で訪問し、個のアルファベットを回収することを考える。頂点は何度も訪問することができ、ある頂点に書かれたアルファベットは任…

AtCoder Regular Contest 029 C - 高橋君と国家

問題 個の都市と本の道を持つ国家がある。都市には交易所を置くという操作ができ、道には舗装するという操作ができ、それぞれ各都市、道ごとにコストが設定されている。全ての都市について、「その都市に交易所が設置されている」あるいは「舗装された道のみ…

AtCoder Regular Contest 028 C - 高橋王国の分割統治

問題 頂点の木に対して、各頂点についてその頂点を通らずに通行可能な頂点集合の最大の大きさを求めよ。 解法 ある頂点を根としたときの答えを求めることを考える。根から行ける各頂点について、その頂点の下にいくつの頂点があるかを深さ優先探索で求め、そ…

AtCoder Regular Contest 027 C - 最高のトッピングにしような

問題 ある飲食店では種類のトッピングを行うことができる。トッピングを入手したときに得られる嬉しさはであり、枚のチケットを使うと入手できるが、その中には1枚以上スペシャルチケットを含んでいる必要がある。同じトッピングを複数回入手することはでき…

AtCoder Regular Contest 026 C - 蛍光灯

問題 西側メートル地点から東側へメートル分の廊下がある。この廊下には個の蛍光灯が付いており、番目の蛍光灯は地点から地点の間を照らすことができ、点けるのに円の費用がかかる。廊下をすべて照らすときの最小費用を求めよ。 解法 まず蛍光灯を左端の値で…

AtCoder Regular Contest 025 C - ウサギとカメ

問題 ウサギとカメがレースをする。個の地点があり、地点間は本の道で繋がれている。ウサギの速さがm/s、カメの速さがm/sであると与えられるとき、カメが先に目的地に到着するような目的地、ウサギのスタート地点、カメのスタート地点の選び方の個数を求めよ…

AtCoder Regular Contest 024 C - だれじゃ

問題 長さの文字列の中から、長さの連続な部分文字列を重複が無いように二つ選んだ時、それらがアナグラムになっているようなものが元の文字列の中に存在するかを判定せよ。 解法 長さの部分文字列が互いにアナグラムになるかどうかは、その中にどの文字が何…

SRM510 Div1 Easy - TheAlmostLuckyNumbersDivOne

問題 からまでの整数の中で4と7以外の数字を多くとも1つしか使わない数字はいくつあるか求めよ。 解法 桁DPのメモ化が無いようなもの。状態として、 上から何桁目を見ているか 4と7以外の数字が何回出てきたか 今まで見てきた要素でより大きいことが保証され…

SRM509 Div1 Easy - LuckyRemainder

問題 整数から数字を1つ以上取り除き残った数字を順番はそのままに右へ詰めてできる整数らの和を9で割った余りを求めよ。 解法 上の桁から順番に9で割った余りがそれぞれ何回出てくるかを記録していく。これをとする()。桁目の数字がだったとき、これを使う…

AtCoder Regular Contest 023 C - タコヤ木

問題 広義単調増加列のうち一部分が不明となっている列が与えられる。あり得る組み合わせの数を求めよ。 解法 不明な部分が連続している一つの塊に注目する。たとえば定数についてという部分列を考えるとすると、からに至るまでの4回の遷移の総和がとなって…

AtCoder Regular Contest 022 C - ロミオとジュリエット

問題 頂点の木が与えられるので最も距離が長くなるような2つのノードのペアを一つ答えよ。 解法 ある頂点を根として考え、そこから再帰関数を回す。それぞれの関数内では、そのノードから各リーフノードへの距離と、リーフノードの番号を返すようにする。一…

AtCoder Regular Contest 021 C - 増築王高橋君

問題 個の建物を回増築することを考える。建物は 最初の価格はである 増築するときには現在の価格に等しい費用がかかる 1回増築すると価格が上昇する 回増築するのに必要な価格の合計値の最小値を求めよ。 解法 解法の流れは、まず最後に増築するときの費用…

AtCoder Regular Contest 020 C - A mod B Problem

問題 ある整数を与えるのでをで割った余りを求めなさい。しかしは非常に大きく、についてが回繰り返されたものを上の桁から順番に並べたものとして表されるものとする。 解法 ダブリング。を回並べてできる整数をとすると、を回並べてできる整数は$$ k \time…

AtCoder Regular Contest 019 C - 最後の森

問題 縦行、横列のマス目で構成されているマップについて各マスは 平地……平地のマスは自由に通行できる。 木……木のあるマスは通行できない。 強敵のいるマス……凶暴な強敵のいるマスである。後述の条件を満たさなければ通行できない。 プレイヤーの村……プレイ…