2020-11-01から1日間の記事一覧
AOJ
マンハッタン距離
AOJ-ICPC250点
最適化テク:最適解の形を考える
コーナーケース
最大値の最小化
計算幾何
連続最適化
連続量問題
式変形
競技数学色強め
入力が定数個
AOJ-ICPC
JAG夏合宿
浮動小数点型を扱う問題
伝説のりんごさんセットの 1 問目 問題へのリンク 問題概要 二次元座標平面上において、 座標と 座標のうちの少なくとも一方が整数であるような点からなる集合を「道路」と呼ぶ。 道路上の 2 点 のユークリッド距離が実数 で与えられる。 点 から道路のみを…
AtCoder
AtCoder800点
ARC-E
橙色diff
行列
二次元グリッド
mex
0と1と2の問題
ほとんどのところで値が一定値に決まる
収束性に着目する
実験
解空間:O(N^2)通りの選択肢
ピラミッド
操作後の結果を求める問題
コンテスト本番はこの問題から解いた!!確信を持つのに時間かかった 問題へのリンク editorial 問題概要 0 と 1 と 2 のみからなる の行列 がある。そのうちの と の値のみがわかっている。他のマスの値は、 に対して = mex() と定められている。 全体の 0,…
AtCoder
AtCoder600点
ARC-D
黄色diff
DP
数え上げ問題
入力が定数個
2^K
DP高速化
DP高速化:累積和
賢い漸化式
制約条件:総和=K
対象を一意に定める操作列を数え上げる
テク:全体を2倍する
いろんな DP が考えられそう! 問題へのリンク editorial 問題概要 正整数 が与えらる。以下の条件を全て満たす有理数の多重集合は何種類存在するか、998244353 で割ったあまりを求めよ。 多重集合の要素数は 多重集合の要素の総和は 多重集合の要素は全て (…