2019-05-15から1日間の記事一覧
これの Easy バージョン。すごく楽しくて好き!!!!! Easy:操作の結果が所望になる入力を求める逆問題 Hard:操作に入力を与えた結果を求める問題 という風になっていて、普通「操作の結果を求めるだけ」の問題の方が絶対簡単なことが多いのに、Easy と …
さ、300 点!? 問題へのリンク 問題概要 個の中からランダムに選ぶ試行を 回行う。それぞれのものが出た回数が 回になる確率を としたとき、 を満たすような最小の を求めよ。 制約 考えたこと 確率を求めること自体は難しくなくて、 で求められる。が、こ…
AtCoder
AtCoder300点
ABC-C
ソート
Greedy
灰色diff
価格に関する問題
【問題集】ソート
Greedy:条件を満たすまで大きい順に取っていく
ソート:条件を満たすまで大きい順に取っていく
最小回数・最小個数を求める
ペア値のソート
ソート:比較関数を設計する
そのまま覚えたい易しい教育的典型問題
最適化問題
これでひとまず ABC 100 以降の CD 問題は全部書けた 問題へのリンク 問題概要 個のお店があって、各店 では 1 本 円のエナジードリンクを 本まで買うことができる。 全部で 本のドリンクを買いたい。最小で何円で実現できるか? 制約 考えたこと 基本的に安…
AtCoder
AtCoder400点
ABC-D
二値パラメータ問題
最適化テク:最適解の形を考える
最適化テク:緩和しても良い
最適化テク:解を変形していく(最適性を失わずに)
データ構造
setの上手な使い方
差分更新
N個からK個を選ぶ設定の問題
ある量を決めるとGreedy
ある量を固定して考える
Greedy
priority_queue
探索順序を工夫して解く
番兵法
最大スコア
青色diff
非自明な比較関数でソートする
最適化問題
学び多き問題。 僕にとっては後半のデータ構造パートが苦戦を強いられ、本当に勉強になった! 問題へのリンク 問題概要 個の寿司があって、それぞれネタ と美味しさ をもっている。この中から 個の寿司を選びたい。選んだ寿司集合のスコアは 選んだ寿司の美…