計算量改善:O(N)で求められる式に変形する
AtCoder
AtCoder250点
ABC-C
灰色diff
NoviSteps5Q
易しい計算量改善
計算量改善:O(N)で求められる式に変形する
数列
考察テク:最大値や最小値に着目する
最適化問題
最大スコア
計算量改善のことを本当に知らないと、TLE に悩むかもしれない。 問題へのリンク 問題概要 長さ の 2 つの数列 、 が与えられる。 1 以上 以下の整数 を選んで、 の最大値を求めよ。 制約 考えたこと 最も素直に考えると、次のように二重 for 文を用いて解き…
AtCoder
AtCoder300点
ABC-C
茶色diff
気付き系
易しい計算量改善
計算量改善:O(N)で求められる式に変形する
オセロ
0と1の問題
for文
条件の言い換え
最適化テク:自明な上界が最適解
NoviSteps4Q
一次元グリッド
最小回数・最小個数を求める
最適化問題
ARC-C
綺麗な言葉で条件を言い換えよう！ 問題へのリンク 問題概要 一列に白色碁石と黒色碁石が合計 個並んでいる。 左右のいずれかに白色碁石と黒色碁石を置いていく。このとき、オセロのルールに基づいて石の色がひっくり返る。 すべての色を同色にするのに必要…
AtCoder
JOI
JOI予選・二次予選
JOI難易度3
考察テク:最大値や最小値に着目する
解空間:O(N^2)通りの選択肢
全探索
for文
最適化テク:探索候補を絞る
最適化テク:端点のみを考える
数列
絶対値やminを扱う問題
各kに対して
AOJ
NoviSteps5Q
易しい計算量改善
計算量改善:O(N)で求められる式に変形する
シンプルながらも、学べるポイントがたくさんある問題ですね 問題へのリンク 公式解説へのリンク 問題概要 JOI 市には から までの番号が付けられた 人の住民がいて、住民 () の年齢は 歳です。 JOI 市の住民の年齢 が与えられます。 に対して、住民 と他…
