メモ できなかった... C-sum(low[i])がどの箱に入ってるかわからない。 最悪なケースは選ばない箱にどこに入ってるかわからない飴ができるだけ入っている状態。 良い選択方法としては ・lowが大きい順に選ぶ->選ぶ箱に最低限入っている飴を多くしたい or ・h…

メモ tasteが正なら絶対食べた方が良い tasteが負の場合はそのハンバーガーを食べることで種類が増えるなら、食べるとjoiを大きくできる可能性がある tasteが負のハンバーガーしかない種類については、tasteが一番大きいハンバーガーだけを食べるか食べない…

メモ Possibleの場合 xとyの和は ± 30 ± 31 ± ... ± 3k なので、x座標かy座標どちらかが3の倍数+1or3の倍数-1になる 余計な1を消して3で割ると ± 30 ± 31 ± ... ± 3k-1 となり、x座標かy座標どちらかが3の倍数+1or3の倍数-1になる これを繰り返していくとx=0…

メモ Atcoderの D - ABS と似た考察でいけた。 先攻が3ターン目以降で良い点数を狙うことができない系の問題。後攻が2ターン目で得られる最小の得点で終了させるから。 なので1ターン目で終了する時の最大値を出力すればOK。 今回は葉の頂点の中でのコストの…

メモ 動的計画法。 dp[i+1][j] := i個目まででレートがjの時の色が変わった回数の最大値とする。レートjにならない時は-1とする。 レートは109以上になるため工夫しないとTLE。 2200以上が2回以上続くことが禁止されているため、2200未満のレートだけ考えれ…

メモ n個の袋から取り出したappleとorangeを合わせた時、appleとorangeの個数が(a,b)になる（a+b=nX）。 それぞれの袋にappleとorangeがそれぞれX個以上あるならそれぞれの袋からX個取り出すときは、 合わせると(nX,0),(nX-1,1),...,(0,nX)となるのでnX+1通…

解法 N <= Aの時 絶対に先行が勝つ N > Aの時 A > Bの時 N > A > Bであるため先攻が1個だけとる戦法をとると絶対にN > Bにできる。N <= Aになったら全部取れば良い。よって先攻が勝つ。 A < Bの時 N > B > Aである。A > Bの時と同様に考えると、後攻が絶対勝…

