問題概要 人がN( 考えたこと ビットDP臭。でもそれにしても6は小さい気がする。 最も単純に状態を表すと、(残ってるメンバー、今誰のターンか)で6*2^6通り。 この状態遷移はDAGになってないからDPやメモ化再帰だと素直にかけない。 ならば連立方程式か。 こ…

問題概要 所属しているグループ名の集合と、アクセス可能な部屋名の集合と、(書名、部屋名、グループ名)の集合が与えられる。部屋名とグループ名がどちらも集合に含まれるような書名は何通りあるか求める問題。 考えたこと setなりなんなりに突っ込んで調べ…

主にC++でbool型を扱うときに注意することを覚えているうちに書いておく。 まず、当たり前のことから。 assert( sizeof(bool) == 1); bool hoge; assert( sizeof(hoge) == 1); const int N = 10; assert( sizeof(bool[N]) == N ); bool piyo[N]; assert( siz…

問題概要 H*W(H,W 考えたこと 何か最大流の匂いがするような。 でもサイズ小さいし、ビットDP？ コストの計算に上の列の情報がいるから前の列と今の列で2重にビットを回すのか。 計算量がH*2^(2*W)*Wでちょっと多い。2^20 * 100を計算すると10^8。ギリギリ間…

問題概要 長さL[i]( 考えたこと いつも基本は全探索。長さをいくつに揃えるかを固定したら利益の計算がO(N)位でできそう。 何本作れるかは単純に割り算。何回切る必要があるかは割り算のceil-1で出せる。 サンプルの最後のケースが親切過ぎる。木によっては…

問題概要 円周上にN個の点がある。このうち、いくつかを選んで互いに素な集合A、Bをつくる。ただし、Aの各要素を角度rだけ回転させるとBと一致するようにしなくてはならない。最大でいくつ集合に含めることができるか求める問題。 考えたこと 何度回転させる…

問題概要 K-riderという新しいチェスの駒を考える。K-riderはナイトの動きを1ターンにK回以下行うことができる。H*W( 考えたこと サイズが小さいし、幅優先で間に合いそう？ 最大でH*W個のriderが居て、各riderについてO(H*W)でマスの移動に何ターン必要かで…

問題概要 雑草がN( 考えたこと 何かgrow[i]/init[i]見たいな変なのをキーにして貪欲にやるんだろうか。 これはあれか、単調性が無いから二分探索は使えないのか。 とりあえず同じのを二回以上切る必要は無いよね。だから答えの範囲は[0..N]で全探索行けそう…

問題概要 W*H(W,H 考えたこと うん？これ最小点被覆(Asteroids POJ 3041, 蟻本205p)？(与えられた盤面を真っ黒にする問題かと思ってた) でもDiv2 250でそんなの出る訳無いよね。 問題文を読み返してやっと正しく理解した。 真っ黒な列、行の数を数えるだけに…

問題概要 整数N(再帰的に分解される。途中でtargetという値が必ず現れるかどうか判定する問題。 考えたこと Nが大したことないし普通に愚直に探索で間に合いそう。 書けた。メモ化も付けることができるけど、最大ケースだと思われるのが余裕で間に合ってるし…

問題概要 N( 考えたこと サンプルが弱くて参考にならん。取りあえず非自明なケースを突っ込んでおく。 単調性から二分探索臭がする。冷静に考えると別に二分探索で無くても解けそうな気はするが、判定問題に落とした方が問題が単純になるので二分探索で。 ta…

問題概要 右方向にしか動けないナイトが原点上にいる。H*W( 考えたこと DAGの最長パスの問題だけど、今回はサイズが大きいのでグラフ的な考えは無視する。 4回以上動くときは、最初に4通り動けば良さそう。 何か場合分けで全部解けそうな気がする。 場合分け…

問題概要 L*W*H(L,W,H 考えたこと 立方体のサイズの増え方からしてgreedyっぽい？ でもgreedyだとしてもどう埋めていけばいいのかよく分からない。 とりあえず、どう埋めるかは置いておくとしてA[i]は最初無視して考えてよいことに気付いた。 数の上限が無い…

問題概要 i人の顧客がいる。それぞれ、ある商品の値段がP[i]以下ならその商品を買う。ただし、商品を届けるのにC[i]の費用がかかる。利益を最大化するには商品の値段をいくらに設定すべきか求める問題。出てくる数字は10^6以下。 考えたこと 値段を決めれば…

問題概要 右を向けとか後ろを向けとか止まれとかの命令列が与えられるので最後にどこを向いてるか求める問題。 考えたこと 最後にMOD 360してやればよい。 stringstream使うの面倒くさい。

問題概要 長さN( 考えたこと 数字が小さいので、どうとでもなりそう。 どの文章が正しいのか全通り試せばよさそう。 矛盾が生じるのは、どの文章も正しくなくて、かつAの要素に0が含まれているとき。

問題概要 2彩色されたグラフ(|V| 白のノードに対して、石の数を隣接するノードにある石の和にする。 黒のノードに対して、石の数を隣接するノードにある石の和にする。 という操作を行う。N( 考えたこと Nが大きいので行列累乗で書けたら嬉しい。 白→黒と黒→…

問題概要 W*H(W*H 考えたこと サイズがやたら小さい。 最小支配集合か。 H>=Wを仮定するとWの最大値は6。ビットDPが見える。 ライツアウトに似た匂いがするけどもう少し面倒そう。 上の列の状態が決まれば今の列をどうすべきかも決まるのでビットDP的なもの…

問題概要 N( 考えたこと (Twitter上で解法らしいものが飛び交っていた後で手を付けた問題です) 最後にその約数がカウントされたのがいつかタイムスタンプを押しておけばOK。 平方数に対して2重にカウントしないよう注意。

問題概要 整数N( 考えたこと ロシアゲーですね。 とりあえず和はぴったりyに等しくなると考えて良いことは分かる。 で、和が一定な状態で二乗和を大きくするには偏りをつければよい。 なので、a[1],...,a[N-1]=1, a[0]=y-(N-1)としてa[0]>0かつ二乗和がx以上…

問題概要 W*H(W,H 考えたこと O(1)解法があるかもしれないけどそんなのに興味は無い。 ある正方形を考えて、その中に何通りの正方形があるかを数えてやれば良さげ。 これは簡単だ。include無しでササッと書けて気分がいい。

問題概要 線路の図が与えられる。ある距離以内にある到達可能なノードの数を求める問題。 考えたこと ただの面倒くさいBFSにしか見えない。

問題概要 各文字間に距離が定義される。与えられた文字列との距離が最小になるような"Month day"のフォーマットに従った文字列を返す問題。 考えたこと どう見てもやるだけ問題。 グラフ構成パートが面倒だけど、バグが起きないように非コピペで書こう。 一…

問題概要 整数係数の多項式が与えられる(次数n 考えたこと 根の候補はそんなに多くないので、候補を列挙して確かめれば良さそう。 0と、最低次の非ゼロの係数の正負の約数が候補になる。 ただ、普通に多項式を計算したらオーバーフローするので、それをどう…

問題概要 N*M(N,M 本番中考えたこと 1-indexedだと何かと面倒なので0-indexedにして最後にNを足せば楽そう。 そういえばk-indexedという表現とk-originという表現はどっちがよく使われているんだろう。あまり見ないけどk-baseという表現もあるらしい。 まず…