ABC D問題 ジャンル分け

ABC100まで

体感難易度(★)、問題概要、一言コメント

自分で辞書的に使うために作ったもの

まだ解いてない問題の大まかな解法(累積和とかDPとか)を知りたくない人は見ないように

 

  

DP

004D - マーブル

★★★★☆

3つのマーブルの山を平らにならすために必要な最小移動回数を求める

006D - トランプ挿入ソート

★★☆☆☆

ばらばらなカードの山を昇順に並び替えるために必要な最小スワップ回数を求める

008D - 金塊ゲーム

★★★★☆

クレーンを最適な順序で動かしてより多くの金塊を回収する

座標圧縮って要素もある

015D - 高橋くんの苦悩

★★☆☆☆

"重さ"と"価値"って言葉を"幅"と"重要度"に置き換えたナップサック問題

選べる品物の個数にも上限があるのが若干めんどくさい

017D - サプリメント

★★★☆☆

サプリメントの摂取方法が何通りあるか

同じ種類のサプリは1日に1個までしか食べられない

032D - ナップサック問題

★★☆☆☆

n<=30 or w<=1000 or v<=1000のどれかを必ず満たすって条件のナップサック問題

ボスラッシュ的な 1問で3度おいしい

036D - 塗り絵

★★☆☆☆

木の頂点を2色で塗る総数を求める ただし隣り合う頂点は同じ色で塗れない

037D - 経路

★★☆☆☆

グリッドの上下左右のマスのうち今いるマスより大きい数字が書いてあるマスにのみ進める

好きなマスから好きなだけ進めるとして経路は何通りあるか

038D - プレゼント

★★★☆☆

 タテ・ヨコのサイズが異なる箱を最大で何重に入れ子にできるか

公式解説が超わかりやすかった

054D - Mixing Experiment

★★★☆☆

2つの物質のペアをいくつか組み合わせて決まった比率の薬品を作るのに必要な最小コスト

半分全列挙もあり

056D - No Need

★★★★★

カードに書かれた数字の総和がK以上になるような集合をよい集合として、カードiを含む任意のよい集合がカードiを抜いてもよい集合のままならカードiは不必要ってやつ

簡単な別解もあった

076D - AtCoder Express

★★★☆☆

区間によって速度制限がある中で電車が走れる最長の距離

082D - FT Robot

★★★☆☆

「前進」と「好きな方向に90度回転」を指定された回数繰り返して(x,y)に辿り着けるか

 

桁DP

007D - 禁止された数字

★★★☆☆

10^18以下で'4'と'9'を含まない数が何個あるか

029D - 1

★★★☆☆

1から10^9までの数字を順番に紙に書いたとき'1'って何回書いたか

高橋君イカれてる

050D - Xor Sum

★💃★💃★💃★

a^b=u, a+b=vとなる(u,v)の組の個数を求める

個人的に82問の中でぶっちぎりで意味不明だった ちゃんと理解しておきたい

 

bitDP

025D - 25個の整数

★★★★★

5*5のグリッドに、どの縦・横連続する3マスも昇順/降順にならないように数字を並べる並べ方の総数

ビギナーとは(。ŏ﹏ŏ)

041D - 徒競走

★★★☆☆

いくつか着順が確定してる状態で、徒競走の着順が何通り考えられるか

 

組み合わせ / 確率 / 数学的問題

003D - AtCoder社の冬

★★★★☆

X*YってスペースにデスクD個とサーバーラックL個を配置する仕方の総数

ただしスペースの上下左右各1列が空いていてはいけない

011D - 大ジャンプ

★★★☆☆

それぞれ1/4の確率で上下左右にDだけ進むとして、N回進んで(x,y)に着く確率

020D - LCM Rush

★★★★★★

1以上N以下の全ての数字とkの最小公倍数の和を求める

ビギナーとは( ・ั﹏・ั)

021D - 多重ループ

★★☆☆☆

1 <= a1 <= a2 <= ... <= ak <= nを満たす整数の組(a1,...,ak)の個数

024D - 動的計画法

★★★★☆

左下から右か上に1マスずつ進んでって(r,c)に辿り着く方法の個数を求める問題 の逆

(r,c), (r,c+1), (r+1,c)のマスに書かれた数字から(r,c)を復元する

028D - 乱数生成

★☆☆☆☆

1〜Nの数字を等確率に選ぶ機械を3回動かして、選ばれた数字3つの中央値がKになる確率

LCM Rushと同じコンテストの問題か?

042D - いろはちゃんとマス目 / Iroha and a Grid

★★☆☆☆

左上から右か下に1ずつ進んで(H,W)に辿り着く進み方の総数

ただし下からA個以内、左からB個以内のマスを通ってはいけない

057D - Maximum Average Sets

★★☆☆☆

N個の品物からA個以上B個以下選んだときの価値の平均の最大値とそういう選び方の総数

