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

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

NoviSteps4D

AtCoder ARC 186 A - Underclued (4D, 橙色, 900 点)

久しぶりに高難易度問題を解いてみた! 問題へのリンク 問題概要 各マスの値が 0 または 1 である グリッドを考える。 グリッド のマス が「固定されている」とは、次の条件を満たすすべての グリッドについて、マス の値が一意に決まることをいう。 すべて…

AtCoder ABC 374 G - Only One Product Name (4D, 橙色, 600 点)

最初、頂点にアルファベット、辺に文字列を乗せたグラフを考えていたが、うまく解けなかった。 頂点に文字列を乗せて、しりとりが成立する箇所に辺を張ったグラフを考えるとうまくいった。 問題へのリンク 問題概要 英大文字 2 文字からなる 個の文字列 が与…

ゆるふわ競技プログラミングオンサイト at FORCIA #7 G - Dot Product Query (4D)

コンテスト中最初に挑んだが解けず、その後も結局解けなかった。gcd convolution を思い出せなかった。 問題へのリンク 問題概要 長さ の正の整数からなる数列 、 が与えられる。これらの数列に対して 個のクエリが与えられる。 【クエリ】 正の整数 が与え…

JOI 春合宿 2022 day2-3 チーム戦 (4D, 難易度 10)

面白かった! 問題へのリンク 問題概要 人がいて、人 の考察力、実装力、運はそれぞれ である。 これら から 3 人を選ぶ。ただし、3 人全員について「考察力・実装力・運のうちのいずれかについては他 2 人よりも真に高い」という条件を満たさなければならな…

AtCoder ABC 361 G - Go Territory (4D, ?色, 600 点)

方針を決めるのが大変な問題。 問題へのリンク 問題概要 二次元平面上の 個の格子点に碁石が置かれている。 このとき、碁石によって囲われている格子点の個数を求めよ。より正確には、「その空き格子点から上下左右の空き格子点への移動を繰り返して点 (-1, …

AtCoder ABC 354 G - Select Strings (4D, 橙色, 625 点)

Dilworth の定理から、DAG の最小パス被覆!! かつて流行った高度典型。 問題へのリンク 問題概要 個の文字列 が与えられる。各文字列には重み がついている。 これらの文字列から「どの 2 つの文字列も互いに他を部分文字列として含まない」という条件を満…

AtCoder ARC 176 D - Swap Permutation (4D, 橙色, 700 点)

行列累乗した。デバッグに手こずった。 問題へのリンク 問題概要 の順列 が与えられる。以下の操作を 回行う。 を選んで と を swap する 操作列は 通り考えられるが、それぞれについての の総和を 998244353 で割った余りを求めよ。 制約 考えたこと の期待…

AtCoder ABC 338 G - evall (4D, 橙色, 600 点)

人目見て「頑張れば解けそう」と思えたので、コンテスト中になんとか頑張って通した! 問題へのリンク 問題概要 "1+2*34" のような文字列が与えられる。 この文字列の連続する部分文字列をすべて考えて 数式として成立しているなら、その数式を計算した値 数…

AtCoder ABC 225 G - X (4D, 橙色, 600 点)

2 変数劣モジュラ関数の和の最小化! 俗にいう燃やす埋める 問題へのリンク 問題概要 のグリッドがあって、各マス には値 が記されている。 いくつかのマスに「x」を描いていく。「x」は書かれるマスの左上の角と右下の角を結ぶ線分、および右上の角と左下の…

AtCoder ABC 326 G - Unlock Achievement (4D, 橙色, 625 点)

2 変数劣モジュラ関数の和の最小化を最小カットにするやつ! 問題へのリンク 問題概要 種類のスキルがある。それぞれ初期状態のスキルレベルは 1 であるが、最大で 5 まで上げられる。スキル のスキルレベルを 1 上げるのに必要なコストは 円である。 種類の…

AtCoder ABC 320 G - Slot Strategy 2 (Hard) (4D, 橙色, 600 点)

広く捉えれば「各スロットに対して止める秒数を割り当てる」方法を考える割当問題だと言えそう。 問題へのリンク 問題概要 のグリッド が与えられる。各マスには 0 から 9 までの数字が描かれている。 今、次の条件を満たす 0 以上の整数値 を考えたとき、 …

AtCoder ABC 314 Ex - Disk and Segments (4D, 赤色, 625 点)

本当に三分探索で通るのね! これらの問題を思い出した drken1215.hatenablog.com drken1215.hatenablog.com 問題へのリンク 問題概要 二次元平面上に 本の線分がある。この平面上の円盤 (円周と内部を含む) のうち、 本の線分すべてと共有点をもつようなも…

JOI 二次予選 2021 E - スパイ 2 (4D, 難易度 10)

面白かった。 問題へのリンク 問題概要 人がいて、それぞれ「スパイ」か「非スパイ」かのどちらかである。 人のうち、何人かについてはスパイかどうかが予めわかっている ( で与えられる)。 個の証言がある。各証言は人 が証言者によってなされ、「人 はスパ…

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

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

AOJ 3182 Umg Kart (HUPC 2020 day3-K) (4D)

確かに、えでゅふぉのラス問にありそう! 問題へのリンク 問題概要 人の選手が距離 のレースを走る。 人目はデフォルトでは距離 1 走るのに 秒かかる。 スタートから距離が のところにアイテムがある。各アイテムは各選手に対して独立に、確率 で減速 (距離 …

第6回 ドワンゴからの挑戦状 予選 D - Arrangement (4D, 橙色, 800 点)

今回は惨敗したけど次回また頑張りたい!!! 問題へのリンク 問題概要 の順列であって、以下の条件を満たすもののうち、辞書順最小のものを求めよ。存在しない場合は -1 を出力せよ。 の右隣の値は ではない 制約 考えたこと 色々手を動かしてみると、条件…

第一回日本最強プログラマー学生選手権-予選- E - Card Collector (4D, 橙色, 800 点)

マトロイドだ!!!!!!! 問題へのリンク 問題概要 のボード上の 個のコマがあってそれぞれ重みがつけられている。同じマスに複数のコマが置かれていることもある。 今、各行から 1 個以下のコマを取り去る。次に各列から 1 個以下のコマを取り去る。 最…

AtCoder ARC 038 D - 有向グラフと数 (4D, 試験管赤色)

後退解析を用いる問題。queue に不慣れなので、急に queue を使えるように。 問題へのリンク 問題概要 頂点 辺の有向グラフが与えられる。各頂点 には値 X_v が割り振られている。先手と後手とで以下の対戦を行う スタート時には駒を頂点 1 に置く 各プレイ…

競プロ典型 90 問 005 - Restricted Digits(4D, ★7)

きたまさ法によく似たタイプの DP ダブリング高速化! ただかなり難しい問題だと思うので、004 まで順調に解いていた方が、この問題で挫折しないように注意!!! 無理に解こうとせずに飛ばすのも一案だと思います...... 問題へのリンク editorial 問題概要 …