2024-04-22から1日間の記事一覧
というコーナーケースにやられた! 問題へのリンク 問題概要 整数 が与えられる。 を で割った余りの一の位の値を求めよ。 (マルチテストケース) 制約 考えたこと まず最初に考えたのは「全体を で割った世界」で考えれば良いということ。 このことを正当化…
順列テク:逆順列を考える
順列
ソートすることが目的の操作の問題
構築
AtCoder
AtCoder300点
灰色diff
ABC-C
そのまま覚えたい易しい教育的典型問題
データ構造テク:どこにその要素があるのかを管理する
操作
操作をK回まで行える
操作:swap
NoviSteps3Q
の計算量で良いなら簡単。 「どこに値 の要素があるのか」を管理するというテクニックをここで習得しよう! 問題へのリンク 問題概要 の並び替えである順列 が与えられる。これをソートしたい。以下の操作を 回まで実施できる。 を選んで、 と を swap する …
バケット
集計処理
AtCoder
AtCoder200点
ABC-B
灰色diff
データ構造
フラグを活用する
ビットを活用する
操作:flip
操作
そのまま覚えたい易しい教育的典型問題
NoviSteps6Q
「集計処理」の基本問題! 問題へのリンク 問題概要 (意訳) 個の LED が最初はすべて光っている。 回の処理を行う。 回目の処理では 番目の LED の状態を flip する (光っていたら消して、消えていたら光らせる)。 最終的に何個の LED が光っているかを求め…
グラフ
テク:グラフの問題として考える
探索順序を工夫して解く
各地点について自由度を掛け算していく
数え上げ問題
AtCoder
AtCoder700点
ARC-C
黄色diff
後退解析
順列
グラフ・盤面・数列の個数の数え上げ
NoviSteps3D
これは面白かった。 問題へのリンク 問題概要 の順列であって、以下の 個の条件を満たすものの個数を 998244353 で割った余りを求めよ。 について、 である 制約 考えたこと グラフの問題として考えることにした。つまり、0-indexed で表現すると 頂点数 、…