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

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

AtCoder400点

AtCoder ABC 169 D - Div Game (400 点)

久しぶりに素因数分解する問題が来た!!!!!!!!!!! 問題へのリンク 問題概要 正の整数 に対して、以下の操作を何回行うことができるか、その最大回数を求めよ。なお、素数 と正の整数 を用いて の形で表すことのできる整数を「素数べき」と呼ぶこと…

AtCoder ABC 138 D - Ki (400 点)

まさに「the 緑 diff」な問題だと思う。 「木を上手く扱えるか」を問いかける問題。 問題へのリンク 問題概要 頂点の木が与えられる。この木の頂点 1 を根とした根付き木を考える。各頂点には初期状態では 0 という数値が書かれている。以下の 回の操作を行…

AtCoder ABC 139 D - ModSum (400 点)

これが灰色 diff なのかーーー、マジかーーー!!! いや、AtCoder プレイヤー、数学強すぎでしょ!!! 問題へのリンク 問題概要 正の整数 が与えられる。 の順列 をすべて考えたときの、 % の値の最大値を求めよ。 制約 考えたこと 文句なしの数学ゲー。で…

AtCoder ABC 140 D - Face Produces Unhappiness (400 点)

ABC では数少ない発想力系。 問題へのリンク 問題概要 L と R から成る 文字の文字列 が与えられる。文字列のスコアは次のようにして決められる。 各 index i について S[ i ] = 'L' ならば、i + 1 >= 0 かつ S[ i - 1 ] = 'L' のときに限り、1 を加算 S[ i …

AtCoder ABC 165 D - Floor Function (400 点)

気づけば一発系。ただし、数式の見た目がエグく見えてしまうかもしれない... 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数 に対する - の値の最大値を求めよ。 制約 考えたこと 全探索すれば だけど、それでは間に合わない。さて、式の…

AtCoder ABC 164 D - Multiple of 2019 (400 点)

まさかの既出!!!しかも割と最近の ABC-E!!! drken1215.hatenablog.com 問題へのリンク 問題概要 から までの数字のみからなる文字列 が与えられる。 の連続する区間であって、 の倍数であるものが何個あるのかを求めよ。 制約 考えたこと 実は完全にマ…

AtCoder ABC 144 D - Water Bottle (400 点)

これかーーー数学ゲーじゃないかと物議を醸した問題。でも普通にいい問題だと思う!! 問題へのリンク 問題概要 底面が一辺 cm の正方形であり、高さが cm であるような直方体型の水筒に、体積 cm3 の水を入れる。 底面の正方形の一辺を軸として、この水筒を…

AtCoder ABC 145 D - Knight (400 点)

この問題のおかげで、僕の二項係数記事が一躍広く普及することになったのだった。 問題へのリンク 問題概要 二次元グリッドの原点 にチェスのナイトの駒がある。 ナイトの駒はマス にあるとき か のどちらかのマスにのみ動かすことができる。 ナイトの駒をマ…

AtCoder ABC 146 D - Coloring Edges on Tree (400 点)

軽めの構築問題!! 今回は「最大次数」というのが割と明らかだけど、しっかり構築法踏まえて証明する練習をすると、高難易度問題にも繋がりそう! 問題へのリンク 問題概要 頂点の木が与えられる。 本の辺に色を塗っていきたい。ただし、どの頂点についても…

AtCoder ABC 147 D - Xor Sum 4 (400 点)

考え方自体は典型的ではある 問題へのリンク 問題概要 個の整数 が与えられる。 これらから 2 個選んで XOR をとって得られる整数 ( 個ある) の総和を 1000000007 で割ったあまりを求めよ。 制約 考えたこと XOR をみたら、とにかく「各桁ごとに考える」とい…

AtCoder ABC 149 D - Prediction and Restriction (400 点)

ちょっと問題を理解するのが大変かもしれない 問題へのリンク 問題概要 ロボットと 回ジャンケンをする。ロボットの出す手はあらかじめすべてわかっている。 グーを出して勝つと 点 チョキを出して勝つと 点 パーを出して勝つと 点 が得られる。ただし 回目…

AtCoder ABC 135 D - Digits Parade (400 点)

よくある桁DPとはまた違うけれど、桁DPの応用問題としてよくあるやつを試せる問題ですね! 問題へのリンク 問題概要 "013?42???2??" のような、'?' と数値で構成された、長さ の文字列が与えられる。 この '?' を埋めて数値を作る方法のうち、13 で割ったあ…

AtCoder ABC 155 D - Pairs (400 点)

最初は、問題を見た瞬間に「にぶたんだ...」となったので、青 diff に驚いたのだった。でもいざ実装を始めると、頭壊れる問題ですね。。。^^; 問題へのリンク 問題概要 個の整数 が与えられる。これらから 2 つを選んで積をとって得られる 個の整数のうち、…

AtCoder ABC 156 D - Bouquet (400 点)

二項係数を使いこなすっ!!! 問題へのリンク 問題概要 種類の花束から何個か選ぶ方法のうち、それが 個でも 個でもないようなものが何通りあるかを 1000000007 で割ったあまりを求めよ。 制約 考えたこと 結局、 個のものからいくつか選ぶ方法 ( 通りある)…

AtCoder ABC 160 D - Line++ (400 点)

すごく色んな考え方ができる問題ですね! 問題へのリンク 問題概要 個の頂点を持つ無向グラフ がある。 の辺集合は と とを結ぶ辺 頂点 と頂点 とを結ぶ辺 とで構成されている。各 に対して、最短距離が であるような頂点対が何個あるかを求めよ。 制約 考え…

AtCoder ABC 163 D - Sum of Large Numbers (400 点)

「作れる数が連続する整数になる」というの、実は結構よくある!! 問題へのリンク 問題概要 個の整数 がある。 これらから 個以上の整数を選んで合計して得られる整数としてありうるものの個数を 1000000007 で割ったあまりを求めよ。 制約 考えたこと まず…

AtCoder ABC 162 D - RGB Triplets (400 点)

落ち着いて頭を整理。。。 問題へのリンク 問題概要 'R', 'G', 'B' のみからなる長さ の文字列 が与えられる。 の index の組 であって、 と と はすべて互いに異なる である という条件を満たすものの個数を求めよ。 制約 考えたこと 頭がごっちゃになりそ…

AtCoder ABC 079 D - Wall (400 点)

Floyd--Warshall と、あとグリッド上の各マスは独立に考えて OK。 問題へのリンク 問題概要 のグリッドがあって、各マスには -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 のいずれかの数値が書かれている。目的は -1 以外のマスをすべて 1 に変えることである。 各マ…

AtCoder AGC 004 B - Colorful Slimes (400 点)

実装を柔軟にしたい 問題へのリンク 問題概要 体のスライムがあって、初期状態では、それぞれの色は となっている。以下の操作を繰り返すことで全てスライムを消滅させたい。そのために必要なコストの最小値を求めよ。 色 のスライムを消滅させる (コストは …

AtCoder ARC 058 D - いろはちゃんとマス目 (400 点)

これが青パフォ!!!!! 時代の進化を感じるところ!!! 問題へのリンク 問題概要 のマス目が与えられる。左上から右下へ進む最短経路のうち、 下から マス以内、かつ 左から マス以内 の範囲内には来ないようなものの個数を、1000000007 で割ったあまり…

Judge System Update Test Contest 202004 D - Calculating GCD (400 点)

面白かった 問題へのリンク 問題概要 要素からなる正の整数列 が与えられる。以下の 個のクエリに答えよ 各クエリは整数 が与えられる の順に、 という更新を行う 初めて となる瞬間の を求めよ 最終結果が 1 より大きいときは、その値を答えよ 制約 解法 (1…

AtCoder ABC 161 D - Lunlun Number (400 点)

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

AtCoder ABC 159 D - Banned K (400 点)

差分更新系の教育的問題かな 問題へのリンク 問題概要 長さ の数列が与えらえる。各 index k に対して、 数列から k 番目の要素を除いたものについて その中から異なる 2 つの要素を選ぶ方法であって (順番は問わず) その 2 つの要素の選び方が等しい という…

AtCoder AGC 043 A - Range Flip Find Route (400 点)

「予め盤面をいじることができる」という設定の問題にはある程度の定石があるように思う! 問題へのリンク 問題概要 の盤面が与えられ、左上から右下まで行きたい。'#' マスは壁を表し、'.' マスは通路を表す。 予め盤面に以下の操作を行うことができる。最…

AtCoder ABC 158 D - String Formation (400 点)

先頭と末尾の両方から push できるデータ構造といえば、deque!!! 問題へのリンク 問題概要 長さ の文字列 が与えられる。以下の 個の操作を行ってできる文字列を出力せよ type 1: 文字列 を左右反転する type 2: 値 F と文字 c が与えられ、F = 1 のと…

AtCoder AGC 003 B - Simplified mahjong (400 点)

微妙なコーナーケースに注意 問題へのリンク 問題概要 の書かれたカードがそれぞれ 枚ある。以下の条件を満たすようにペアリングしていくとき、最大で何組できるか? ペアとなるカードの数値の差は 1 以下 制約 考えたこと 一瞬、 値が等しいペアを作れるだ…

AtCoder ABC 157 D - Friend Suggestions (400 点)

とても教育的な Union-Find!!! 問題へのリンク 問題概要 人がいて、 組の友達関係と、 組のブロック関係がある (いずれも双方向的)。 各人について、 直接的な友達関係ではない ブロック関係でもない 友達の友達の...とたどっていくと到着できる ような人…

CODE FESTIVAL 2017 qual C C - Inserting 'x' (400 点)

少しでも実装を楽にしたい 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。以下の操作を最小回数行って回文にしたい。その最小回数を求めよ。不可能な場合は -1 を出力せよ。 のどこかに 'x' を挿入する 制約 考えたこと まず可…

AtCoder ABC 154 D - Dice in Line (400 点)

期待値の線形性!!! 問題へのリンク 問題概要 個のサイコロが左から右に一列に並べてある。 番目のサイコロは目が となっていて、これらが当確率に出る。 隣接する 個のサイコロを選んでそれぞれ独立に振ったとき、出る目の合計の期待値の最大値を求めよ。…

AtCoder ARC 074 C - Chocolate Bar (400 点)

最適解の形を丁寧に場合分けして考える系 問題へのリンク 問題概要 の板チョコレートを 3 つの長方形に割りたい。そのときの 3 つの長方形の面積の最大値と最小値の差の最小値を求めよ。 制約 考えたこと まず思ったのは、 のうちの少なくとも一方が 3 の倍…