058D - 井井井 / ###

★★★★☆

横線m本と縦線n本があり、その中に存在する全ての長方形の面積の和を求める

066D - 11

★★★★☆

1〜Nの数字のみからなるN+1個の数列の長さkの部分列の個数

ただし1〜Nの全ての数字が1個以上入ってる つまり1つだけ重複した数字がある

071D - Coloring Dominoes

★★☆☆☆

2*Nのマス目に1*2か2*1のサイズのドミノが敷き詰められてて、それらを隣接するドミノの色が被らないように3色で塗る塗り方の総数

084D - 2017-like Number

★★☆☆☆

各クエリで[l,r]に含まれる「nも(n+1)/2も素数になる奇数n」の個数を出力 

090D - Remainder Reminder

★★☆☆☆

a%b>=Kとa,b<=Nを満たす正の整数(a,b)の組の個数を求める

094D - Binomial Coefficients

★★☆☆☆

n個の非負整数からaCbが最大になる2つの整数a,bを見つける

098D - Xor Sum 2

★★☆☆☆

数列に対してA[l]^A[l+1]^...^A[r] = A[l]+A[l+1]+...+A[r]となるl,rの組の個数を求める

 

幾何

016D - 一刀両断

★★☆☆☆

線分と板の形が与えられて、線分の位置で板を切断すると板が何枚に分かれるか求める

022D - Big Bang

★★★☆☆

点の集合Aとそれらを平行移動・回転・p倍拡大したBが与えられてpの値を求めるやつ

 

最短経路

012D - バスと避けられない運命

★★☆☆☆

好きな場所に引っ越せるとき、引越し先から最も遠い会社への最短経路の長さ の最大値を求める

030D - へんてこ辞書

★★★☆☆

閉路がある1本道の有向グラフをk歩進んだときに辿り着く頂点の番号を求める

10^100000みたいなバカでかい数字のmodをとるテクニックが必要

035D - トレジャーハント

★★☆☆☆

町iに1分滞在するごとにA[i]円もらえるとき時間内に何円稼いで戻ってこれるか

051D - Candidates of No Shortest Paths

★★☆☆☆

連結グラフにおいてどの異なる2頂点間のどの最短経路にも含まれない辺の数を求める

061D - Score Attack

★★★☆☆

辺(a[i], b[i])を通るとスコアがc[i](負のこともある)増えるとき、頂点nまでに稼げるスコアの最大値

ただしいくらでも稼げるときはinfと出力

067D - Fennec VS. Snuke

★★★☆☆

先手と後手が交互に自分の色が塗られた点と隣接する点をどれか塗っていって先に塗れる点がなくなった方が負け どっちが勝つか

問題の登場人物ってクソつまんなそうなゲーム好んでやるよね

070D - Transit Tree Path

★★☆☆☆

木とクエリが与えられる 各クエリでx[q]からKを通ってy[q]に行く最短経路を出力

073D - joisino's travel

★★☆☆☆

最大8個の街を好きな順番で巡ったときの最短経路

074D - Restoring Road Network

★★★☆☆

与えられた最短経路の隣接行列が正しいものか判断

079D - Wall

★★☆☆☆

数字iをjに変えるコストがa[i][j]のとき与えられたテーブルの数字を全て1に変える最小コスト

088D - Grid Repainting

★★☆☆☆

迷路の(0,0)から(H,W)に辿り着けなくならない範囲で何個まで道を壁にできるか

最小全域木

065D - Built?

★★★★☆

座標(a,b), (c,d)間を繋ぐのにmin(|a-c|, |b-d|)だけコストがかかるとき全ての街を連結にする最小コストを求める

 

二分探索

023D - 射撃王

★★★☆☆

初期高度と上昇速度がそれぞれ異なる風船n個を1秒につき1個撃ち落として、"各風船を撃ち落としたときの高さ"の最大値の最小値を求める

026D - 高橋君ボール1号

★★★☆☆

軌道がわかってる変化球を打つためにどのタイミングでバットを振ればいいか

033D - 三角形の分類

★★★★★

n個の点から3つ選んでできる三角形全てのうち鋭角・直角・鈍角三角形がそれぞれ何個あるか

034D - 食塩水

★★★☆☆

濃度と質量が異なるn個の食塩水を混ぜて作る食塩水の濃度の最大値

063D - Widespread

★★★☆☆

魔物がn匹いて、「任意の1匹にAダメージ、他のn-1匹にBダメージ与える」爆発を起こして全員倒すのに必要な爆発の最小回数

 

累積和 / imos法

001D - 感雨時刻の整理

★☆☆☆☆

雨が降ってた時間帯を整理する

005D - おいしいたこ焼きの焼き方

★★☆☆☆

