問題概要 正方形のケーキがある。縦、横にチョコレート割して最後に連結成分がいくつになるか求める問題。 解法 この手の問題は座標を2倍に拡大すると単なるflood fillに落ちる。必要なら座標圧縮する。またDFSで書くならstack overflowには注意。

問題概要 文字列Sと文字列集合Xが与えられる。Sをいくつかに分解する。分解してそれぞれを適当に並び替えて、全てがXに含まれるようにしたい。並び替える前の部分文字列のうち、位置の異なる文字の個数がペナルティとなる。ペナルティを最小化する問題。でき…

問題概要 [0..n)を考える。この区間でx[i]をカバーするような長さkの範囲を考える。範囲を順番に動かし、動かす前後で交わってない部分をカバーするのにその範囲の分だけのコストがかかる。コストを最小化する問題。 解法 動かすときは領域の右端か左端がど…

問題概要 短い文字列はそのまま出力し、長い文字列は先頭の文字と長さ-2と最後の文字を出力する。

問題概要 N*N(N行列式をMOD p(0 解法 基本的には三角化で求める。ただし三角化の際逆元を求める必要があるのでそこで工夫する必要が出てくる。 pが素数の時は逆元を簡単に求めることができる。 pが合成数の時はpを素因数分解して、MOD q^kで求める問題に帰着…

要素が整数の行列に対して行列式をMOD Mで計算する。Mは素数でも合成数でも構わない。 SPOJ DETER3で動作確認。 計算量はO(sqrt(P) + N^3 * log^2 P)くらい？ グラフの問題とかで役に立つ場面があるかもしれないしないかもしれない。 namespace DeterminantI…

問題概要 H*W(H,W 考えたこと 問題文読んでる間に当時のことを思い出してしまった…。 これは確か答えに上限があったはずだ。ちょっとずるけど、5*5のサイズの盤面を全て試して答えが存在しことを確認した。 なのでW ここまで小さくなればいくらでも有り様が…

問題概要 長さN( 解法 等差数列は初項と第二項を決めれば一意に定まるので、初項と第二項がどうなるかを全探索する。 もっと賢いやり方もあったとは思う。

問題概要 4種類の団子がある。団子をシリンダーに上から押し込む。同じ種類の団子がL( 考えたこと (当時は手も足もでなかった問題)。 式一発はさすがにないだろうし、DPだろうか。 制限から計算量を予測するも、L^4*Nとか4^L*Nとかいろいろあってよく分から…

問題概要 s(x)をxを10進表記したときの各桁の和とする。[low, high](0 解法 s(x*x)=s(x)*s(x)になるためにはxの各桁の数字は0~3であることが必要。これは実験によってたしかめられる。こういうのはきちんと証明しないと書かないみたいな人が結構いるけど、個…

問題概要 1~1000のマスにコインがN( 解法 長さK以下の塊は一気に1マス動かせるものだと思えばよい。貪欲で解ける。最も後ろにある動かせる最大の塊を前にずらしていけば良い。

問題概要 長さL[i](アナグラムの部分文字列となっているようなもののうち辞書順最小のものを求める問題。 解法 文字数をカウントして最小値を答える。

結果。 tourist出題のセット。 Subanagramsはとても簡単だけど、書いてる途中に実装方針切り替えて書き直したせいで大幅に時間をとられて出遅れた。 Moving Coinsは多分貪欲だとあたりをつけて書き始めた。単なる実装ゲーとして見てもある程度高速化する必要…

Competitive Programming Advent Calendarでtayama0324さんが素晴らしい記事を書いておられました。なので自分もそれに触発されて、以前書いた記事の続きを書いてみました。以下はtayama0324さんの記事を読んでいることを前提に話をします。 DPのメリットと…

問題概要 最初にN個の箱がある。そのうち任意個数の空箱を選んで、箱の中にK個の新しい箱を詰める。このような作業をT回繰り返した結果、空の箱がF個ある。全ての箱の個数を求める問題。数字はいずれも10^6以下。 解法 式一発で求められる。非空の箱の個数さ…

問題概要 二人であるゲームをする。今数xがあって、各プレイヤーは交互にxに含まれる数字(10進数表記の下)で0でないものを選び、xから引く。xを0にしたプレイヤーの勝ちとなる。両者が最善を尽くしたとき勝つのがどちらか判定する問題。先手が勝つ場合は初手…

はじめに この記事はCompetitive Programming Advent Calendar12月10日分の記事です。 誤差が原因でWAになる問題が嫌いな人は決して少なくないと思います。「こんなのは本質的なことではない」という人もいるでしょう。誤差を回避することが本質となるような…

問題概要 H*W(H,W 考えたこと どっか1マスに集めるときの最小値を求める問題？どこに集まるか全探索するだけじゃん。 サンプル合わない。誤読していた。一列に集まるのか。じゃあどの列に集まるか全探索だ。 サンプル合わない。隙間なく並ぶのか。さてどうし…

初の2連続2完で満足度高い。2完勢の中では最下位に近いけどそれはまだ気にしないことにする。2完してレートが下がるようになったら真剣に考えよう。今回の問題はEasyの方が難しかったような。Mediumはちょっと典型的だったような気がする。以下コンテストの…

問題概要 二人でゲームをする。石がN(素数になるようにしなければならない。後手は石を1..K個取り除いて残りが合成数になるようにしなければならない。石を取り除くことができなくなったら負けになる。両者が最善を尽くしたとき何手で勝負が付くか求める問題…

問題概要 整数Nが2進表記で表される(長さN 考えたこと 10^6はO(N)の匂いがする。大抵こういう制約だと想定解にはlogすらつかない。 上位桁から考えて、余りがあるかどうかで(先頭からの桁数、上位桁に余りがあるかどうか)のDPで行けそうな気がしなくもない。…

問題概要 x=0, d=1とする。長さL( 考えたこと サイズ小さいしぱっと見工夫せずに解けそう。 幅優先っぽいDPで行けそうな気がする。 効率が悪いとされるbool配列でのDPを考える。 状態を(i文字目、位置、変更回数、向き)とすれば状態数は2*L^2*N。 で、遷移は…

問題概要 2次元のボード上で最短路を求める問題。 解法 幅優先。

問題概要 charをビットリバースしたりmod 256しながら計算する。 考えたこと サンプルの説明を見たらビットリバースして直前の値とうんぬんかんぬんと書いてある。 とりあえず書いたらサンプル通ってしまったのでそのまま提出。 本番中は全然気にしてなかっ…

結果。 順位を見たらそれなりにとれている。Bみたいなのは問題文の読解が厳しすぎて解ける気がしない。つまるところ、もうこれ以上はどうしようもなかった。ただしDに時間を使いすぎたのはちょっと反省。プレテストがもう少し弱ければWAっていた可能性もある…

問題概要 予算がB(区間[0,L( 解法 状態を(位置、これまでに使ったコスト)の組としてDP。毎回すべての要素を舐めるようなことをしなければ十分間に合う。

問題概要 長さN( 解法 RMQのライブラリ検証用問題として適切。長さが大きくなく、クエリ数が多いのでsparse tableを使うのが最も良いと思う。

問題概要 長さN( 解法 2^N通り全探索する。

問題概要 [A,B] (in [1, INT_MAX], B-A区間内の数において、各桁の数字の出現回数を数える問題。 解法 愚直に全部試す。

問題概要 整数N( 考えたこと 10^7とはまた微妙な制限だ。 N!が素因数pで何回割り切れるか求めればいいのか。 N!を奇数回しか割れない素数pで割ると考えればいい。 10^7の篩が間に合うかどうか。いもす先生のエラトステネスならぎりぎり間に合う気もする。 ロ…