2019-02-01から1ヶ月間の記事一覧
E - Independence解法 辺で繋がっていない都市は、別のグループに属さないといけない よって補グラフが二部グラフでなければ答えは-1二つの集合サイズを均等に分けると答えが最小になる これは、ナップザックにより解ける グラフは複数の二部グラフに分けら…
E - Symmetric GridPItS さんのコードを参考にしました ARC095 E : Symmetric Grid(700) - PItS' Buffer Solution解法 まず列の並び方を決めた後、全ての行に対応する行があるかを判定するまた、列の並び替えは全て試す必要はなく、ペアを決めるだけでいい具…
No.794 チーム戦 - yukicoderこの手の一つ一つ選んでいく問題は、選ぶ対象が単調増加していくように設定すれば解ける ソートして大きい順に見ていくと、選べる相手はあるv以下の数であり、このvは単調増加のため解けた類題 F - チーム分け D - Double Landsc…
F - Normalization操作において、不変の値に気付けると強いの意味が分かったabcを012とするとmod3上で合計は変化しない 自明に作れないケース以外はうえで作れる nが3以下の時はどの操作でも真ん中が使われるため例外的に全部は作れないSubmission #4271328 …
E - Tozan and Gezanまずaiがbi以下なら限界まで取ったほうがよさそう 残ったaj > bj なる任意のあるjについてj以外が０になるまで選べる なぜならとざん君がjを取らない限りa[j] > b[j] が保たれるためよって答えは全体の合計からa[i] > b[i]なる最小のb[i]…
E - Both Sides Merger「どちらの操作も全体の合計から自分を引いている」 という事を利用するのかと思ったが、持てる合計を書いてみると最終的な合計に偶数番目と奇数番目が含まれることはないとわかる また、偶奇上なら自由に選べる Submission #4267606 -…
E - Avoiding Collision二人が最短で動く方法から出会う組み合わせを引くsからtへの最短距離をdとする すると二人が出会うのはd/2移動したときところで、ある頂点iにいる時の時刻は一定なので diss[v] := sからvへ移動するのにかかる時間 dist[v] := tからv…
E - Bichrome Tree解法 木のdpを考えたくなる頂点iの色をai、違う色をbiとする 頂点i以下でaiの合計はXiであり、biの合計は自由であるよってdp[i][bsum] := i以下でbiの合計がbsumとなるものが作れるか としたくなったが、計算量が多すぎるここでbsumは小さ…
Submission #4195664 - AtCoder Regular Contest 0812*2の時について考えると 黒の合計が偶数の時のみ全てを黒くできるとわかる また、この領域からなる長方形も全て黒くできるなぜなら、どのような操作をしても2*2正方形内の黒は偶数個あり 左端と上を黒く…
E - guruguruお気に入りを使わなかったときに比べて、それぞれのお気に入りボタンで答えがいくつ少なくなるかの表 サンプル1 分かりやすさのためm+1は1として扱う fからtで移動する際、f+2からtにかけて-1 -2と増えていく これは下のようにいもす法を二回使…
E - Connected?よく考えると端同士が繋がれてるもののみ考えればいいとわかる その中で、全ての線が交わらなければYes時計回りで見た時に123321のように対応が取れていれば繋げるため、スタックの要領で溶ける(kmjpさんのコード参考) Submission #4184430 - …
E - Frequency最大の石を減らすには、石の数×高さの回数が必要になる この操作をシミュレートする 自分と同じ高さの場所の数と二番目に高い物の位置が必要になる pairに（石の高さ,インデックス）を持たせて降昇順にソートすると石の数と最小のインデックス…
E - Frequency最大の石を減らすには、石の数×高さの回数が必要になる この操作をシミュレートする 自分と同じ高さの場所の数と二番目に高い物の位置が必要になる pairに（石の高さ,インデックス）を持たせて降昇順にソートすると石の数と最小のインデックス…
E - Snuke Lined毎に行ける駅をm log nで見れる 累積和を使えば各駅に置かれる名産品の数がわかる ここで、dで行ける駅について名産品の数を加算していくと名産品が重複してしまうなので、区間の長さがd以上の名産品は必ず取れることと、区間の長さがd未満の…
E - 高橋君とホテル / Tak and Hotelsホテルiからd日で移動できる場所は、「現在地点から距離がLを超えない範囲で移動する」をd回繰り返した場所です 全てのiについて1日で移動できる場所は二分探索でO(log n) よってダブリングが出来て二分探索しますまた左…
E - 和風いろはちゃん / Iroha and Haiku余事象を考えるとわかりやすい 桁毎に全探索するメモ化で解く ある桁iで使える数vは、iを右端としたときに575とならないようなvだが これは右端から数の累積和を取ってbitに持たせれば575になるか判定できる 18以上の…
