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

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

AtCoder300点

AtCoder ABC 182 C - To 3 (灰色, 300 点)

これ灰色ってマジか!! 問題へのリンク 問題概要 どの桁の値も 0 でないような正の整数 が与えられる。 に含まれるいくつかの数値を除去することで、 が 3 の倍数となるようにしたい。 除去すべき数値の個数の最小値を求めよ (最初から 3 の倍数の場合は 0 …

AtCoder ARC 109 A - Hands (灰色, 300 点)

Dijkstra 法をしたけど、同じ殴りなら Warshall--Floyd 法にすればよかった。 問題へのリンク 問題概要 100 階建ての 2 つの建物 A, B がある。 A, B 内では 1 フロア上下するのに 秒を要する A の 階と B の 階とが廊下でつながっていて、移動に 秒を要する…

AtCoder ARC 108 A - Sum and Product (灰色, 300 点)

教育的な約数列挙問題!! 問題へのリンク 問題概要 2 つの正の整数 が与えられます。 を満たす正の整数 が存在するかどうかを判定せよ。 制約 考えたこと として、 の約数のみを考えれば OK。そして を決めると は と決まる。 となることがあるかどうかを判…

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

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

AtCoder AGC 048 A - atcoder < S (緑色, 300 点)

単純な探索でも解けるし、考察で計算量を減らすこともできそう。 問題へのリンク 問題概要 文字列 が与えられる。文字列 に以下の操作を最小回数行うことで、辞書順で > "atcoder" となるようにせよ。 中の連続する 2 文字を swap する (このテストケースが …

AtCoder ABC 183 C - Travel (灰色, 300 点)

C++ なら next_permutation() を使うことで 通りの全探索ができる! 問題へのリンク 問題概要 個の都市 がある。都市 と都市 とは距離が だけ離れている。 都市 から出発して各都市をちょうど一度ずつ訪問して都市 に戻ってくる方法のうち、その移動距離の総…

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

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

AtCoder AGC 040 A - >< (茶色, 300 点)

いかに上手に実装するか! 問題へのリンク 問題概要 長さ の ">" と "<" のみかななる文字列 が与えられる。 長さ の非負整数列 は, すべての について次の条件をみたすとき、良い非負整数列と呼ぶ。 = "<" のとき: = ">" のとき: 良い非負整数列の要素の…

AtCoder AGC 039 A - Connection and Disconnection (茶色, 300 点)

区間分割して考える系、AGC-A にめちゃくちゃ多いね 問題へのリンク 問題概要 文字列 が与えられる。 を 回繰り返してできる文字列を とする。 の文字をひとつ選んで他の文字に書き換える操作を繰り返すことで T のどの隣り合う 2 文字も相異なるようにする…

AtCoder AGC 038 A - 01 Matrix (緑色, 300 点)

これは天才パズル!!! 問題へのリンク 問題概要 のグリッドに 0, 1 の数値を書き込む方法であって、 どの行をみても、それに含まれる 0 の個数と 1 の個数のうちの小さい方の個数が どの列をみても、それに含まれる 0 の個数と 1 の個数のうちの小さい方の…

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

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

AtCoder AGC 035 A - XOR Circle (茶色, 300 点)

面白かった。でも茶色ってことは流石になさそう......(コンテスト中は、全部の XOR 和が 0 かどうかを判定する、という嘘解法が AC になっていたらしい) 問題へのリンク 問題概要 個の非負整数 が与えられる。これらを円環状に上手に並べることで、 「どの整…

AtCoder AGC 022 A - Diverse Word (茶色, 300 点)

ある程度探索でゴリ押した。 問題へのリンク 問題概要 英小文字のみからなり、どの 2 文字も互いに相異なる文字列を「多彩」であると呼ぶこととする。多彩な文字列 が与えられる。以下の条件を満たす文字列の中で最も辞書順が小さいものを求めよ。 よりも辞…

AtCoder AGC 024 A - Fairness (灰色, 300 点)

少し手を動かせば見えてくる! 問題へのリンク 問題概要 高橋君、中橋君、低橋君は、それぞれ整数 を持っている。 以下の操作を 回行った後の、高橋君の持っている整数から中橋君の持っている整数を引いた値を求めよ。ただし、答えの絶対値が を超える場合は…

AtCoder AGC 021 A - Digit Sum 2 (灰色, 300 点)

少し慎重に 問題へのリンク 問題概要 以下の正の整数の 10 進法での各桁の和の最大値を求めよ。 制約 考えたこと とかだったら答えは になりそうだ。一般に、 の形をしたものだけ考えれば良さそう。仮に とかが最適解だったとしても、その場合は として、 も…

AtCoder AGC 020 A - Move and Win (灰色, 300 点)

シンプルだけど、すごい好き 問題へのリンク editorial 問題概要 マス と区切られた マス上でゲームする。 Alice は最初マス に、Bob は最初マス にいる。交互に左右どちらかに動かす。ただし「マスの外」や「相手のいるマス」には動かせない。 先に動かせな…

AtCoder ABC 181 C - Collinearity (灰色, 300 点)

幾何っぽい問題。確かに数学ゲーではあるのだけど、平行判定は「計算幾何」の知見として習得してしまっても良さそう。 問題へのリンク 問題概要 二次元平面上に 個の点 () が与えられる。 これらのうちの 3 点であって、同一直線上にあるものが存在するかど…

AtCoder ARC 107 A - Simple Math (灰色, 300 点)

よくある式変形問題 問題へのリンク 問題概要 3 つの正の整数 が与えられる。 を 998244353 で割ったあまりを求めよ。 制約 考えたこと 求める値は に一致する。あとは modint を活用すれば求められる! コード #include <bits/stdc++.h> using namespace std; // modint te</bits/stdc++.h>…

AISing Programming Contest 2020 C - XYZ Triplets (灰色, 300 点)

ごとに考えるのではなく、集計する考え方をするのがポイント!!! 問題へのリンク 問題概要 正の整数 が与えられる。各 に対して、 は正の整数 を満たすような の組の個数を求めよ。 制約 考えたこと 最初に特定の整数 に対して は正の整数 を満たす の個数…

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

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

AtCoder ABC 180 C - Cream puff (灰色, 300 点)

完全に約数列挙!!!!! 問題へのリンク 問題概要 正の整数 が与えられる。 の正の約数をすべて出力せよ。 制約 考えたこと 約数列挙問題そのものだった!!!!! まったくそのまんまなものを次の記事の「3. 約数列挙」のところで書いた! qiita.com 計算…

CODE FESTIVAL 2016 Final B - Exactly N points (緑色, 300 点)

1, 2, ..., i のうちのいくつか選んで和を取った値は、連続した自然数を作れる 問題へのリンク 問題概要 からいくつか選んでできる総和が となるようにしたい。 選んだ数の最大値が最小となるような場合の数を求めよ。 制約 考えたこと 一般に、 によって作…

AtCoder ARC 105 B - MAX-=min (灰色, 300 点)

操作が「Euclid の互除法」っぽくなっている系の問題!!!そういう系の問題は次の一覧で示してる drken1215.hatenablog.com 問題へのリンク 問題概要 個の正の整数 に対して次の操作を繰り返し行う。 個の整数の最大値を 、最小値を とする。 なら手続きを…

HHKB プログラミングコンテスト 2020 C - Neq Min (灰色, 300 点)

mex!!!それにしても、ならし計算量解析系が来たのびっくり! 問題へのリンク 問題概要 長さ の数列 が与えられる。 各 に対して、0 以上の整数で のいずれとも等しくない値のうち最小値を求めよ。 制約 考えたこと とりあえず次のような配列を用意したく…

AtCoder ABC 177 C - Sum of product of pairs (灰色, 300 点)

茶色 diff にはなると思ったけど、灰色 diff だった...「/2」が必要と感じて詰まる人も多いと思ったのに... 問題へのリンク 問題概要 個の整数 が与えられる。 を満たすすべての に対しての の総和を 1000000007 で割ったあまりを求めよ。 制約 考えたこと …

AtCoder ABC 176 C - Step (灰色, 300 点)

Greedy の一番簡単なパターン 問題へのリンク 問題概要 人が 1 列に並んでおり、前から 番目の人の身長は です。 それぞれの人の足元に、高さが 0 以上の踏み台を設置し、全ての人が次の条件を満たすようにしたいです。 条件:踏み台を込めて身長を比較した…

AtCoder ABC 178 C - Ubiquity (茶色, 300 点)

包除原理!!!C 問題としては難しめですね。 問題へのリンク 問題概要 0 以上 9 以下の整数値からなる長さ の数列 であって、 数列中に 0 が含まれる 数列中に 9 が含まれる という条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 制約 考え…

ACL Beginner Contest C - Connect Cities (茶色, 300 点)

Union-Find の練習問題という雰囲気ながら、DFS や BFS でも解ける 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。これに最小本数の辺を追加することで全体が連結となるようにしたい。その最小本数を求めよ。 制約 考えたこと 全体…

ACL Contest 1 A - Reachable Towns (水色, 300 点)

えーーー、300 点!? 問題へのリンク 問題概要 二次元平面上に 点が与えられる。これらの点の x 座標、y 座標を抽出すると、それらは の順列となっている。 各 に対して、点 から 自分よりも x 座標と y 座標がともに大きな点 自分よりも x 座標と y 座標が…

AtCoder ABC 179 C - A x B + C (灰色, 300 点)

でもできる! 問題へのリンク 問題概要 正の整数 が与えられる。 を満たすような正の整数 の組の個数を求めよ。 制約 考えたこと こういう整数問題は、実のところ本当に整数論的考察を必要とするパターンは少なくて、大抵は探索ベースの解法が有効になる!!…