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

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

最大値や最小値に着目する

AtCoder ABC 208 A - Rolling Dice (灰色, 100 点)

「この数からこの数の間の数はすべて作れる」という考え方をする問題。この考え方は、より高度な問題では頻出! 問題へのリンク 問題概要 1〜6 の目が出るサイコロを 回振った。 出た目の総和が になることがありうるかどうかを判定せよ。 解法 これは難しい…

AtCoder ABC 207 A - Repression (灰色, 100 点)

頭を柔らかくして考えよう。 問題へのリンク 問題概要 3 個の整数 から 2 個選んで和をとる。 この和の最大値を求めよ。 解法 3 個の整数 から 2 個選んだ和は の 3 通りがある。これらの最大値を求めればよい。 #include <bits/stdc++.h> using namespace std; int main() </bits/stdc++.h>…

AtCoder ABC 129 A - Airplane (灰色, 100 点)

この頃によくあった 3 個の入力をどうのこうのする系! 問題へのリンク 問題概要 3 つの空港 A, B, C がある。 A-B 間の移動の所要時間は B-C 間の移動の所要時間は A-C 間の移動の所要時間は 今、これらの空港を順に訪れる (たとえば、B → A → C)。最短の所…

AtCoder ABC 123 A - Five Antennas (灰色, 100 点)

ちょっと数学的な部分が難しい問題かもしれない。 問題へのリンク 問題概要 5 つのアンテナがこの順に一直線上に並んでいて、それぞれ座標値は () である。 2 つのアンテナは、距離が 以内であるとき、通信できる。 これらのアンテナの組であって、通信でき…

AtCoder ABC 047 A - キャンディーと2人の子供 (灰色, 100 点)

これも「まずソートして考える」が効く系。でも、そうしなくても解ける。 問題へのリンク 問題概要 3 つの正の整数 が与えられる。 これらを 2 つのグループに分けて、各グループの数値の総和が等しくなるようにできるかどうかを判定せよ。 解法 (1):場合分…

AtCoder ABC 313 A - To Be Saikyo (灰色, 100 点)

トップタイがある場合に注意! 問題へのリンク 問題概要 (0 始まりに表現改) 人の人 がいる。人 のプログラミング力は である。 人 は必要に応じてプログラミング力を鍛えることで、 人の中で単独トップになろうとしている。 そのためにプログラミング力をい…

AtCoder ABC 311 G - One More Grid Task (黄色, 575 点)

黒マスを避けながら、長方形領域の値の総和を最大化する問題として解いた! 問題へのリンク 問題概要 のグリッドがあって、各マス には正の整数 が書かれている。 グリッドに含まれる長方形領域のうち、「長方形領域に含まれる値の総和」と「長方形領域に含…

JOI 二次予選 2023 A - 年齢の差 (AOJ 0747, 難易度 3)

シンプルながらも、学べるポイントがたくさんある問題ですね 問題へのリンク 公式解説へのリンク 問題概要 JOI 市には から までの番号が付けられた 人の住民がいて、住民 () の年齢は 歳です。 JOI 市の住民の年齢 ​ が与えられます。 に対して、住民 と他…

AtCoder ABC 281 G - Farthest City (黄色, 600 点)

