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

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

ソート

AtCoder AGC 001 A - BBQ Easy (200 点)

伝説の始まり 問題へのリンク 問題概要 個の整数 が与えられる。これらを 個ずつ 組作り、各組についての「小さい方の値」の総和を最大にしたい。 制約 考えたこと 小さすぎる値と大きすぎる値とを組合せてしまうと、大きい値が小さい値に吸収されてしまって…

CS Academy FII Code #1 E - Sugarel’s Garden

にはできたけど、 にできなかった。 問題へのリンク 問題概要 二次元平面上に 点が与えられる。 点から 4 点を選んでできる四角形のうち、内部にちょうど 個の点をもつものすべてを考えたとき、その面積の最小値を求めよ。 制約 どの 3 点も同一直線上にはな…

JOI 2019 本選 B - 展覧会 (AOJ 0659)

Greedy を信じよう...じゃなくて、証明しよう! 問題へのリンク 問題概要 枚の絵画があって、それぞれ大きさは 、価値は で与えられる。 個の額があって、それぞれ大きさが で与えられる。 絵画と額とをマッチングさせる。ここで、以下の条件を満たすような…

AtCoder ABC 117 C - Streamline (300 点)

ソートする問題。 問題へのリンク 問題概要 個のコマを数直線上に配置して、それぞれ移動させる。それによって、 個の地点 をすべて訪れるようにしたい。総移動距離の最小値を求めよ。 制約 考えたこと とりあえず、各コマについて、「行って、引き返して」…

キーエンス プログラミング コンテスト 2019 C - Exam and Wizard (400 点)

好き!!! 問題へのリンク 問題概要 長さ の 2 つの数列 と が与えられる。 数列 であって 任意の に対して、 を満たすものを考えたときの、 となる の個数の最小値を求めよ。 制約 考えたこと をなるべく変形箇所を少なくしつつ に変形して、 にオール勝ち…

AOJ 1391 Emergency Evacuation (ICPC アジア 2018 C)

結構好き!ソートすることが本質の問題としていい感じな気がする。 問題へのリンク 問題概要 下図のような「中央の通路とそこから横に伸びた乗り物に乗客がどこにいるかを表した地図」が与えられる。乗客は 人いる。各乗客は 1 秒かけて 1 マス移動できる。…

Tenka1 2018 C - Align (400 点)

今週のお題「わたしとバレンタインデー」 提出するまでが怖かった 問題へのリンク 問題概要 整数が N 個与えられます。 i 個目の整数は Ai です。 これらを好きな順に一列に並べるとき、隣り合う要素の差の合計の最大値を求めてください。 考えたこと うおっ…

AtCoder ARC 101 C - Candles (300 点)

問題概要 (ARC 101 C) N 本のろうそくが一直線上に並んでいる。最初は原点にいて、N 本のうち K 本のろうそくに火をつけたい。ろうそくと同じ座標に到達すると火をつけることができる。火をつけるのに要する時間は 0 秒である。移動距離を最小化せよ。 解法 …

AtCoder AGC 013 C - Ants on a Circle (700 点)

蟻さんぐるぐるなのん 問題へのリンク 問題概要 (AGC 013 C) 長さ の円周上を 匹の蟻が動く。どの蟻も 1 秒間に 1 だけ動く。互いに反対方向に動いている 2 匹の蟻がぶつかったら、互いに向きを反転させて動く。 匹の蟻は最初 の地点にいた。どの蟻が最初に…

AtCoder ABC 100 D - Patisserie ABC (400 点)

ABC 100 D - Patisserie ABC 問題概要 整数 3 つ組 (xi, yi, zi) が N 個与えられる。 このうちの M 個選んで、 (x の選んだ M 個の総和の絶対値) + (y の選んだ M 個の総和の絶対値) + (z の選んだ M 個の総和の絶対値) が最大になるようにせよ。 制約 1 <=…

2016 Benelux Algorithm Programming Contest L - Sticky Situation (AtCoder 300 点くらい)

バチャやりました! vjudge.net L 問題ですが、一番易しい問題です。 問題へのリンク 問題概要 N 個の値 a_1, a_2, ..., a_N が与えられる。 このうちの 3 つをうまく選ぶことで、3 辺の長さがそれらになるような三角形を作ることができるかどうか判定せよ。…