2020-12-04から1日間の記事一覧
JOI
JOI本選
JOI難易度6
AOJ
AtCoder
二分探索
半分全列挙
二分探索:lower_bound
ある量を固定して考える
けんちょん本演習問題
【問題集】二分探索の入門
そのまま覚えたい典型問題
AtCoder 版蟻本記事で、登竜門として紹介している問題。 ずばり「半分全列挙 + 二分探索」です! 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 個の正の整数 が与えられる。これらの整数のうちから重複を許して 4 個まで選んで総和をとる (1 …
JOI
JOI予選
JOI難易度6
AOJ
AtCoder
全探索:ビット全探索
ある量を固定して考える
二次元グリッド
操作:flip
Greedy:各要素について独立に考えてよい
テク:幅が小さいことに着目する(2^Wが小さい)
典型要素を詰め合わせた教育的問題
幅が小さいので、幅についての 通りの探索が間に合う! 問題へのリンク 問題概要 のマス目がある。各マスの値は 0 または 1 である。次の操作を好きな順序で好きな回数だけ行うことができる。 ある行を選択して、その行の数値をすべてひっくり返す (0 を 1 …
JOI
JOI春合宿
JOI難易度6
AtCoder
各桁ごとに見る
アナグラム
文字列
順列の数え上げ
制約条件:総和<=K
辞書順
数え上げ問題
二項係数
どの場所で初めてsmallerになるかを考える
桁DPとは違うけど、桁DP的な発想で解けた ジャッジページへのリンク 問題概要 長さ の文字列 が与えられる。 の各文字を並び替えてできる文字列をすべて考えたとき、 はその中で辞書順で何番目の文字列に相当するのかを求めよ。 制約 の文字はすべて英大文字…
JOI
JOI春合宿
JOI難易度6
AtCoder
二分探索
二分探索:lower_bound
各kに対して
算数と数学
最大値と最小値を求める
現実世界の題材を扱った問題
テーマにストーリー性のある面白い問題
lower_bound を上手に駆使する系 ジャッジページへのリンク 問題概要 人の選手が、コンテストに参加している。各選手の現在の得点は である。 どの選手についても、今後加算される可能性のある得点は、 点以上 点以下となっている ( 問中 問の競技が終了して…