問題：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2331&lang=jp 解答：AIZU ONLINE JUDGE: Code Review 解法：x人が参加するとした場合に、参加できる人の数を数え、それがx-1人（「私」を除くため）以上でる最も大きなxが答え。 xが与えら…

問題：C - 五目並べチェッカー 解答：Submission #13696167 - AtCoder Regular Contest 012 解法：いろいろな最終盤面が考えられるため、うまく場合分けをしてゆくことが必要。以下、各条件はそれより上の条件でYESNOが決まらなかったもののみ到達するものと…

問題：C - 積み上げパズル 解答：Submission #13676621 - AtCoder Regular Contest 010 解法：dp[i][j][k] ： i番目のブロックまで見て、直前に使った色がj色で、今までに使用した色の集合（ビットで表現）がkであるときの得点の最大値 とし、dpする。全色ボ…

問題：C - 積み上げパズル 解答：Submission #13676621 - AtCoder Regular Contest 010 解法：dp[i][j][k] : i番目までのブロックを見て、直前の色がjであり、今まで使用した色のビット集合をkとしてdpする。 計算量は n * m * 2m ≦ 5000 * 10 * 1024 < 107 …

問題：C - 高橋君、24歳 解答：Submission #13675261 - AtCoder Regular Contest 009 解法：誤って送った友達の組み合わせ数はnCk。 誤って送られた友達を(1, 2, ..., k)とすると、誤って送る送り方は1からnまでの順列(p1, p2, ..., pn)でかつ任意のiに対しp…

問題：No.7 プライムナンバーゲーム - yukicoder 解答：#487788 (C++14) No.7 プライムナンバーゲーム - yukicoder 解法：先手番の時、先手で「後手必勝」の局面に遷移する手があれば先手の勝ち、そうでなければ後手の勝ち。 dp[i] : iの時先手必勝なら1, 後…

問題：C - THE☆たこ焼き祭り2012 解答：Submission #13652774 - AtCoder Regular Contest 008 解法：投げ手をi、受け手をjとすると、iは自分が投げれる最も速い速度でかつjが受け取れる最も投げれる速い速度で投げればよいので、投げるスピードはmin(t[i], r…

問題：C - 高橋君と国家 解答：Submission #13629952 - AtCoder Regular Contest 029 解法：都市の他に交易所をノード(okn)とし、全ての都市と交易所との間に辺を考える。辺のコストはその都市に交易所を設置するときのコストとする。 すると、この問題は「N…

問題：D - grepマスター 解答：Submission #13607531 - AtCoder Regular Contest 014 解法：-B x -A yの時にどれだけ追加的にヒットするかを確認する。 1~L1まではmin(L1-1, x)個、 L1+1~L2-1まではmin(L2-L1-1, x+y)個、 L2+1~L3-1まではmin(L3-L2-1, x+y)…

問題：C - 積み木 解答：Submission #13584602 - AtCoder Regular Contest 031 解法：まず1の移動先を考えると、これは1番左か1番右になる。仮に近い方に置くとする。 次に2の移動先を考える。これは1を除いて1番左か1番右となる。つまり、先に置いた1の位置…

問題：C - ウサギとカメ 解答：Submission #13491153 - AtCoder Regular Contest 025 解法：N ≦ 2500、M ≦ 3000 なので全点ダイクストラやっても間に合いそう。(TLEも7秒) 目的地を固定して、目的地を始点とするダイクストラをする。すると目的地から各中継…

問題：F - Select Half 解答：Submission #13466424 - AtCoder Beginner Contest 162 解法： こちらのブログを参考にしました。考察が綺麗すぎて感動です。 betrue12.hateblo.jp まず、連続しないぎりぎりで数を選ぶことを考えます。oxoxoxoのような選び方で…

問題：No.801 エレベーター - yukicoder 解答：#484275 (C++14) No.801 エレベーター - yukicoder 解法：エレベーターiはLi階からRi階を移動する。すなわち、Li ≦ j ≦ Ri なるj階から、Li ≦ l ≦ Ri なるl階に移動する。よってこの足し算をまとめて行う必要が…

問題：No.458 異なる素数の和 - yukicoder 解答：#483584 (C++14) No.458 異なる素数の和 - yukicoder 解法：20000までの素数のリストを作成する。20000までの素数の個数は2262個。 dp[i][j] ： i番目の素数までを使い、残りの数がjであるときのこれまで使っ…

問題：No.914 Omiyage - yukicoder 解答：#483578 (C++14) No.914 Omiyage - yukicoder 解法：dp[i][j] ：i番目の国まででお土産を買ったとき、残金をjにすることができるかのbool でdpする。 dpの遷移は、各iについて、残金jのとき、その国のお土産lを変え…