点数テーブルとクエリが与えられ、各クエリで面積がp以下の長方形でテーブルの好きな場所を切り取ったときの、その長方形内の点数の和の最大値を出力する

080D - Recording

★★☆☆☆

複数のチャンネルで上映される全ての番組を録画するのに必要な録画機の最小機数

086D - Checker

★★★☆☆

グリッドとN個の希望がある i個目の希望はマスx[i],y[i]を黒or白で塗ること 

グリッドを1辺がKの市松模様で塗るとき最大で何個の希望を叶えられるか

089D - Practical Skill Test

★★☆☆☆

グリッドがあり、クエリiでは"整数Liが書かれたマスにまず駒を置き、駒が置かれたマスをxとするとき、x==Riになるまで駒をx+Dに移動することを繰り返す"ときの総コストを求める

2マス間の移動コストはマンハッタン距離

095D - Static Sushi

★★☆☆☆

円形のカウンターに寿司がn個あり、各寿司の位置と栄養価が与えられる

1m歩くたびに1キロカロリー消費し、好きなタイミングで退店できるとき、得られる栄養価を最大化

 

全列挙 / 全探索

002D - 派閥

★☆☆☆☆

議員同士の関係♂が与えられて、作れる派閥の大きさの最大値を求める

同じ派閥に属する議員は全員互いに関係♂を持っていないといけない

018D - バレンタインデー

★★☆☆☆

各女子が渡す相手が決まっているチョコをいくつか持っていて、その女子と対応する男子が同じグループならチョコを渡せる

女子p人と男子q人を選んで渡されるチョコの数を最大化する

031D - 語呂合わせ

★★★☆☆

数列と文字列のペアがいくつか与えられてそれぞれの数字がどの文字列に対応するかを調べる

例えば2-ni, 12-iniなら1-i, 2-niみたいな

060D - Simple Knapsack

★★☆☆☆

重さも価値も最大10^9のナップサック ただしw[1] <= w[i] <= w[1]+3

061D - 3N Numbers

★★★★☆

長さ3Nの数列からN個取り除いて残る長さ2Nの数列の (前半N個の総和) - (後半N個の総和) の最大値

075D - Axis-Parallel Rectangle

★★☆☆☆

N個の点のうちK個以上を内側に含む長方形の面積の最小値

099D - Good Grid

★★☆☆☆

問題の要約が難しい

100D - Patisserie ABC

★★☆☆☆

n種類のケーキがそれぞれ3つのパラメータx,y,zを持っていて、m個食べるとき、(xの合計の絶対値)+(yの合計の絶対値)+(zの合計の絶対値)を最大化

 

貪欲法

043D - アンバランス / Unbalanced

★☆☆☆☆

 長さが2以上で過半数が同じ文字である文字列をアンバランスと呼ぶ

文字列Sにアンバランスな部分文字列が存在するか判別

046D - AtCoDeerくんと変なじゃんけん / AtCoDeer and Rock-Paper

★☆☆☆☆

グーとパーしか存在しないじゃんけんで相手の出す手がわかってるときにスコアを最大化

ABCのD問題で唯一の300点問題(藁)

047D - 高橋君と見えざる手 / An Invisible Hand

★☆☆☆☆

高橋君がリンゴを売って得る利益を1円以上下げるための最小コスト

青木くんなにもんだよ

052D - Walk and Teleport

★☆☆☆☆

徒歩だと1歩ごとにA、テレポートだと距離関係なくBだけコストがかかる

N個の町を全て通るためにかかるコストの最小値を求める

053D - Card Eater

★★☆☆☆

カードの山から「任意のカードを3枚抜き取り、中央値のみ山に戻して残りを食べる」という操作を行って山に同じ値のカードがないようにするときの最小操作回数

064D - Insertion

★★☆☆☆

'('と')'のみからなる文字列Sを最も小さい正しい括弧列に直す