残り 1 分でなんとか通せた。 問題へのリンク 問題概要 頂点数 の連結な単純無向グラフ (頂点番号は であって、次の条件を満たすものの個数を で割ったあまりを求めよ。 なお、ここで、頂点 から各頂点 までの最短距離を としている。 制約 考えたこと グラ…

AtCoder ABC 280 G - Do Use Hexagon Grid 2 (赤色, 600 点)

ハニカムにそんな性質があるなんて!!! 45 度回転する技術のアナロジーが炸裂する。 あと、x 座標が最小となる点で場合分けする際に、同一の x 座標を持つものに対してダブルカウントを除去する工夫が大変だった。 問題へのリンク 問題概要 2 次元平面上に…

AtCoder ABC 091 C - 2D Plane 2N Point (ARC 092 C) (水色, 400 点)

とても教育的かつ典型的な貪欲法の問題ですね。 問題へのリンク 問題概要 二次元平面上に、赤い点と青い点が 個ずつあります。 個目の赤い点の座標は であり、 個目の青い点の座標は です。 赤い点と青い点は、 座標と 座標がともに赤い点よりも青い点の方が…

AtCoder ARC 115 B - Plus Matrix (茶色, 400 点)

「決めてから、整合性を確認する」というタイプの問題の典型例ですね! 問題へのリンク 問題概要 の非負整数を成分とする行列 が与えられる。 すべての について を満たすような非負整数列 と の組が存在するか判定し、存在するなら一つ出力せよ。 制約 考え…

Codeforces Global Round 12 D. Rating Compression (R1800)

頑張った 問題へのリンク 問題概要 正の整数のみからなる長さ の数列 が与えられる。各 に対して、以下の問に答えよ。 数列 を左から順に「連続する 個の最小値」をとっていってできる長さ の数列が、 の順列になっているかどうかを判定せよ。 制約 の総和 …

AtCoder ARC 110 C - Exoswap (緑色, 500 点)

「転倒数 = N-1 で Yes とする」という嘘解法が大量に通ったらしい 問題へのリンク 問題概要 の順列 が与えられる。 と を swap する と を swap する ... と を swap する という 種類の操作を、それぞれちょうど 1 回ずつ行う必要がある。その結果がソート…

AtCoder AGC 005 C - Tree Restoring (青色, 700 点)

面白かった! 問題へのリンク 問題概要 頂点数が の木であって、各頂点 から最も遠い頂点への距離がそれぞれ であるような木が存在するかどうかを判定せよ。 制約 考えたこと 面白そう!!!!!!似た見た目の問題としては、次の問題もあった。 drken1215.h…

AtCoder ABC 163 E - Active Infants (黄色, 500 点)

探索順序を上手に決めると、普通の DP になる系!!! EDPC の Zubton なんかもそうやね! 問題へのリンク 問題概要 個の正の整数 が与えられる。これらを並び替える。並び替えのスコアは以下のようにして決まる。 各 に対して、 の index が に移動するとき…

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

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

AtCoder AGC 043 D - Merge Triplets (橙色, 1200 点)

めちゃくちゃ楽しかった 問題へのリンク 問題概要 長さ の数列を 個用意する。ただしこれらのなす 個の値は が 1 個ずつ登場するようにする。これらの数列から以下の操作を繰り返して、長さ の順列を作る。 空にならずに残っている数列のうち、先頭の要素の…

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

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

AtCoder ARC 103 F - Distance Sums (赤色, 900 点)

900 点なので備忘録程度に... 久しぶりに競プロでめちゃくちゃ楽しかった!!! 2 時間 10 分かかったので本番だったら通せていないけど、どうすればもっと早く解けたのかの反省もこめて。 問題へのリンク 問題概要 以下の条件を満たす 頂点の木を復元せよ。…

AtCoder ABC 142 F - Pure (青色, 600 点)

色んな方法がありそう。 問題へのリンク 問題概要 頂点数 、辺数 の単純な有向グラフが与えられる。なお各有向辺の向きをなくして得られる無向グラフも単純であるとする (有向辺 (u, v) があったら辺 (v, u) はない)。 このグラフの有向サイクルであって、有…

Codeforces Round #584 (Div. 1 + Div. 2) A. Paint the Numbers (R900)

誤読して大きく出遅れた... 問題へのリンク 問題概要 個の整数 があたえられる。これを何個かのグループに分けて、各グループについて「グループ内のすべての整数がグループ内の最小値で割り切れる」という条件を満たすようにしたい。 これを実現するための…

AtCoder ABC 131 D - Megalomania (茶色, 400 点)

いわゆる、「必要条件を列挙したら十分条件になっている」というタイプの教育的な Greedy 問題ですね。 問題へのリンク 問題概要 個の仕事があって、仕事 は、 の時間を要し、時刻 までに終わらなければならない。 時刻 0 に仕事を開始する。 個の仕事をすべ…

Codeforces Global Round 2 E - Pavel and Triangles (R1900)

こういう貪欲は確実に抑えて行きたい 問題へのリンク 問題概要 長さが の線分がそれぞれ 本ずつある。 これらから三角形は最大で何個作れるか? 制約 考えたこと 面白そう!!!!! な量を扱う問題リストにまた 1 問加えられる!!!!! この手の問題では…

AtCoder ABC 123 C - Five Transportations (茶色, 300 点)

結構難しい... 問題へのリンク 問題概要 人全員が最初都市 1 にいて、全員を都市 1 -> 2 -> 3 -> 4 -> 5 -> 6 へと順番に進んで、全員が都市 6 にいる状態にしたい。 都市 1 から都市 2 への移動手段は毎秒ごとに提供されているが、同時に 人しか行けない。…

AtCoder AGC 010 B - Boxes (青色, 500 点)

状況がゴチャゴチャとして来て、整理するのが大変だった 問題へのリンク 問題概要 個のマスがあって最初は全マスに が書かれている。これに以下の操作を好きな回数だけ好きな順序で行って数列 にできるかどうか判定せよ。 を巡回させてできるものを足す 制約…

キーエンス プログラミング コンテスト 2019 E - Connecting Cities (橙色, 600 点)

めちゃいっぱい解法あってすごい!!!!!!!MST への理解が問われる。 いずれ復習をやり切ってちゃんとしたいが取り急ぎ、分割統治法 Kruskal と、想定解法のみ。 問題へのリンク 問題概要 頂点からなるパスグラフと整数 が与えられる。各頂点には重み が…

AtCoder ARC 098 E - Range Minimum Queries (青色, 600 点)

ARC 098 E Range Minimum Queries 問題概要 長さ N の数列 A と整数 K が与えられる。 この配列に、以下の操作を Q 回行います。 長さ K の連続する部分列を 1 つ選ぶ。 そして、選んだ部分列に含まれる K 個の要素のうち最小のもの(複数ある場合はその中で…