問題：No.533 Mysterious Stairs - yukicoder 解答：#482595 (C++14) No.533 Mysterious Stairs - yukicoder 解法：dp[i][j] を今i段目にいて、直前でj段上ったときの通り数としてdpする。 dpの遷移は配るdpとして if(j != 1) dp[i+j][j] += dp[i][1] のよう…

問題：No.800 四平方定理 - yukicoder 解答：#481517 (C++14) No.800 四平方定理 - yukicoder 解法：半分全列挙。等式を移行するとx2 + y2 = w2 - z2 + D となるので、両辺全ての組み合わせを列挙し、一致するものの個数を数える。mapだとTLEしたので配列を…

問題：No.875 Range Mindex Query - yukicoder 解答：#481502 (C++14) No.875 Range Mindex Query - yukicoder 解法：(数値, インデックス)をペアにしてセグ木に入れる。

問題：F - Three Variables Game 解答：Submission #13217763 - AtCoder Beginner Contest 166 解法：再帰で通った。計算量要確認。

問題：No.871 かえるのうた - yukicoder 解答：#481008 (C++14) No.871 かえるのうた - yukicoder 解説：貪欲だけど注意点が多い。 左端と右端を保持しながら鳴くカエルが増えるたびに左端と右端を更新する。注意が必要なのは、より右のカエルが鳴くことで左…

問題：F - Bracket Sequencing 解答：Submission #13137686 - AtCoder Beginner Contest 167 解法：'('でインクリメント、')'でデクリメントする変数lを準備する。各文字列についてこの変数が途中でとりうる最小値、最終値のタプル(m, f)が肝となる。 f ≧ 0 …

問題：No.806 木を道に - yukicoder 解答：#480139 (C++14) No.806 木を道に - yukicoder 解法：Σ max(deg(v) - 2, 0) が答え。 辺のつなぎ変えは変更前の頂点の次数を1つ減らし、変更後の頂点の次数を1つ増やす。作成したいグラフの次数列は(1, 1, 2, 2, ..…

問題：E - Active Infants 解答：Submission #12999465 - AtCoder Beginner Contest 163 解法：dp[x][y] : 左にx人移動させ、右にy人移動させたときの活発度の合計の最大値、としてdpする。移動させるのは活発度が大きい順で、左・右から詰めるように移動さ…

問題：No.949 飲酒プログラミングコンテスト - yukicoder 解答：#479694 (C++14) No.949 飲酒プログラミングコンテスト - yukicoder 解答：Ｋ問解けたとする決め打ちの二分探索。 もしK問解いたとすると、Dを昇順ソートしてK, K-1, K-2, ..., 1番目の問題か…

問題：No.978 Fibonacci Convolution Easy - yukicoder 解答：#479634 (C++14) No.978 Fibonacci Convolution Easy - yukicoder 解法：下記の足し算。 a1 * a1 a2 * a1 + a2 * a2 a3 * a1 + a3 * a2 + a3 * a3 これはsm = a1 + a2 + a3 + ... + an, diag = a…

問題：No.816 Beautiful tuples - yukicoder 解答：#479612 (C++14) No.816 Beautiful tuples - yukicoder 解法：3数の条件はA | (B + C)、B | (A + C)、C | (A + B)である。3番目の条件より、A + Bの約数を全て調べ、条件が満たすものの最小値を出力すれば…

問題：L - Lexicographically Minimum 解答：Submission #12939716 - 第二回 アルゴリズム実技検定 解法：後ろからぎりぎり作ることを考える。最後の1つはa[n-1]で作ればよい。その前はa[n-1-d]までで作る必要がある（そうでないと間隔がdとれない）。その前…

問題：J - Parse 解答：Submission #12846967 - 第二回 アルゴリズム実技検定 解法：実際に文字列を構築する。再帰でうまくやると出来るように感じたが、実装が思いつかなかったため、ループ + 配列で実装した。

問題：K - Parentheses 解答：Submission #12875879 - 第二回 アルゴリズム実技検定 解法：dp[i][j] ：i文字目までで、「'('の個数」 - 「')'の個数」 = j の場合であるときに費やした最小コスト、でdpする。 dp[i][j]からの遷移を考える。 次の文字が'('の…

問題：I - Elimination 解答：Submission #12845732 - 第二回 アルゴリズム実技検定 解法：実際にシミュレーションを行ってゆく。各人が負けた時点で結果を配列(res)に保存してゆく。