URL https://community.topcoder.com/stat?c=problem_statement&pm=15436 概略 5桁の素数 $A, B, C$ がある．各桁の和が与えられるので，これを満たす $(A, B, C)$ の組を1つ求める．ただし $A, B, C$ は互いに異なる． 方針 $A, B$ を決め打つ全探索がしたくなる．5桁なので $O(n^2)$ は怪しいが，色々工夫すると通る． 主な枝刈りは以下の通り．手元で1s前後． エラトステネスの篩で $A, B$ の候補を絞る． $A < B$ とする． $C$ の1桁目は偶数でも $5$ でもないので，そこで探索を打ち切る． $C$ の最上位は $0$ ではないので，そこでも探索を打ち切る． $C$ の素数判定は篩の中を二分探索する．（これは怪しい） [展開する] 反省 どう頑張っても1sかかるので，ジャッジを信じて投げたら通った．あとでシステスを通したら最大で400msだった．信仰心が足りない．
URL https://community.topcoder.com/stat?c=problem_statement&pm=15257 概略 単純無向グラフ $G$ が与えられる．$G$ の橋を含まないような誘導部分グラフのうち，頂点数が最大となるものを求める． 方針 要は，$G$ から橋だけを残したグラフについての最大独立集合問題である．このグラフは明らかに森であるから，木DPが使える． 参考 制約が甘いので橋の検出にはUnionFindを使う．各辺ごとにそれを除いたグラフを構築し，端点の連結性を判定する． [展開する] 反省 本番では橋の検出までしかできなかった．最大独立集合問題であることにはなんとなく気付いていたが，名前だけが先走った．「NP困難じゃん…」 dp等の初期化も忘れずに．
URL https://community.topcoder.com/stat?c=problem_statement&pm=11295 概略 $N$ 日間だけ開くレストランがある．メニューは $M$ 種類あり，その値段は日ごと，メニューごとに異なる． また，注文するメニューは $7$ 日前と同じでなくてはならない． 1日1回注文をするとして，財布の限り粘るとすると何日間粘ることが出来るか． 方針 サンプル1を見ると，1日だけいる場合と8日いる場合とでは，取る料理の種類が異なることがわかる．なので日を進めるたび，曜日( $7n$ 日前)の料理をおさらいして最小コストを再計算してやるとよい． 7日目まではソートして一番左にくるやつを選ぶ．以降は曜日でかかったコストをいったんbudgetに戻してから再計算．この方法だと貪欲にやってる感が強いので見通しはいい． [展開する]
これ本家のカテゴリが Recursion なんですけど，どうなんですかね． URL https://community.topcoder.com/stat?c=problem_statement&pm=11485 概略 ウサギとネコが合わせて $N$ 匹いる．彼らの身長は互いに異なる． 1匹ずつに次の質問をする． 「あなたと同じ種類で，あなたよりも身長が高い動物は何匹いるか？」 彼らの回答が全て正しいものとするとき，それを構成するウサギまたはネコの割り当ては何通りあるか． 補足 {0,0,1,1,2}という回答が得られたとき，ウサギをR，ネコをCとすると， {R,C,R,C,R} {R,C,R,C,C} {R,C,C,R,R} {R,C,C,R,C} {C,R,R,C,R} {C,R,R,C,C} {C,R,C,R,R} {C,R,C,R,C} の8通りが考えられます． 方針 $2^{40}$ をシミュレートすることはまず無理． とりあえずanswersをソートしてみる．ウサちゃんもネコちゃんも同じ身長の同種はいないとのことなので，構築可能であるとき， answers={0,0,1,1,2,2,…,n-1,n-1,n,n+1,n+2,…,m} になる．逆にこうでないものは全て弾く必要があってこれが結構面倒．実装ではmapで数えてuniqueを取っている． 各数字へのウサギとネコの割り振り方は， $$ 2(多いほうがウサギかネコの2通り) \times 2^{n} = 2^{n+1} $$ [展開する]
URL https://community.topcoder.com/stat?c=problem_statement&pm=11464 概略 Lucky numberは $4,7$ のみを含む数字である． JohnとBrusはゲームをする．先ずJohnが長さjLenの区間を選ぶ．そのあとBrusが長さbLenの区間を「Johnが選んだ区間」の中から選ぶ．Brusが選んだ区間に含まれるLucky numberの数がポイントになる． Johnがスコアを最大化するように，Brusがスコアを最小化するように戦術をとるとき，最終的なスコアはいくらになるか． 方針 範囲が $[1,4747]$ と狭いので全探索できそう． Johnはスコアが大きくなるように，Brusはスコアが小さくなるように，それぞれ区間をとるというのがわかりにくい．こういう戦略最適化問題の場合，おおむね先手はエスパーなので，まずBrusの行動から考える． BrusはJohnの決めた区間のうち，スコアが小さくなるよう更に区間を定める．つまり，Johnの各選択に対してスコアは一意に確定することがわかる．こうなると後は単純で，Johnはこの内スコアが最も大きくなる選択をすればいい．数学でやる1文字固定に近い． どうせラッキーナンバーは少ないので，2進数を列挙する感覚で全部書き出した．春に受講した，ひたすらカルノー図を書く授業を思い出してちょっと鬱になった． Brusが全範囲の最小値を必死に探す中，Johnはそのうちの最大値を高みの見物で選ぶ．そんな主従関係が目に浮かぶと書きやすいですね． [展開する]
URL https://community.topcoder.com/stat?c=problem_statement&pm=11434 概略 $1 \sim N$ のスロットが1列に並んでいる．プレイヤーは常にスロット $1$ の中身しか取得することができない．ゲームの目的は，開始時にスロット $M$ にあった中身を取得することである． スロットには2通りの操作を行うことが出来る． Divide $N$ を割り切れる素数 $p$ を選びスロットを $[1,\frac{N}{p}],[\frac{N}{p}+1,\frac{2N}{p}],…$ に分割する．この内，目的のスロットを含む部分列のみを保持する．その後，$N←\frac{N}{p}$とし，スロットの番号を $1 \sim \frac{N}{p}$ に振り直す． Shift スロットを左/右にシフトする．シフトするとスロット番号が $-1/+1$ だけ変化する．スロット $0$ は $N$ に，$N+1$ は $1$ に別途移動する． 最低で何回操作をすれば目的を達成できるか． 方針 全然できなかった．調べたら「DivideとShiftの操作は可換」ということがわかって（証明は知らない）そこからはノーヒントで行けた．これで250ptなんだ… Shiftは数えるだけなので先にDivideを行う．Divideのやり方は高々、2^(素因数の数)だから全列挙してやればいい．あとは各々についてShiftの回数を求める． のんきに数えてたらTLEしたので，剰余で考える必要があるのだが，これが難しかった．右にShiftする場合の式がよくわからなくて，手元のサンプルと帳尻を合わせるように書いたら通った（最悪） [展開する]
URL https://community.topcoder.com/stat?c=problem_statement&pm=11096 概略 $n$ が与えられる．$n$ を下1桁が $4$ または $7$ である正の数の和として表すとき，必要な項数の最小はいくつであるか．構成不可能であれば -1 を返す． 方針 $4+10k,7+10k$ を使うことが出来るので，$n$ が項数 $x$ で構成可能であるとき，$n+10k$ も項数 $x$ で構成可能．したがって $n$ の下1桁に注目してやればいい． 例えば下1桁が $3$ になるような項数最小の構成法は $$ 23 = 4 \times 4 + 7 \times 1 $$ である．これを下1桁 $0 \sim 9$ についてやればよく，結果下図が完成した． 4と7で表せる数の下一桁 最小値未満の数は表せない [展開する]
URL https://community.topcoder.com/stat?c=problem_statement&pm=11154 概略 $N$ 個の街があり各々には名前がついている．2つの街の合併を繰り返し，最終的に1つにすることを考える． 合併前の街の人口を $i,j (i \leq j)$ とする． $i < j$ のとき 合併後の街の名前は $j$ を継承する． $i = j$ のとき 合併後の街の名前は $i$ または $j$ を継承する． 最終的に街が1つになったとき，その名前として取り得るものは何通りか． 方針 B - Colorful Creatures — AtCoder Grand Contest 011 サンプル5の解釈を説明する． ソートして人口の昇順に並べても一般性は失われない．また赤は累積和である． 合併のルールから，自分より人口の少ない街は無条件に取り込めるので全て取り込むことにする．これで増えた人口でも1つ右の街が取り込めなければ，その街が生き残ることはない．最終目標は全ての街を合併することなので，右から赤と黒を判定をしていき，図の点線のように断層ができるまでの数が答え． [展開する]
URL https://community.topcoder.com/stat?c=problem_statement&pm=11397 概略 perfect sequence とは以下の条件をともに満たす数列である． 全要素が非負整数 全要素の積と和が等しい seq の要素をひとつだけ変更して perfect sequence が作れるかを判定する． 方針 $$ S_i = \frac {\sum_k{seq[k]}} {seq[i]} $$ $$ P_i = \frac {\prod_k{seq[k]}} {seq[i]} $$ とすれば，perfect sequenceが作れる時 $$ S_i + x = T_i \times x ⇔ S_i = (T_i - 1) \times x $$ をみたす $x$ が1つ以上の $i$ で存在する． ただし以下の点に注意． 変更しないのはダメ． seq のサイズが1なら必ず Yes $T_i - 1 = 0$ のとき0除算で危ない．この場合， $S_i = 0$ であればよい。 最悪のケースだと $T_i \approx 10 ^ {9 \times 50}$になってオーバーフローするからこのコードはダメなはず…だけど，普通に通る．
URL http://community.topcoder.com/stat?c=problem_statement&pm=11400 概略 小長方形を組み合わせた長方形の盤面が与えられる．小長方形の各々について，面積がわかっていればY，そうでなければNと表記される．質問をするたび，任意のNが1つYに変化する．最低で何回質問をすれば盤面全てをYに変えられるか． 方針 図の赤枠のように長方形をとる．このとき，頂点と接する4つの小長方形に着目する． 図より，このうち3つの面積がわかっている(Y)ならば，残り1つの面積もわかる．このような作業を繰り返すといずれ盤面のYが増えなくなるため，小長方形の面積を質問する必要がある． 質問する小長方形はどれでもよさそうだが確証はない． 追記1: ケースが大きいとTLEするらしい．再帰部分が明らかに怪しいがいまいちわからない．改善中… 追記2: creepさんなどの記事を参考にして通しました．TLE解では再帰時に頂点を全探索していたので $O(W^2H^2)$ だったが，実際にはN→Yとしたところに関係する場所しか変わらないので，$O(WH)$ に減らせるはず．結果として全体では $O(W^3H^3)$ → $O(W^2H^2)$ に削減． 改善後 [展開する] 改善前 #include <bits/stdc++.h> using namespace std; class RectangleArea { public: int h,w; int board[51][51]; int ret=-1; void greed(){ for(int y=0;y<h-1;y++){ for(int x=0;x<w-1;x++){ for(int dy=y;dy<h;dy++){ for(int dx=x;dx<w;dx++){ if(board[y][x]+board[y][dx]+board[dy][x]+board[dy][dx]==3){ board[y][x]=board[y][dx]=board[dy][x]=board[dy][dx]=1; greed(); } } } } } } int minimumQueries( vector <string> known ){ h=known.size(); w=known[0].size(); for(int y=0;y<h;y++){ for(int x=0;x<w;x++){ if(known[y][x]=='Y') board[y][x]=1; else board[y][x]=0; } } while(1){ ret++; greed(); bool end=true; for(int y=0;y<h;y++){ for(int x=0;x<w;x++){ if(board[y][x]==0){ board[y][x]=1; end=false; break; } } if(!