各桁がある値を持つ条件を大小関係に関する条件に言い換える
yukicoder
floor_sum
各桁がある値を持つ条件を大小関係に関する条件に言い換える
テク:スタートを0としてよい
各桁ごとに見る
入力が定数個
マルチテストケース問題
テク:l以上r以下の個数→f(r)-f(l-1)
floor sum の練習！ 問題へのリンク 問題概要 以上 以下の の倍数をすべて十進表記で 1 回ずつ書き出した時、数字 が書かれる回数を求めよ。 (テストケースが 個与えられる) 制約 考えたこと 各桁ごとに考える。整数 の右から 桁めが である条件は を で割っ…
AtCoder
AtCoder600点
ABC-Ex
橙色diff
floor_sum
数学(整数問題)
各桁ごとに見る
0と1の問題
各桁がある値を持つ条件を大小関係に関する条件に言い換える
条件の言い換え
主客転倒・寄与分解
そのまま覚えたいシンプル設定の中堅以上の典型問題
floor sum と聞いて！！ 問題へのリンク 問題概要 以上 以下の整数のうち、 で割って 余るものを考える。そのような整数の popcount 値の総和を求めよ。 ( ケース与えられる) 制約 考えたこと TL を見て、floor sum と知った上での考察。 「popcount の総和…
AtCoder
AtCoder900点
AGC-D
DEGwerさんの数え上げテクニック集の例題
数え上げ問題
条件の言い換え
連結性に着目する
後ろから解く
0と1の問題
操作:上書き
部分和
入力が定数個
各桁ごとに見る
各桁がある値を持つ条件を大小関係に関する条件に言い換える
橙色diff
再帰的に上位桁から順に値で分類した木を作る
最大値と最小値の間はすべて作れることに着目する
最初、「これは本当に AGC か！？？」となってた 問題へのリンク 問題概要 以上 以下の整数の中からいくつか選んで、OR 和をとってできる値が何通りあるか求めよ。 制約 考えたこと 一見するとこどふぉっぽい見た目の問題だけど、実はすごく AGC っぽい感じ…
各桁ごとに見る
XOR
主客転倒・寄与分解
累積和
データ構造テク：前処理
条件の言い換え
総和を求める
ABC-D
AtCoder
AtCoder500点
解空間:O(N^2)通りの選択肢
二分探索
二分探索:lower_bound
0と1の問題
各桁がある値を持つ条件を大小関係に関する条件に言い換える
ARC-D
黄色diff
そのまま覚えたいシンプル設定の中堅以上の典型問題
NoviSteps2D
桁ごとに考えるしかなさそうなのはそれはそう... 問題へのリンク 問題概要 (ARC 092 D / ABC 091 D) 要素の数列 と が与えられる。 個の整数 の XOR 和を求めよ。 制約 < 解法 XOR 和と言われた時点で、各桁ごとにカウントしたい気持ちにはなる。 個の整数の…
