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

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

コーナーケース

AtCoder ABC 184 C - Super Ryuma (茶色, 300 点)

これ難しいと思った! あと、どうやら (1, 1, 1, 6) を 3 回にする嘘解法が AC になったらしい 問題へのリンク 問題概要 以下の動きのできる駒がある。駒をマス からマス へ移動させるのに必要な手数の最小値を求めよ。 制約 考えたこと まず、スタートとゴ…

AtCoder AGC 049 C - Robots (黄色, 800 点)

11 WA の末に通した... 問題へのリンク 問題概要 初期状態では、数直線上の座標 の位置にロボット がいる。 一方、たくさんのボールがある。ボールの情報は長さ の整数列 と で表される。具体的には、各 について、 の書かれたボールが 個ある。 今からすぬ…

AtCoder AGC 048 C - Penguin Skating (黄色, 700 点)

想定解法とちょっと違うやり方したっぽい 問題へのリンク editorial 問題概要 個のマスが横一列に並んでいる ()。 匹のペンギンがマス にいる。 あなたは,次の操作を好きな回数行うことができる。 ペンギンを 1 匹選び、左または右へ向かって滑らせる ペン…

AtCoder AGC 041 A - Table Tennis Training (灰色, 300 点)

若干注意力ゲーだった。端で折り返してこれることに注意。 問題へのリンク 問題概要 正の整数 が与えられる。2 つの整数 に対して毎回以下のような操作を行う。2 つの整数が一致させられるまでの最小回数を求めよ。 整数 が でも でもないとき、 と のいずれ…

AtCoder AGC 037 A - Dividing a String (灰色, 300 点)

意外とすぐにわからなかったんやけど... 問題へのリンク 問題概要 英小文字からなる文字列 が与えられる。以下の条件をみたす最大の正整数 を求めよ。 を空でない 個の文字列へと分割したとき、連続する文字列は相異なる 制約 Greedy は嘘 パッと思い浮かぶ …

AtCoder AGC 034 A - Kenken Race (茶色, 400 点)

場合分けやコーナーケース回避がエグい問題! 問題へのリンク 問題概要 .#..#.. のような長さ のマス目が与えられる。"#" は岩を表す。初期状態では、すぬけ君は マス目に、ふぬけ君は マス目にいる ()。 今、「2 人のうちのいずれかを選んで 1 マス右か 2 …

AOJ 2295 Power of Power (JAG 夏合宿 2011 day2-F) (550 点)

コーナーケースがエグい 問題へのリンク editorial 問題概要 個の非負整数 が与えられる。これらの並び替え であって が最大となるものを求めよ。複数通り考えられる場合には辞書順最小のものを答えよ。ただし、 とする。 制約 考えたこと エグい場合分けが…

Codeforces Round #681 (Div. 1) C. Graph Transpositions (R2400)

AOJ-ICPC みを感じる! 問題へのリンク 問題概要 頂点数 、辺数 の有向グラフが与えられる。頂点 1 から頂点 へとたどり着きたい。以下の 2 種類の操作ができる。 頂点 上にいるとき、辺 をたどって、頂点 へと移動する 移動に要するコストは 1 任意の頂点に…

AOJ 2629 Manhattan (JAG 夏合宿 2014 day2-A) (250 点)

伝説のりんごさんセットの 1 問目 問題へのリンク 問題概要 二次元座標平面上において、 座標と 座標のうちの少なくとも一方が整数であるような点からなる集合を「道路」と呼ぶ。 道路上の 2 点 のユークリッド距離が実数 で与えられる。 点 から道路のみを…

CPSCO2019 Session4 E - ox Concatenation (600 点設定)

これすごく好き!!!普通に難しい。 問題へのリンク 問題概要 'o' と 'x' のみからなる長さ の文字列 を作りたい。部品として使えるのは以下のものたち ( となっている)。 "ox" が 個 "xo" が 個 "o" が 個 "x" が 個 これらを適切な順序で concat すること…

CPSCO2019 Session3 G - Grand Election (800 点設定)

資源配分問題とも言われるタイプの問題。均等配分からの摂動で良さそう (嘘解法) だと騙すことを狙った! 問題へのリンク 問題概要 個の正の整数 (総和を とする) が与えられたとき、 が最小値となる を満たすような非負整数の組 を求めよ。複数通り考えられ…

AtCoder ARC 106 C - Solutions (水色, 500 点)

面白かった 問題へのリンク 問題概要 以下の条件を満たすような 個の区間 ( 番目を とする) を構築したい。 はすべて互いに相異なる整数 これらの区間の中から「どの 2 個も交差しないように最大で何個の区間を選べるか」という問題に対して、高橋君と青木君…

AOJ 2904 GuruGuru (JAG 夏合宿 2018 day3-A) (200 点)

英文だし、題意をちゃんと読み解くのがちょっと大変 問題へのリンク editorial 問題概要 L と R のみから構成された文字列 が与えられる。ロボットは最初北方向を向いている。文字列 を左から順番に読んで次のように処理していく。 L のとき、ロボットは 90 …

yukicoder No.321 (P,Q)-サンタと街の子供たち

kirika さんの「整数論テクニック集」より。 問題へのリンク 問題概要 二次元平面平面上において から の合計 8 方向に移動できる。今、 個のクエリが与えられる。各クエリは座標 が与えられる。原点から出発して、上述の移動を好きな順序で好きな回数だけ繰…

