けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

見積り大事

Codeforces Round #684 (Div. 1) B. Graph Subset Problem (R2600)

TLE が厳しくて話題になってた 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ [tex G] が与えられる。また、正の整数 が与えられる。 以下のいずれかの条件を満たすものが存在するかどうかを判定し、存在するならばそれを出力せよ。 type 1: の…

AtCoder ABC 042 C - こだわり者いろはちゃん (ARC 058 C) (緑色, 300 点)

記念すべき新体制 AtCoder になってからの初の rated ABC の C 問題!!! 問題のリンク 問題概要 以上の整数のうち、 種類の数値 のいずれも含まない最小のものを求めよ。 制約 考えたこと 真っ先に思い浮かぶ方法は、単純に と順々に試していって「 をいず…

Codeforces Grakn Forces 2020 F. Two Different (R2300)

ならば になるネタ、結構見る! 問題へのリンク 問題概要 数列 があって、初期状態では となっている。ここで 2 つの正の整数の組 に対して正の整数 を返す関数 を考える。 次の条件を満たす操作列を構築せよ。1 つの操作は整数 で与えられ、 , をともに で…

AOJ 3166 Not Found (HUPC 2020 day1-C)

単純に bit 全探索で良さそう。 問題へのリンク editorial 問題概要 長さ の 0 と 1 からなる文字列が 個与えられる ()。以下の条件を満たす文字列 が存在するかどうかを判定し、存在するならば具体例を一つ与えよ。 の長さは は '0' と '1' と '*' のみで構…

AtCoder ABC 175 F - Making Palindrome (橙色, 600 点)

こういう重たい実装を確実にこなせるように...なりたい! 問題へのリンク 問題概要 個の文字列 が与えられる。これらを好きな順序で好きな回数だけ concat して回文を作りたい。ただし 番目の文字列を使用するコストは 1 回あたり である。 回文を作れるかど…

AtCoder ABC 166 D - I hate Factorization (茶色, 400 点)

一瞬ヤバそうに見えるけど、落ち着いて考えると、 くらいまで調べればいいという 問題へのリンク 問題概要 正の整数 が与えられるので、 を満たす整数 を一つ求めよ。 制約 考えたこと こういうの、基本的には全探索。でも という制約を見ると、 あたりまで…

Codeforces Round #489 (Div. 2) D. Nastya and a Game (R2100)

方針立ってからも、ちょっと実装辛い ^^; 問題へのリンク 問題概要 長さ の正の整数列 と、正の整数 が与えられる。 正数列の連続する部分列であって、その積が、和の 倍となっているものが何通りあるかを求めよ。 制約 考えたこと パッと思うことは、積の中…

AtCoder ABC 161 D - Lunlun Number (緑色, 400 点)

この手の DFS、一時期全然見なかったけど、最近復活してきた! 問題へのリンク 問題概要 1 以上の整数であって、隣り合う桁の値の絶対値が 1 以下であるような数をルンルン数とよぶ。 番目に小さいルンルン数を求めよ。 制約 考えたこと さて、「 番目に小さ…

AtCoder AGC 003 E - Sequential operations on Sequence (赤色, 1400 点)

この頃、数列を繰り返すのが流行ってたのかな 問題へのリンク 問題概要 長さ の恒等数列 () が与えられる。この数列に以下の操作を合計で 回行う。 番目の操作は、パラメータ であらわされ、以下のように行われる。 現在の数列を無限回繰り返した数列の先頭 …

CADDi 2018 E - Negative Doubling (黄色, 800 点)

こういうのを確実に... 問題へのリンク 問題概要 1 以上の整数からなる長さ の数列 が与えられる。この数列に対して、以下の操作を好きな回数だけ好きな順序で行うことで広義単調増加となるようにしたい。最小回数を求めよ。 個の整数から 1 つ選んで -2 倍…

yukicoder No.979 Longest Divisor Sequence

LIS の亜種だけど、雰囲気違って面白い! 問題へのリンク 問題概要 長さ の正の整数列 が与えられる。この部分列であって 狭義単調増加 後の index に出てくるやつは前の index にでてくるやつの倍数になっている という条件を満たすものの最長の長さを求め…

第6回 ドワンゴからの挑戦状 2020 予選 E - Span Covering (赤色, 1100 点)

すごく面白かった!!!!!!! 問題へのリンク 問題概要 長さ のマス目があって、長さがそれぞれ の 個の区間を配置していきたい。 個の区間がすべてのマスを被覆するような配置方法は何通りあるか、1000000007 で割ったあまりを求めよ。 制約 考えたこと …

AtCoder ABC 153 D - Caracal vs Monster (灰色, 400 点)

こういうのだったら、愚直な再帰関数がバッチリはまる!!! 問題へのリンク 問題概要 体力 のモンスターに魔法を唱えたとき ならば、モンスターは倒れる ならば、モンスターは体力が (小数点切り捨て) の 2 体のモンスターに分裂する 最初は体力が のモンス…

Codeforces Round #609 (Div. 1) A. Long Beautiful Integer (R1700)

こういうのは、いかにシンプルにできるか... 問題へのリンク 問題概要 桁の整数 が与えられる (文字列として)。leading zero はない。整数 が与えられる。 以上の整数 であって の 桁目と 桁目の値は等しい という条件を満たす最小値を求めよ。 制約 考えた…

AtCoder AGC 014 A - Cookie Exchanges (灰色, 300 点)

何回も何回も操作すると同じことになる系 問題へのリンク 問題概要 3 つの整数 があたえられる。以下の操作を行えなくなるまで繰り返す: 3 つの整数の中に奇数が 1 個でもあったら終了 すべて偶数だったら を に置き換える 操作を何回行うか?無限に行う可能…

AOJ 3054 Tunnel (RUPC 2019 day2-D)

離散量だなんて思わなかった。。。 問題へのリンク 問題概要 (略) 個の長方形からなるヒストグラム (x 座標が から の範囲に存在していて、それぞれの長方形の高さが ) が与えられて、それに合わせて折れ線を最適化する。 折れ線の始点は 正の整数 があって…

AtCoder ABC 101 D - Snuke Numbers (ARC 099 D) (黄色, 500 点)

完全に冷静さを欠いたし、ハマったん。。。 ARC 099 D - Snuke Numbers 問題概要 (ARC 099 D / ABC 101 D) 正の整数 N に対してその 10 進法での桁の和を f(N) で表す。今、正の整数 N がすぬけ数であるとは、任意の N より大きい正の整数 M に対して f(N) /…