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

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

解を変形していく(最適性を失わずに)

diverta 2019_2 D - Squirrel Merchant (600 点)

操作が複雑な順序性をもつ問題だけど、こういうのは「操作の流れを単純化して、こういうものだけ考えればよい」という考察を狙うのが常だとは思う。 問題へのリンク 問題概要 問題画像そのままを 解法 1: 自分のやつ 僕が最初に考えたことは、例えば 「最初…

AtCoder ABC 128 D - equeue (400 点)

こういう全探索が意外と出てこないという意見はよく聞くよね。 同時に「複数種類の操作を行える問題では、操作の流れを単純化する」という典型思考を試す問題でもある。 問題へのリンク 問題概要 あなたは誕生日プレゼントとして友人から dequeue D を貰いま…

AtCoder AGC 007 D - Shik and Game (1200 点)

すごく典型的な問題。 現代なら企業コンの 800 点問題とかに出そうな雰囲気だね。このころはまだあまり典型じゃなかったのかな。 問題へのリンク 問題概要 一直線上に 個の点 があってこの順に並んでいる。さらに左側に 、右側に がある。 からスタートする …

AtCoder AGC 008 C - Tetromino Tiling (600 点)

ペアリングを頑張る問題として高難易度なすごく楽しい問題。 結構注意力がいる。割とやばいケースがある。 問題へのリンク 問題概要 下記のテトロミノの個数がそれぞれあたえられる。これらを回転は OK で反転は NG で組み合わせて の長方形を作りたい。作れ…

AtCoder ABC 116 D - Various Sushi (400 点)

学び多き問題。 僕にとっては後半のデータ構造パートが苦戦を強いられ、本当に勉強になった! 問題へのリンク 問題概要 個の寿司があって、それぞれネタ と美味しさ をもっている。この中から 個の寿司を選びたい。選んだ寿司集合のスコアは 選んだ寿司の美…

AtCoder AGC 032 E - Modulo Pairing (1200 点)

楽しかった。7 時間かかったけど自力 AC できたー! 問題へのリンク 問題概要 正の整数 が与えられる。 個の 以上 未満の整数 を 個ずつのペアに分けたい。 各ペア に対して % の値 (これを醜さと呼ぶ) を求め、その最大値をとる。 この最大値の最小値を求め…

AtCoder ABC 124 D - Handstand (400 点)

これ...以前 Twitter につぶやいた問題とよく似てた!!! 400 点くらいの問題【問題】N 要素の 0 と 1 から成る数列が与えられる。以下の操作を最大 K 回行なって錬成し得る数列が何通りあるか 10e9 で割った余りを求めよ「数列の連続する区間を選んで 0 と…

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

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

AOJ 3056 Equilateral Triangle (RUPC 2019 day2-F)

計算量的な詰めが甘かった。二分探索要らなかった。 問題へのリンク 問題概要 凸な 角形が与えられる。この 角形を完全に含むような正三角形の一辺の長さの最小値を求めよ。 制約 考えたこと 座標系として くらいの大きさまであるので、EPS は くらいがいい…

AtCoder ABC 120 C - Unification (300 点)

久しぶりのカッコ列の整合判定問題!!! カッコが binary になっただけ。ただし通常のカッコ列問題は )( みたいなやつはダメだけど、今回はこういうのも消せる (解法 1 へ)。 あるいは今回はカッコ列問題だと思わなくても、自然な考察で回答を導くこともで…

AtCoder ABC 119 D - Lazy Faith (400 点)

二分探索で lower_bound とかきっちり無意識的に使いこなせるようになりたいのんな!!! 問題へのリンク 問題概要 一次元の世界を考える。 A 個の神社と、B 個の寺が並んでいる (各神社と各寺の位置情報が 1 つの整数値で与えられる)。 以下の Q 個のクエリ…

AtCoder ABC 119 C - Synthetic Kadomatsu (300 点)

最近の AtCoder は ABC でも考察重視傾向が強くて、こういうのが見落とされがちかもなのん。。。 でも ABC を競プロ入門コンテンツと見たとき、この種の出題がもっと増えると良さそう!!!!! 大事なことを再認識させてくれる感じ。 問題へのリンク 問題概…

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

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

AtCoder ABC 117 C - Streamline (300 点)

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

AtCoder ARC 064 E - Cosmic Rays (600 点)

昔の AtCoder はこういうのもあったのか!!! 問題へのリンク 問題概要 二次元平面上に、 個の円がある。二次元平面上の点 から点 へと進むことを考える。秒速 1 だけ進む。 そのような方法のうち、円外の領域を進んでいる時間の最小値を求めよ。 制約 考え…

AOJ 1183 鎖中経路 (ICPC 国内予選 2012 E)

あまり良くない方針でゴリ押してしまった。でもゴリ押しで通せることの証左になるかと思って記録してみることに 問題へのリンク 問題概要 下図のような「円の列」の内部だけを通る折れ線 (最初の円の中心と、最後の円の中心とを結ぶ) の長さの最小値を求めよ…

AtCoder AGC 008 A - Simple Calculator (300 点)

もれなく正確に解くための考え方とかが問われる感じ。 問題へのリンク 問題概要 (AGC 008 A) 整数 が与えられる。 に以下のいずれかの操作を最小回数行って に一致させよ: を 1 増やす を にする 解法 最適解は 最初に反転する (かしないか) 「1 増やす」を…

AtCoder ARC 094 D - Worst Case (700 点)

最適性を失わずに解を変形していくことで、都合のいい解の形だけ考えればいいようにする系の問題。 問題へのリンク 問題概要 (ARC 094 D / ABC 093 D) 人の参加者が 2 回のプログラミングコンテストに参加しました。順位がつくのですが、同順位はないものと…

CS Academy 081 DIV2 D - Gerrymandering

貪欲でも、実家 DP でも、ソシャゲ DP 的な DP でも解けるみたいなのんな。これ、実装がややこしくて、苦手なんて言葉ではいい表せないほどの超絶苦手系なのん。。。 Gerrymandering 問題へのリンク 問題概要 N 個の街が一直線上に並んでいて、各街は 2 種類…

AtCoder AGC 025 C - Interval Game (700 点)

コンテスト本番における ウチのコード: https://beta.atcoder.jp/contests/agc025/submissions/2612210 tourist のコード: https://beta.atcoder.jp/contests/agc025/submissions/2609185 解けたとはいえ、反省点も多い感じですね。。。 AGC 025 C Interval …