AtCoder ARC 104 C - Fair Elevator (黄色, 600 点)

コーナーケースがえぐい!! 僕は最初、(1, -1), (-1, 3) で Yes を返してしまっていた。 問題へのリンク 問題概要 個の区間 があって、 両端の座標は のいずれか 両端の座標をかき集めたとき、重複がない 区間 と区間 がもし重なっているならば、区間 の長…

AOJ 3167 Many Points (HUPC 2020 day1-D)

面白かった! 問題へのリンク editorial 問題概要 次の問題が ケース分与えられる。 二次元平面上に 個の格子点が与えられる。これらに対し、以下の条件を満たす直線 が存在するかどうかを判定せよ。 どの点に対しても、 との距離が等しい 制約 考えたこと …

AOJ 3177 Painting (HUPC 2020 day3-F)

こういうの楽しいよね! 問題へのリンク 問題概要 個のマスが横一列に並んでいます。各マスは赤、青、黄、緑のいずれか 1 色で塗られている ("RBYG" からなる長さ の文字列 で与えられる)。 以下の操作を好きな順序で好きな回数だけ行えます。文字列 を作る…

AOJ 3183 Flipping a Path (HUPC 2020 day3-L)

こういう系すごく楽しいよね 問題へのリンク 問題概要 頂点数 、辺数 の重み付き有向単純グラフ が与えられる。 このグラフ上で次の条件を満たすパス (同じ頂点を二度通らないものに限る) が存在するかどうかを判定し、そのようなパスの重みの最小値を求めよ…

AtCoder ABC 175 C - Walking Takahashi (茶色, 300 点)

ちょっと場合分けが怖い問題だけど、最後の動きは「ちょうどゴールにならないと、上がれないすごろく」を思い出すと納得できそう! 問題へのリンク 問題概要 現在、座標 にいる。以下のいずれかの操作をちょうど 回行う。 座標 にいるとき、 に移動する 座標…

AtCoder ABC 175 D - Moving Piece (水色, 400 点)

異様に難しかった!! 問題へのリンク 問題概要 の順列が与えられる。 順列の中の i から P[ i ] へ移動するとき、C[ P[ i ] ] だけスコアが加算される。 出発点を自由に選んで 回以上 回以下の移動を行うとき、得られるスコアの最大値を求めよ。 制約 考え…

AtCoder ARC 094 F - Normalization (赤色, 700 点)

これ系、この問題以降はたくさん見るようになったけど、この問題が先駆けとなった気がする 問題へのリンク 問題概要 'a', 'b', 'c' のみからなる長さ の文字列 が与えられる。 に以下の操作を好きな順序で好きな回数だけ行って得られる文字列が何通りあるか…

AtCoder ABC 169 C - Multiplication 3 (茶色, 300 点)

誤差は怖い!!!!!!! 問題へのリンク 問題概要 整数 と、"x.yz" のフォーマットで与えられる実数 が与えられる。 の小数点以下を切り捨て、結果を整数として出力せよ。 制約 考えたこと 数値誤差が怖いというテーマの問題は、パナソニックコンでもあっ…

AtCoder AGC 017 A - Biscuits (緑色, 200 点)

これ、知らなくても解ける制約設定だけど、結構大変やね 問題へのリンク 問題概要 個の正の整数 が与えられる。これらからいくつか選ぶ方法のうち、総和を 2 で割ったあまりが となる方法が何通りあるかを求めよ。 制約 考えたこと 一般に 総和が奇数 ⇔ 和の…

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

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

AtCoder Petrozavodsk Contest 001 D - Forest (青色, 600 点)

面白かった 問題へのリンク 問題概要 頂点 辺の森が与えられる。各頂点 には、値 が付いている。これにいくつかの辺を追加して、連結にしたい。 頂点 と頂点 とを結ぶのに必要なコストは である すでに辺がある二頂点間は結べない 一度辺を張るのに使用した…

AtCoder ABC 158 E - Divisible Substring (青色, 500 点)

こういう問題を求めてた!! 問題へのリンク 類題として、こんなのがある。 drken1215.hatenablog.com 問題概要 長さ の、各文字が '0'〜'9' のいずれかとなっている文字列 と、素数 が与えられる。 の空でない連続する区間であって、その整数が で割り切れ…

AtCoder AGC 003 B - Simplified mahjong (水色, 400 点)

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

第6回 ドワンゴからの挑戦状 本選 2020 A - 2525敷き詰め (500 点)

面白かったけど、実際に実装するのは辛かった。 問題へのリンク 問題概要 のグリッドが与えられる。各マスを 2 または 5 で埋めたい。ただし以下の条件を満たすようにしたい。 2 が書かれたマスだけに着目し、上下左右斜め に隣接するマス同士に辺を張ったグ…

AtCoder ABC 153 C - Fennec vs Monster (灰色, 300 点)

な場合に注意。。。 問題へのリンク 問題概要 個の正の整数 が与えられる。以下の操作を 回まで行うことができる: 整数を 1 つ選んで、0 にする 操作を行った後の、整数の総和として考えられる最小値を求めよ。 制約 考えたこと 素朴に考えれば、 が大きい順…

AtCoder ARC 007 D - 破れた宿題 (橙色)

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