chokudaiさんがtwitterでコメントしてたので適当に実装 追記：逆ポーランド全列挙でゴリ押したほうが早そう string f(vector<string> v) { if (1 == v.size()) return v[0]; string ret = "("; rep(i, v.size())ret += v[i]; ret += ")"; return ret; } void solver(</string>…

21.？？？ 問題の意味を理解できず22.★★ {1,4,9}{2,6,12}{3,5,15}{7,8,14}は積が平方数になり共通部分を持たない なので最大は高々15-4であり 11が構築できるなら{10,11,13}は含まれる {1,4,9}{7,8,14}{2,5,10}{6,15,10}は積が平方数になる 組み合わせると{3…

上級問題 ★は５段階評価 11.★★ 問題の設定を理解するのにめちゃめちゃ時間がかかる 大きいものから考えていく12.★ 2冪で考える 2048枚あったとして96回の操作が経過したところからスタートしたと思えばいい (2^10-1)-9692713.★ 2*2のマスは1999*2001個数ある…

上級問題 ★は５段階評価 1.★★ 合計を二通りの方法で表す。 全員の得点の合計は、試合の結果に関わらず一試合で1なので(0+1,1/2+1/2,0+1) Σai=Binom(n,2) 下位同士での勝ち点の合計はBinom(10,2)であり、これが合計の半分になることより Σ下位=Binom(n-10,2)*…

組合せ論の精選 基本問題51 解法メモ 01. 簡単な計算をします02. 丁寧に計算をします03. 二項係数の和が2^nになること 合計が奇数なら奇数が奇数個あること04. 包除原理をします05. 丁寧に計算をします 二問目とほぼ同じ06. 連続する同性をブロックにしてみ…

更新してなかったのを思い出したので 8問abcは再走するには後半が重すぎるので、この企画(?)の最終記事になります。■206F - Interval Game 2 区間dp+Grundy数 [0,100)から初めて取れる区間[l,r)を取る [0l)と[r,100)に分かれる Grundy数なのでxorを取ればい…

ARCメモ 回数:配点:writer 163:3,4,6,7,9,11:PCTprobability(7) 162:3,5,5,7,7,9:tatyam(1), nok0(3) 161:3,4,5,5,8,9:ygussany(2) 160:4,5,5,7,8,9:PCTprobability(6), Nyaan(3) 159:3,4,5,6,9,9:m_99(2) 158:3,5,5,8,8,9:maspy(9) 157:3,5,6,6,7,9:ygussan…

201の自分の解放メモ見ても全くわからなくて ここの存在意義を見失いかけた。 橙diffだし仕方ないよね。■201F - Insertion Sort 固定する、ソート後の一番右の要素をiとする それより右のものは動かす必要がなくても動かすこととする すると dp[i] = 固定す…

ここら辺りからFがまた黄diffに戻る。 ABCの復習に飽きてきた。 ■196F - Substring 2 経験則で畳み込めば解けそうな事がわかる。 xorを掛け算の形に分解したい a xor b = a*(1 - b) + (1 - a) *b を使う。■197F - Construct a Palindrome 偶数長と奇数長の回…

ここら辺りからFがまた黄diffに戻る。■191F - GCD or MIN答えになるのはAの最小値以下かつ、適当に選んでgcdとなるもの全て。gcdがxになる選び方があるかを考える。xの倍数全てを拾ってきてgcdを取れば良いこれでxにならないならxの倍数全てが、x*pを因数に…

この辺りから参加記を書き始めたみたいですね。■186F - Rook on Gridこれギリ黄色あっても良くないですか？縦に行って横か、横に行って縦かまず縦にいって横のケースをすべて求める。そのあとに横に行って縦で濡れるところを求める。これはセグ木で区間和を…

Fが異常に易化していた時期の前半■181F - Silver Woodsunionfind釘と壁とで距離が近いものをどんどん結んでいくその状態で上の壁と下の壁が同一グループなら通行不可 ■182F - Valid paymentsメモ化再帰桁dpサンプル1,5,10で9を払う9->10 or 510->105->0,10 ■…

★自力ACだが難しめ★★twで拾ったヒントAC★★★解説AC★★★★最難★★★★★真最難01：二分探索：1000~120002：dfs：1000~120003：木の直径：1000~120004：累積和：200~40005：行列累乗：1600~1800★06：dp：1200~140007：lowerbound：800~100008：dp：1000~120009：幾何…

■176F - Brave CHAINdpO(n^3)は明らかにTLEする。一回の操作毎に更新する部分は高々しれているので更新箇所だけメモしておいて、後で更新分だけ更新すれば良い。xy+abc->???と遷移させる中でxy+aaa->xyaa+abc->bcaa+abb->bbbb+aab->aaが+1されるケース。この…

■171F - Strivoreoofに5文字挿入**o**o**f**とでもして最後以外は25種を最後は26種類をいれれるf1 = 1 + 25x + 25^2x^2 + 25^3x^3..............f2 = 1 + 26x + 26^2x^2 + 26^3x^3..............f1^N * f2の係数が答え f1 = 1/(1-25x)f2 = 1/(1-26x)f1^k = Σ…

■166F - Three Variables Game構築は苦手a+b+c=0は明らかNGa+b+c=1は打てる手が一択なので簡単a+b+c>=2は基本的に大きい方から小さい方に移せばいい。1,1,0で(1,1)が選ばれたときは次のターンに支障がないように動く ■167F - Bracket Sequencing括弧列の成立…

■161F - Division or SubtractionN = 1+ nk を満たす２以上のものN = (nk+1)*k^n ■162F - Select Halfナップサックdp[i][j]:=i番目まで見た、j個を条件を満たすように採用しただとO(n^2)かかる問題条件より、一つ空けて選ぶこと＋ほぼ半分選ぶなので上のdpの…

■156F - Modularnessこれも難しいね。サンプルをベースに説明すると3,6,7,11,14でmodを取ると1,0,1,1,0なりansは1 aに足されるdは最初からmodをとってから足しても変わらないので3,4,5,5,6と同じこうするとn項目とn+1項目の差はd未満なのでanとan+1をmodで割…

■151F - Enclose Allとりあえず二分探索なのはあきらか。半径が最小になるときは、少なくとも２つの点が円の円周上にある。なので二点から距離rの点を中心の候補とし、すべての点が収まるかを確認する。 ■152F - Tree and Constraints制約を見る。NとMが少な…

■146F - Sugoroku 単純にdpをするとO(NM)かかる 貰うdpで考えると結局欲しいのは区間minなので セグ木におまかせする。 ■147F - Sum Difference 選ぶ個数に着目する。 数列が(4,6,8,10)だったとすると２個選ぶ場合：10,12,14,16,18 ３個選ぶ場合：18,20,22,2…

■141:F - Xor Sum 3 これ、難しくないですか？ xorなので、当然bitごとに考える。 入力例２をもとに考える 23:0010111 36:0100100 66:1000010 65:1000001 である。 32,16のような奇数本bitが立っているものは どう振り分けようが、答えもbitが立つので考える…

■136:F - Enclosed Points(2334) とりあえず図示してみる。 問題文を言い換えて、それぞれの頂点ごとに自分が含まれるような部分集合の場合の合計を求める。 自分自身が選ばれていれば残りのN-1個の頂点はどうでもいいので2^(N-1)が加算される 次に、自分自…

■131:F - Must Be Rectangular!(1937) X座標、Y座標を二部グラフの問題と解釈し、unionfindで同グループの結ばれていない辺の個数が答え 類題：D - Skate(arc112) ■132:F - Small Products(2143) 状態をまとめて計算量を減らすdpdp[i][j] := 最後がjで条件を…

■126:F - XOR Matching(1770) まず 0 = 0; 0 xor 1 = 1 以下、 0 xor 1 xor 2 xor ,,,,,,,,,,,, 2^N -1 = 0 です。 これに気がつくと 0,1,2,3....K-1,K+1........2^M-1,K,2^M-1,,,,,K-1,K+1,,,,,3,2,1,0,K のように構築すれば良いことがわかります。 構築で…

■51:C - 掛け算 ある程度まで揃えてから、 全てに同じ数を掛ける■52:C - 高橋くんと不思議な道★★★ 難しかった。 枝刈りダイクストラ。 O(N^2)だとTLEするので、なにかの工夫が必要 まず特定の頂点に到達するまでにタイプBの辺を最低でも何回使う必要があるか…

■41:C - ウサギ跳び 方針的には簡単だが、実装が少し面倒 端っこの処理を上手にやらないと事故が起きる。 ■42:C - おやつ ナップサック 一番安いものを覗いて予算内に収まればいいので 入力情報をソートしてdpを使い回すといい ■43:C - 転倒距離★★★ 配列Aは0…

■031:C - 積み木BIT ■032:C - 仕事計画dp後ろから決めていく ■033:C - データ構造セグ木の更新とセグ木上の二分探索 ■034:C - 約数かつ倍数A-Bが小さいのでA+1,A+2,,,,,Bそれぞれを素因数分解した結果からA+1,A+2,,,,,Bをかけ合わせた数の約数の個数を求めれ…

■021:C - 増築王高橋君★★★二分探索オーバーフローの罠が２つもある ■022:C - ロミオとジュリエット 木の直径はdfsして一番遠いところを求め、そこからさらに一番遠い点を探せばいい ■023:C - タコヤ木サンプル２62 -1 -1 9 -1 9 2 -1 -1 9は2 -1 -1 12として…

■011:C - ダブレット各単語間ごとに経由が出来るなら辺を貼りbfsをする。到達可能なら結果から復元 ■012:C - 五目並べチェッカー 面倒。ちまちまするだけ。 ■013:C - 笑いをとれるかな？問題が長い。読むとnimをしろと書いているのでやる。 ■014:C - 魂の還…

■001:C - パズルのお手伝いnext_permutationをして8!すべてを調べる ■002:C - コマンド入力Lに割り振られるのは16通りRも同じく16通り全部試しても256通りそれぞれをdp ■003:C - 暗闇帰り道解の二分探索dfsパートはテンプレだけど、解の二分探索は経験がない…