ビット全探索もついに茶色 diff ですね！ 問題へのリンク 予備知識 ビット全探索の知識があると解きやすいです！ drken1215.hatenablog.com 問題概要 英小文字のみからなる 個の文字列 が与えられます。 これらの文字列の中から、いくつかの文字列を選びます…

1. はじめに お久しぶりです！ けんちょん本のけんちょんです。 最近はアルゴリズムがとても盛り上がっていますね。今回新たなアルゴリズム本を上梓させていただくことになりました！ 発売予定日は 2022/4/20 です。一部大型書店では、もうすでに並んでいる…

めっちゃ面白い問題だった！ 問題へのリンク 問題概要 頂点 0 を根とする頂点数 の根付き木が与えられます。頂点 0 以外の頂点 には数値 が書かれています。今、頂点 0 にコマが置いてあります。 高橋くんと青木くんが次の動作を交互に繰り返します。 青木く…

包除原理を学べる問題！ 問題へのリンク 問題概要 個の文字列 が与えられます。次の手順によって作れる長さ の文字列の個数を 998244353 で割ったあまりを求めてください。 のいずれかを選ぶ 文字列 に含まれる文字のみを使って、長さ の文字列を作る 制約 …

迷路の最短路問題なので BFS でやりたくなるが、まともにやると で TLE してしまう！！ 頂点の持ち方を工夫して 0-1 BFS で解く！ 別解として枝刈り BFS も。 drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドが与えられます。各マスは通路 (文…

前回の ABC に続いて、D 問題が数学っぽい。でも実際には今回は探索問題ですね。 問題へのリンク 問題概要 非負整数 を用いて と表せる整数 を「特別数」と呼ぶことにします。 非負整数 が与えられますので、 以上である最小の「特別数」を求めてください。 …

ソートが必要になるところが少し難しいかもしれない。 問題へのリンク 問題概要 個の商品があって、それぞれ 円である。 またクーポンが 枚あって、1 枚のクーポンを使って次のことができる。 商品を 1 つ選ぶ その商品の価格を 円減少させる ただしもとの価…

「競プロ典型 90 問 001 - Yokan Party」とよく似た問題！ 問題へのリンク editorial 前提知識 基本的な二分探索 問題概要 枚の絵が一直線上に順に並んでいます。 枚目の絵は座標 の位置にあり、その価値は です。 今これらの絵から 枚の絵を選びます。この…

落ち着いて整理して考えましょう。問題自体は「累積和」が使える良い問題ですね！ 問題へのリンク editorial 問題概要 個の電球を一列に並べていて、オンオフ状態が であるような状態を作りたいとします。ただし は 番目の電球をオンにしたいことを表し、 は…