例えば ) ) ( ってあったら ( ( ) ) ( ) みたいに閉じたものが"正しい括弧列"

072D - Derangement

★☆☆☆☆

数列に対して「隣接する2要素を入れ替える」って操作をして、任意の要素p[i]についてp[i] != iとなるようにするときの最小操作回数

085D - Katana Thrower

★★☆☆☆

n個の刀を投げるか振るかでダメージを与えて体力Hを削りきるのに必要な最小操作回数

どの刀も投げる方がダメージが大きい代わりに一回投げた刀はもう使えない

 

Union-Find

040D - 道路の老朽化対策について

★★★☆☆

無向グラフで辺に"道の製造年度"って要素がついてて、クエリqではw[q]年度以前に作られた道を使わずにv[q]から行ける都市の数を出力する

049D - 連結 / Connectivity

★★☆☆☆

都市の間が道路と鉄道で結ばれてて、各都市から道路でも鉄道でも行ける都市の数を求める

 

行列累乗

009D - 漸化式

★★★★★

A[N+K] = (C[1] & A[N+K-1]) ^ (C[2] & A[N+K-2]) ^ ... ^ (C[K] & A[N])

⇡これのA[M]を求める(M<=10^9) は?って感じ

 

最大フロー最小カット

010D - 浮気予防

★★☆☆☆

無向グラフに対して「頂点を1個消す」または「辺を1本消す」って操作をして頂点0から特定の頂点に行けないようにするための最小操作回数

 

ダブリング / LCA

010D - 阿弥陀

★★★☆☆

あみだくじを大量に繋げたものの全ての始点について最後にどこに辿り着くか求める

014D - 閉路

★★☆☆☆

木に1本辺を足したときに出来る閉路の長さを求める

 

考察系

019D - 高橋くんと木の直径

☆☆☆☆☆

頂点が50個ある木の直径を、2頂点間の距離を100回まで質問することで求める

これ知ってて当たり前の問題なのか?完全に初見だった

027D - ロボット

★★★☆☆

ロボットを操作する指示が与えられる スコアを最大化 指示の種類は↓

1)右か左に1歩進む 2)今の座標をxとするとスコアがx増える 3)スコアが-x増える

039D - 画像処理高橋君

★★★☆☆

2値画像が収縮されたものを復元できるか判断 できるなら復元した画像を出力

044D - 桁和 / Digit Sum

★★★★★

n進表記したときの各桁の和がsであるような数字bを求める

これは思いつくの大変だなぁ

045D - すぬけ君の塗り絵 / Snuke's Coloring

★★★☆☆

H*Wマスの盤のうちNマスだけ黒く塗られてて、盤の中の全ての3行3列の連続するマス目のうち黒いマスがj個あるものの個数を0<=j<=9の場合全て求める

H, W <= 10^9

048D - An Ordinary Game

★★★★☆

文字列sの両端以外から交互に、取り除いても同じ文字が隣接する箇所ができないように文字を1つずつ取り除き、取り除ける文字がなくなった方が負けのゲーム

もう変なゲームすんのやめてくれ!

055D - Menagerie

★★★★☆

羊は自分の両隣が同じ動物ならo、異なるときはxと言い、狼は逆を言う

oとxからなる文字列に対してこの法則に矛盾しない動物の並びが存在するか判断

059D - Alice&Brown

★★★★☆

2つの石の山から交互に、片方の山から石を2i個とり、i個捨て、もうi個はもう片方の山に積む 操作を行えなくなったほうが負け

068D - Decrease (Contestant ver.)

★★★★★

長さnの数列に対して「数列の最大の要素からn引いて、他の要素は全て1増やす」という操作をちょうどk回すると数列の最大値がn-1以下になるような数列を1個求める

069D - Grid Coloring

★☆☆☆☆

H*Wのマス目に数字を詰める 数字iはa[i]個使い、同じ数字は全部繋がってないといけない

077D - Small Multiple

★★★★★

 Kの正の倍数の各桁の和としてあり得る最小値を求める(+_+)

078D - ABS

★★★★☆

交互に山札から何枚かカードを引いて、引く度に手札を捨てて最後に引いたカードを手札にする

最終的に2人の手札の数の差の絶対値はいくつになるか

081D - Non-decreasing

★★★★☆

長さNの数列に対し「a[y]をa[x]に足す」という操作を2N回までして数列を単調減少にする手順を1つ示す

083D - Wide Flip

★★★★☆

0と1からなる文字列を「長さK以上の区間の1/0を反転する」って操作のみで全要素0にできるようなKの最大値

087D - People on a Line

★★★☆☆

N人が一直線に立っていて、「人Riは人Liより距離Diだけ右にいる」という形の情報がM個与えられる

M個の情報全てに矛盾しないようなN人の座標の組が存在するか判定

091D - Two Sequences

★★★☆☆

長さNの非負整数列a,bについてa[i]+b[j]のxor和(1<=i, j<=N)を求める

092D - Grid Components

★★☆☆☆

100×100のグリッドを、白マスの連結成分がA個、黒マスの連結成分がB個あるように塗る方法を1つ見つける

093D - Worst Case

★★★★★

高橋くんが2回コンテストに参加し、1回目でA位、2回目でB位だったときに高橋くんよりスコア(2回のコンテストの順位の積)が小さい人の人数の最大値を求める

ABCのD問題では過去最高配点の700点

096D - Five, Five Everywhere

 ★★☆☆☆

「全要素が55555以下の素数」「全要素がそれぞれ異なる値」「どの異なる5要素を選んでもその和は合成数になる」という3つの条件を満たす長さnの数列を1つ出力

097D - Equals

★★☆☆☆

m個のペア(xi,yi)があり、与えられた数列pに対して任意回p[xi]とp[yi]をスワップできるとき、p[i]=iとなるiの個数の最大値を求める