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

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

AtCoder

AtCoder ARC 007 D - 破れた宿題

一瞬激ヤバに見えるし、コーナーケースの数もえげつないけど、とりあえず最小の初項はすぐにわかると... 問題へのリンク 問題概要 等差数列があった。 等差数列を concat して得られる文字列から、先頭から何文字かと、末尾から何文字かを削除して得られた文…

キーエンス プログラミング コンテスト 2020 E - Bichromization (900 点)

実装に精彩を欠いてしまった...コンテスト中に WA を取りきれず... WA の原因は「すでに色を決めたはずの頂点について再度色を上書きしていることがある (現在見ている D 値について、それより小さい値の頂点とはつながっておらず、等しい D 値同士で結ばれ…

キーエンス プログラミング コンテスト 2020 D - Swap and Flip (700 点)

隣接 swap 操作を行いながら最小回数でソートする系の問題は、過去に何度も出てる!!! drken1215.hatenablog.com drken1215.hatenablog.com これらはいずれも自然に DP で解くことができる。今回も。なお、「どれを表にするかを決め打って転倒数を求める」…

キーエンス プログラミング コンテスト 2020 C - Subarray Sum (400 点)

結構ギャグ要素強めな問題だった 問題へのリンク 問題概要 3 つの整数 が与えられる。 長さ の整数列 であって、以下の条件を満たすものを構築せよ: を満たすような の組がちょうど 個ある 制約 考えたこと とりあえず一つ思うこととして、 は全部 1 以上な…

キーエンス プログラミング コンテスト 2020 B - Robot Arms (200 点)

区間スケジューリング問題そのものだった!!! ...とはいえ 200 点というのは衝撃!!! 問題へのリンク 問題概要 ある工場では、 数直線上に 個のロボットが設置されている。 ロボット は座標 に設置されていて、左右に長さ のアームを伸ばしている。 これ…

AtCoder ABC 151 C - Welcome to AtCoder (300 点)

間違わないように、正確に、シミュレーションする問題。 C、大好き!!!!!!「言われたことを正確にこなせるか」というシミュレーション問題なんだけど、題材が面白い上に、配列か連想配列で情報を管理することを要求したり、少し注意力も要求する感じが…

AtCoder ABC 151 D - Maze Master (400 点)

面白かった。BFS したり、Warshall--Floyd したり。 問題へのリンク 問題概要 の盤面が与えられる。各マスは '.' か '#' のいずれかである。それぞれ「通路」と「壁」を表している。 「通路を 2 箇所 指定したときの、上下左右に通路のみをたどって から へ…

AtCoder ABC 151 F - Enclose All (600 点)

幾何だ!!!!! そして、こういうので「ギリギリを考える」というのは典型な感じ。 なお、僕は最小包含円のことを知らず、アドホックに解いたけど、ライブラリ貼るだけだったらしい... (その方が計算量も少ない) 他にも、三分探索でも解ける!!! 問題へ…

AtCoder ABC 151 E - Max-Min Sums (500 点)

こういう系の「個別要素に分解して考える」という問題が三連発だ!!!!! これもあれも! drken1215.hatenablog.com drken1215.hatenablog.com 問題へのリンク 問題概要 個の整数 が与えられる。これらから 個を選ぶ 通りの方法についての 「選んだ 個の整…

AtCoder ABC 150 E - Change a Little Bit (500 点)

面白かった 問題へのリンク 問題概要 長さ の整数列 が与えられる。 長さ の 0 と 1 からなる文字列 に対して定まる関数 は次のようになっている。 は、次のようにして文字列 を文字列 に一致させるのに必要な最小コストとする。 回目の操作で、 の文字 を選…

AtCoder ABC 150 D - Semi Common Multiple (400 点)

面白かった!!! 「2 で何回割れるのか」に着目するのはあるあるだけど、400 点としては難しめな感じかな。 問題へのリンク 問題概要 個の正の整数 と整数 が与えられる。以下の条件を満たす整数 が何個あるか求めよ。 任意の に対して、ある 0 以上の整数 …

AtCoder ABC 150 C - Count Order (300 点)

next_permutation の練習になりそう。DFS でも。 問題へのリンク 問題概要 の順列 が与えられます。 が の順列のうち辞書順で何番目か が の順列のうち辞書順で何番目か を求め、それらの差を答えよ。 制約 考えたこと 制約が小さいので、 通りの順列をすべ…

AtCoder ABC 150 F - Xor Shift (600 点)

バチャやった。13 位相当で割とよかった。 ロリハした。 問題へのリンク 問題概要 長さ の整数列 , が与えられる。以下の条件を満たす 以上 以下の整数 と、整数 の組をすべて求めよ。 = が成立する 制約 考えたこと 整数列 を circular shift した上で、 と…

第6回 ドワンゴからの挑戦状 予選 B - Fusing Slimes (600 点)

期待値の線形性的な。 問題へのリンク 問題概要 体のスライムがそれぞれ の位置にいる (これらは単調増加)。 以下の 通りのスライム合体過程それぞれについて、スライムの移動距離の総和を考える。その総和距離の総和を求めよ。1000000007 で割ったあまりで…

第6回 ドワンゴからの挑戦状 予選 C - Cookie Distribution (800 点)

これ 81 人も通してるのか... 問題へのリンク 問題概要 人の子供がいる。 日間にわたって、 人の中から 人を一様ランダムに選んでクッキーを与える。 日分のあらゆるクッキーの配り方を考えたときの「各子供の最終的にもらったクッキーの個数の積」の総和を…

第6回 ドワンゴからの挑戦状 予選 D - Arrangement (800 点)

今回は惨敗したけど次回また頑張りたい!!! 問題へのリンク 問題概要 の順列であって、以下の条件を満たすもののうち、辞書順最小のものを求めよ。存在しない場合は -1 を出力せよ。 の右隣の値は ではない 制約 考えたこと 色々手を動かしてみると、条件…

第5回 ドワンゴからの挑戦状 予選 2018 E - Cyclic GCDs (1000 点)

バチャでは手が回らなかったけど、復習した。ちょっとこの多項式解法は今はよくわからないけど、覚えておこう... 問題へのリンク 問題概要 要素の数列 が与えられる。 の順列 に対して、それを巡回群の直積として表したときの、各巡回群に含まれる要素に対応…

第5回 ドワンゴからの挑戦状 予選 2018 D - Square Rotation (800 点)

すごく詰め切るのに時間かかった 問題へのリンク 問題概要 (意訳) 二次元平面上に 個の座標 (格子点) が与えられる。正の整数 が与えられる。 まず、各座標について「 座標を だけ増減する」「 座標を だけ増減する」という操作を好きなだけ繰り返す。ただし…

第5回 ドワンゴからの挑戦状 予選 2018 C - k-DMC (600 点)

差分更新系の代表的問題。でも頭がごっちゃになって大変だった。 問題へのリンク 問題概要 'D', 'M', 'C' からなる長さ の文字列 と正の整数 が与えられる。 の添字 であって S[ ] = 'D' S[ ] = 'M' S[ ] = 'C' を満たすものの個数を求めよ (というクエリに …

第5回 ドワンゴからの挑戦状 予選 2018 B - Sum AND Subarrays (400 点)

最初、罠に引っかかった 問題へのリンク 問題概要 長さ の数列 が与えられる。これらの連続する区間の総和を書き出していく ( 個ある)。 これらの中から 個選んで AND をとった値として考えられる最大値を求めよ。 制約 嘘貪欲 とりあえず なので、 個の整数…

AtCoder ABC 146 C - Buy an Integer (300 点)

二分探索の教育的問題ですね! 問題へのリンク 問題概要 正の整数 が与えられる。正の整数 に対して を の桁数とする。このとき を満たす最大の正の整数 を求めよ。 制約 考えたこと わけわからない式だし、二分探索に決まってるやろ!!!という雰囲気があ…

AtCoder ABC 149 C - Next Prime (300 点)

C 問題で整数系のアルゴリズムを確認する問題を出すの良さそうやね。 問題へのリンク 問題概要 2 以上の整数 が与えられる。 以上の最小の素数を求めよ。 制約 素数判定 整数 が素数かどうかを判定するのは、整数論的アルゴリズムで最初くらいに学ぶものです…

AtCoder ARC 097 F - Monochrome Cat (800 点)

とにかく重たい... 問題へのリンク 問題概要 頂点のツリーが与えられる。各頂点には「白」か「黒」の色が塗られている。好きな頂点から開始して 今いる頂点の色を flip する 隣接する頂点を 1 つ選んで移動して、その頂点の色を flip する といういずれかの…

ARC 059 F - バイナリハック / Unhappy Hacking (800 点)

面白かった 問題へのリンク 問題概要 長さ の '0' と '1' と 'B' からなる文字列 として、以下の条件を満たすものが何通りあるか、1000000007 で割ったあまりを求めよ。 空文字列に対し、 を左から順に見て、以下の操作を順に行ってえられる文字列が に一致…

Xmas Contest 2019 J - Sub-Post Correspondence Problem

信じる心が大切ですね 問題へのリンク 問題概要 組の文字列 が与えられる。 これらの組を好きな順序で好きな回数だけ選んで、 側と 側とをそれぞれ連結した文字列 ができる。 このとき、 が の部分文字列 (連続でなくてよい) とすることができるかどうかを判…

AtCoder AGC 023 A - Zero-Sum Ranges (200 点)

200 点問題で最も難しい問題として名高い問題ですね。 これについては、以下の「累積和」について特集した記事で詳しく解説しました! qiita.com

AtCoder ARC 099 F - Eating Symbols Hard (1200 点)

楽しかった。こういうのでロリハ使うの楽しい。発想自体は Zero-Sum Ranges (200 点) と似てる。 問題へのリンク 問題概要 高橋君は、いつも頭の中に長さ 2000000001 の数列 と、整数値 を思い浮かべている。初期状態では、数列の各要素値と、 の値はすべて …

AtCoder ABC 148 E - Double Factorial (500 点)

じゅぴろ君が「これは中受典型」と言いそうな雰囲気がありますね。 問題へのリンク 問題概要 以上の整数 が与えられる。 を計算した値において、末尾に何個の 0 がつくのかを求めよ。 制約 考えたこと これとよく似た形で、たとえば の末尾に 0 が何個つくか…

AtCoder ABC 148 D - Brick Break (400 点)

とても教育的な Greedy かもしれない! 問題へのリンク 問題概要 長さ の正の整数からなる数列 が与えられる。この数列からいくつかの値を取り除くことで、数列が となるようにしたい。 取り除くべき個数の最小値を求めよ。どのように取り除いても の形にで…

AtCoder ABC 148 C - Snack (300 点)

結構、そのまんまな問題が来ましたね。 問題へのリンク 問題概要 2 つの正の整数 が与えられる。 でも でも割り切れる正の整数のうち、最小の値を求めよ。 制約 考えたこと すごくそのまんまですね。 と の最小公倍数を求めよ、という問題。実は と の最大公…