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(!
URL http://community.topcoder.com/stat?c=problem_statement&pm=11233 概略 ボールが1列に並んでおり，先頭から順に取り出す．取り出したボールの色によって，列に以下の操作がなされる． white 列を反転させる black 色を反転させる 操作終了までに取り出したblackの数を求める． 方針 愚直に再現すればよさそう．でも色反転の操作がダルそうだったので，状態を別で保持しxorを使うことで省略．初めは以下のコードをsubmitしたが，システスでTLE．よく考えれば $O(N^2)$ なので当然． #include <bits/stdc++.h> using namespace std; class MathContest { public: int countBlack( string ballSequence, int repetitions ) { int n=ballSequence.size(); vector<bool> balls; for(int i=0;i<repetitions;i++){ for(int j=0;j<n;j++){ if(ballSequence[j]=='B') balls.push_back(1); else balls.push_back(0); } } int black=0; bool rev=1; while(balls.size()){ bool color=balls.front(); balls.erase(balls.begin()); if(color^rev){ reverse(balls.begin(),balls.end()); }else{ rev=!rev; black++; } } return black; } }; 一番上を取り出すときのerase スタック反転時のreverse この二つが $O(N)$ なので省略する必要があったが，ここで異常に悩む．eraseの代替をpop_backで考えていたため，reverseと両立できなかったのが原因．結局，reverseは色反転と同じようにフラグ管理で，eraseはindexを操作することで解決．
URL http://community.topcoder.com/stat?c=problem_statement&pm=11204 概略 $N$ 種のパンについての情報underとoverが与えられる．各種のパンには $X_i$ が定められており，これより小さいパンはunder，大きいパンはoverである．$\min N$ はいくらであるか．条件を満たすパンが存在しない場合-1を返す． 方針 最初サンプル3の意味がわからなくて焦った. 1列に並べた時に 左端にover || 右端にunder そんなパンはないので，-1 underとoverが完全に分かれている Xがその間に置けて，1 その他 下図より，2（のはず） [展開する]