URL https://community.topcoder.com/stat?c=problem_statement&pm=13846&rd=16548 概略 $R \times C$ のマス全てをちょうど $K$ 回だけ通るような一筆書きの経路は存在するか？ 方針 $K = 1$ で巡回路が作れれば，$K > 1$ についても構築可能です．巡回できないケースは $R$ と $C$ の両方が奇数の場合のみです．これが真に構築不能であることの証明ができなかったので参考リンクを貼っておきます． 巡回路ができないことの証明 yukicoder : No.85 TVザッピング(1) — kmjp’s blog 構築不能であることの証明 TopCoder SRM 668 Div1 Easy PaintTheRoom — kmjp’s blog [展開する] 反省 そこそこ自信はあったが証明はできていないので，本番ですぐに提出できるかは微妙．
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=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=11359 概略 "000000000"～"999999999"のうち，goodSuffixesを含むものを当たりとするときの当選確率を求める． 方針 単純に数えると重複が生じることに気を付ける．集合を意識すると良い． goodSuffixes={"47","4747"}とすると，"4747"$\subset$"47"なので"4747"を数える必要はない． そこでgoodSuffixesを桁数の小さい順に並べて，集合の大きい方のみを数えるようにする． 追記: 昔のコード酷すぎるな．whileのくだりはusedかなんかで管理したほうが絶対良い． [展開する] テストおわったのでしっかり精進します
URL http://community.topcoder.com/stat?c=problem_statement&pm=11284 概略 初期スコアを0として2種類の行動を任意の順番で行う． A: scoreAを足す． B: scoreBを掛ける Aを $nA$ 回，Bを $nB$ 回行うときのスコアの最大値を求める． 方針 1年生 (A First Grader) — Aizu Online Judge を解いた経験からDP解を思いつくも，うまくいかない．しぶしぶ考察すると，「足してから掛けたい」「正負は融通が利くので絶対値を大きくしたい」など思いついたため，全部入れ込んだ．場合分けはコードを参照． [展開する] 追記：他人の解法が鮮やかすぎて直視できない
URL https://community.topcoder.com/stat?c=problem_statement&pm=11342 概略 このゲーム，言語化が難しい． $N$ 人には0-indexedで番号が振られている．またvulnerableには最初 $N$ 人全員がいる． 以下の手順でゲームは進行する． vulnerable内で $N$ 票を振り分ける． vulnerable&&decisionsの人はdecisionsで宣言された分だけ得票する． vulnerable={0,1,3}，decisions={0,1,1,2}の場合，0は1票，1は2票を得る．2はvulnerableに含まれないので得票しない． 上で $k$ 票消費されたとする．余った $N-k$ 票は得票数の最小値が大きくなるよう，均等に振り分ける． 5人の得票数が{1,0,3,2,1}で残り5票ある場合，以下のように分ける． {1,0,3,2,1}→{1,1,3,2,1}(1票消費)→{2,2,3,2,2}(4票消費)→{3,2,3,2,2}(5票消費) ただし5票目に選ばれる人物は2票得ている者の中からランダム 票数の最も大きい者のみがvulnerableに残る． vulnerableが1人になるまで投票を繰り返す．最後に残った1人が敗者となる． 各人が敗者となる確率を $p[i]$ としたときの $\max p$を計算する．なお，ゲームが終わらない場合には0を返す． 方針 「ゲームが終わらない」というのは，ゲーム中のある時点でvulnerableのサイズが不変，つまりvulnerable内の得票数が全て等しくなるということである．この判定法は投票の回数で異なる． 投票1回目 vulnerableには $N$ 人全員がいるので，decisionsに複数現れる人物がいない場合，全員の得票数は1となってループ. 投票2回目以降 decisionsに係る投票を終えた時点で，vulnerable内の得票数は等しい（そういう風に投票1回目で分けます）．残りの票を振り分けたときに同票であるとループする．vulnerableのサイズを $i$ とするとループの条件は、$N\equiv 0\pmod i$ ループの条件がわかったのでシミュレーションができる．敗者は1回目の投票後にvulnerableにいる人のいずれかであり，彼らに区別はない．よって確率は、$1/i$ [展開する]