解法 愚直にシミュレーションするとB≦109なのでTLEしてしまう。 操作を十分な回数行うと、一番小さい数にAをかけると一番大きな数になる状態ができる。 この状態になれば周期性を利用してとくことができる。 この状態になった時の数列が{a'}で残りの操作回数…

解法 variety setを何個売るか決まれば、同じ色のパッケージを何個売らないといけないか決まる。 variety setを何個売るかで全探索。 コード class PackingBallsDiv2 { public: int minPacks(int R, int G, int B) { int ans = 1e9; // variety set for(int …

解法 どんな文字列でも"A"or"B"or""の3種類のどれかにすることができる。そのため無限にある文字列を"A"にできる文字列、"B"にできる文字列、""にできる文字列の3つのグループに分けることができる。"A"にできる文字列は逆に"A"から作ることができる。"B"、"…

A - Time Penalty 最大値出力。 #include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> #include <cstring> #incl…</cstring></bitset></stdio.h></stdlib.h></vector></string></stack></sstream></set></queue></cmath></map></iostream></cstdio></algorithm>

解説 wa = a_iを含む良い集合の和の最小値とすると、 wa - a_i ≧ K <=> a_i は不必要 wa - a_i < K <=> a_i は必要 となる。 全てのカードiについて、カードiを含まないカードで作れる和をdpで調べる。 dp[j][k] = カードjまで調べたときに和kを作れるかどう…

解説 できるだけ一文字目の方に大きい文字(z,y,x,...,a)を作っていく。繰り上げしていくイメージ。 Ai C[S_i] + Ai+1 C[S_(i+1)] => Ai (C[S_i] + A) + Ai+1 * (C[S_(i+1)] - 1)。 N文字目から繰り上げできるだけしていく。 コード #include <algorithm> #include <cstdio> #inc</cstdio></algorithm>…

解説 a,...,zを頂点としてトポロジカルソート。 頂点数が少ないので、O(N3)のアルゴリズムでOK。 トポロジカルソートの参考サイト。 Topological sort コード #include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #</stack></sstream></set></queue></cmath></map></iostream></cstdio></algorithm>…

解説 dp[i][j] = i人未満のグループのみで、j人を分ける通り数とする。 このようにdpを定義すると、dpの更新式は以下のようになる。 i人のグループを一個も作らないとき、 残りのN-j人のうち、i人のグループをk個作るとき、 で割るのはグループを区別しない…

TopCoder Statistics - Match Overview 問題概要 文字列Sの中に回文が何個あるか 制約 |S| ≦ 5000 解説 文字列Aが回文の時Aの両サイドに同じ文字が連結した文字列も回文となる。 同じ文字でない文字が連結したらその時点で回文では無くなる。 回文の中心がsi…

TopCoder Statistics - Match Overview 問題概要 Aさんが1以上1000000000以下の数字を思い浮かべる BさんがAさんが思い浮かべた数字がx1,x2,...,xnかどうか聞く Aさんは思い浮かべた数字とxとの差の絶対値yを答える Aさんが思い浮かべた数字が一意に定まる時…

TopCoder Statistics - Match Overview 解説 1 * 1, 2 * 2, ...の正方形が作れるかどうか順に調べた。 左からi右からjのマスが正方形の左上として調べた。 コード class AlienAndGame { public: int getNumber(vector <string> board) { int H = board.size(); int W</string>…

問題概要 step k でx方向かy方向に3k進む stepは0から始まる xとyが与えられるのでその座標にちょうど到達できるか判定せよ 制約 0≦x≦109 0≦y≦109 解説 319 = 1162261467なので高々19ステップで制約の座標には到達できるかどうかわかる。 各stepでx方向に行…

TopCoder Statistics - Match Overview 問題概要 要素数が偶数の配列Aが与えられる Aの要素2つを選んでペアを|A|/2個作る ペアの積がX以上となるようなペアの最大数を求めよ 制約 |A| % 2 = 0 -109≦A≦109 -109≦X≦-1 解説 Xが負であることがポイント。 偶数偶…

やり直し B: Mysterious Light - AtCoder Grand Contest 001 | AtCoder 正三角形中の光の経路の長さを求める問題。 解法 f(a, b) := 辺の長さがaとbの平行四辺形の中を光が、2回反射するまでに進む距離とする。 2回反射する時点でまた平行四辺形ができる。 a …

100-200-300-400だったので全完できた！ 実装がいつものABCより重い気がした。 A - One out of Three A - One out of Three A == BならCを出力 B == CならAを出力 C == AならBを出力 int main() { ios::sync_with_stdio(false); cin.tie(0); int a,b,c; cin …

D: 射撃王 - AtCoder Beginner Contest 023 | AtCoder 解説 最小値をx[m]以下にできるかどうかで二分探索。 tを風船iがx[m]を超えない時間とすると、 H_i + t * S_i = xより、 t = (x - H_i) / S_i となる。これが風船iを割らなければいけない制限時間である…

やり直し B: Reverse and Compare - AtCoder Grand Contest 019 | AtCoder 問題概要 英小文字からなる文字列A(|A|≦200,000)が与えられる Aの英小文字2つを選んでそれを両端とする文字列を反転させることを1回まで行う 何通りの文字列ができるか 解法 A = abc…

Differential Pulse Code Modulation | Aizu Online Judge 解説 dp[i][j] := i個目の信号まででyがjのときの最小値 コード #include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include </vector></string></stack></sstream></set></queue></cmath></map></iostream></cstdio></algorithm>

やり直し D: An Ordinary Game - AtCoder Regular Contest 064 | AtCoder 解説 ゲームが終了する直前に文字列がどうなっているか考えると良い。(頭いいな〜) 両端が同じ時 abab...a ->直前は奇数個 よって与えられた文字列が奇数の時はSecondの勝ち（firstと…

DISCO presents ディスカバリーチャンネル コードコンテスト2017 予選 - AtCoder ABCの3完、Dは方針はあってたっぽいけど実装が詰められなくて死亡。234位。19年卒じゃない枠で100位以内は本戦だけどきついな〜。 A - DDCC型文字列 やるだけ。 int main() { …

やり直し B: 難易度 - AtCoder Regular Contest 043 | AtCoder 問題概要 難易度Diの問題がN個ある 以下の条件を満たす4問を選ぶ選び方は何通りか 2 問目の難易度は 1 問目の難易度の 2 倍以上である 3 問目の難易度は 2 問目の難易度の 2 倍以上である 4 問…

やり直し C - 高橋君、24歳 問題概要 N人に手紙をそれぞれの人の宛名で出そうとしたが、K人は自分の宛名ではない手紙がきてしまった。手紙の渡し方は何通りあるか。1,777,777,777で割った余りを求めよ。 2≦N≦777,777,777,777,777,777 2≦K≦777,777 解法 Nがめ…

やり直し D - 食塩水 解説 平均を最大化する問題->二分探索 wiグラムの濃度pi%の食塩水をk個混ぜた時の濃度は、 これがp以上となる時は を満たす。 変形すると、 濃度がp以上の食塩水を作れるかどうかは、 の値が大きい容器からK個選んで0以上となっていれば…