グラフの基本問題！ 問題へのリンク 問題概要 の人 がいる。 組の友達関係があって、 組目の友達は人 と である。 人 1 の友達と、人 1 の友達の友達に相当する人 (人 1 を除く) が何人いるかを答えよ。 制約 解法 この問題はグラフの練習問題といえる。グラ…

ちょっと重たい全探索問題 問題へのリンク 問題概要 の形に配列された二次元文字列 が与えられる。 に対して、次の操作を繰り返すことで に一致させたい。 反時計回りに 90 度回転する (コスト 1) 時計回りに 90 度回転する (コスト 1) 1 マス選んで文字を変…

ちゃんと証明しようとすると、結構大変！ 問題へのリンク 問題概要 人の生徒がいて、生徒 の身長は である。 これらの生徒を 2 人ずつ 組に分けて、どの組も身長差が 以下となるようにしたい。 そのようなことが可能かどうかを判定せよ。 制約 考えたこと こ…

ちょっと実装が大変なので、頑張って実装しよう！ 問題へのリンク 問題概要 太郎君と花子さんが大富豪を模したゲームをする。 の書かれたカードを、 枚ずつ、太郎君と花子さんに配る。太郎君に配られたカードに書かれた 個の数値が与えられる。2 人で次のよ…

直線がいくつかの区間に分かれているとき、点がどの区間に属するかを求めたいとなったら、lower_bound()！！！ 問題へのリンク 問題概要 数直線上に 個の鐘がある。 番目の鐘は座標 の地点に配置されている。 地点 の人の聞く鐘の音の強さは、各鐘 に対する …

DP の典型問題だけど、最初は難しく感じるかもしれない。あと、縦横が微妙に混乱するね。 問題へのリンク editorial 問題概要 (今風に表現改) のグリッドが与えられる。このグリッドで上から 番目、左から 番目のマスを と書くことにする。最初、マス に駒が…

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

累積和を使う代表的な問題ですね。 ジャッジへのリンク 問題文へのリンク 問題概要 個の整数からなる数列 と、整数 が与えられる。 数列から連続する 個の値を選んで総和をとる。この総和として考えられる最大値を求めよ。 制約 前提知識 まず、愚直な解法で…