D - Built? 問題概略 N個の街があり、座標(x,y)が与えられる 座標 (a,b)(a,b) にある街と座標 (c,d)(c,d) にある街の間に道を造るのには、min(|a−c|,|b−d|)min(|a−c|,|b−d|) 円かかります、最小全域木 制約 2≦N≦1052≦N≦105 0≦xi,yi≦1090≦xi,yi≦109 入力は全…

D: 買い物上手 - AtCoder Regular Contest 031 | AtCoder 問題概略アイテムの値段と、組み合わせによって得られる経験値の一覧が与えられる。アイテムをいくつか買い、得られた経験値÷使ったお金を最大化せよ。 1≦N≦100 1≦N≦100N MS1 S2 ... SNT1 T2 ... TMK…

D - ABS 問題概略 N枚のカードの山がある。プレイヤーが二人いて最初にz,wを持っている。 お互いに山札から1枚以上のカードを引き、最後に引いたカードを手札にする。 先行はお互いの差の絶対値を最大化、後攻は最小化する時のスコアはいくつか。 制約 入力…

B: Neutralize - SoundHound Programming Contest 2018 Masters Tournament 本戦 (Open) | AtCoder問題概略 要素Nの数列がある。連続したK個を0にする操作を何回か繰り返し、総和を最大化したい。制約 1≤K≤N≤2×10^5 −10^9≤bi≤10^9 入力中の値はすべて整数で…

E: MUL - AtCoder Regular Contest 085 | AtCoder 問題文 宝石が N 個あり，それぞれ 1,2,…,N と数が書かれています。 あなたは，以下の操作を好きなだけ行うことが出来ます(一度も行わなくてもよいです)。 正整数 x を選ぶ。x の倍数が書かれた宝石を全て叩…

No.421 しろくろチョコレート - yukicoder 問題概略 市松模様でサイズN*Mのチョコレートが渡される。 下記の方法でチョコレートを食べて、幸福度を最大にしたい。 ２つの繋がったチョコレートを食べる 幸福度100 離れた２つの色違いのチョコレートを食べる …

D - 壊れた電車 問題概略 N個の車両があり、M人の人がばらばらの車両にいる。 人は隣の車両に一分で移動できる。すべての車両を見て回るのにかかる最小の時間をもとめよ 制約 N(1≦N≦109),M(1≦M≦105,M≦N)N(1≦N≦109),M(1≦M≦105,M≦N) N≦100N≦100 を満たすデータ…

7/12 D - 桁和 / Digit SumD - ぬいぐるみの整理 (Plush Toys)7/19 C: Sugar Water - AtCoder Beginner Contest 074 | AtCoder7/20 D - Decrease (Contestant ver.)D - 壊れた電車7/22 D: 切り分けできるかな？ - AtCoder Regular Contest 013 | AtCoder7/29…

D - Wide Flip 問題概略 0と1からなる文字列sが与えられる。長さK以上の区間を何回か反転して全てを0にしたい。最大のKを求めよ 制約 1≤|S|≤1051≤|S|≤105 Si(1≤i≤N)Si(1≤i≤N) は 0 または 1 である 解法 K個とK+1個の反転を利用して、左からK+1個目以降のも…

E - Prefix-free Game 問題概略 0,1の高さLの完全二分木でお互いにコマを置いていく。コマが置かれた親と子は使えない。置けなくなったら負け Sn で初期配置が渡される 制約 1≤N≤1051≤N≤105 1≤L≤10181≤L≤1018 s1s1, s2s2, ..., sNsN はすべて相異なる。 {s1,…

D - Remainder Reminder問題概略N以下の整数a,bで、a % bがK以上になる組み合わせを数え上げ 制約 1≤N≤1051≤N≤105 0≤K≤N−10≤K≤N−1 入力は全て整数である 解法 ２つの組み合わせの数え上げは、片方を固定するのが鉄板。 bを固定すると、0~Nの全てのaに対して…

C - String Coloring 問題概略 長さ2Nの文字列が与えられる。各文字を青と赤に塗り分けた時、左から青を読んだときと右から赤を読んだ時の文字列が同じ組み合わせはいくつあるか 制約 1≤N≤181≤N≤18 SS の長さは 2N2N である SS は英小文字のみからなる 解法 …

B - rng_10s 問題概略 はじめAがある。そこからBを引き、もしC以下ならD追加する 何回操作を繰り返しても数がマイナスにならなければYes 制約 1≤T≤3001≤T≤300 1≤A,B,C,D≤10181≤A,B,C,D≤1018 入力される値は全て整数である 解法 まず、AがBより小さい時は死ぬ…

D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder 問題概略 N匹のうさぎがいる。xi < yi がM通り与えられる。 とりうる組み合わせをもとめろ 制約 2≦N≦16 1≦M≦N(N−1)⁄2 1≦xi，yi≦N xi≠yi (xi，yi) の組はすべて相異なる。 すべての観客の情報に合致する…

D - ぬいぐるみの整理 (Plush Toys) 問題概略 N個のぬいぐるみが一列に並んでいる。 ぬいぐるみは全部でM種類あり、同じ種類のぬいぐるみは全て連続させたい。 いくつかのぬいぐるみを選び、それらの場所を自由に入れ替えられる。 取り出す最小のぬいぐるみ…

D - 井井井 / ### 問題概略x軸と平行な直線がM本、y軸と平行な直線がN本ある このなかに存在する全ての長方形の面積の合計を109+7109+7 で割ったあまりを出力してください。 制約 2≤n,m≤1052≤n,m≤105 −109≤x1<...

D - An Ordinary Game 問題概略 長さ3以上の文字列sが与えられる。二人でゲームを行う。 sから両端以外の文字を一つ取り除く。ただし、その結果同じ文字が隣り合ってはいけない。 先に操作を行えなくなったほうが負け。 制約 3≤|s|≤1053≤|s|≤105 ss は英小文…

D - 桁和 / Digit Sum 概略 2以上のbと1以上の整数nで、nをb進数で表した時の各桁の和がsとなる最小のbをもとめよ 制約 1≤n≤10111≤n≤1011 1≤s≤10111≤s≤1011 n,sn,s はいずれも整数である 解法 制約が10^11なので全探索は間に合わない。とりあえずルートを取…

D - Two Sequences 長さNの数列 a,bが与えられる。 ai bjのN^2の全ての選び方について、ai + bjを計算しする。 それらのxorを求めよ 制約 入力は全て整数 1≤N≤200,0001≤N≤200,000 0≤ai,bi<228 解法 愚直に計算すると間に合わない。 xorは繰り上がりしないの…

調べてもあまり引っかからなかったのでまとめておきます。 座標圧縮とは与えられる範囲は大きいが、全ての値を把握する必要はない場合（たとえば#で分けられた領域の数を数える問題など）に使えるテクニックです。 ・・・・・・・・・・・・・＃・・ ＃＃＃…

D: タコヤキオイシクナール - AtCoder Regular Contest 008 | AtCoder 問題概略 N個の箱が一列に繋がって並んでおり、それらは実数(a,b)を持つ。 箱に数字を渡すとその数字は a * 渡された数 + bに変化して次の箱に渡される。 (a,b)は(1,0)で初期化されてい…

B: Sprinkler - ウクーニャたんお誕生日コンテスト | AtCoder お誕生日おめでとうございます（こっそり） 問題概略 N個の数が並んでいる。連続した数を選択して、1減らす作業がM回できる。 ただし、0は選択できない 減らした数の合計最大値を求めよう 制約 1…

D - 壊れた電卓 問題概略 K種類の数字を使う時、Aとの最小の差はなにか 制約 A(1≦A≦1015)A(1≦A≦1015) K(1≦K≦10)K(1≦K≦10) 解法 前からP桁目までをAと同じ数にして、P+1桁目をQに、それ以降をRにして全探索すればいいと分かる 問題の芯 限りなく簡単に実装し…

C: ロト2 - DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 | AtCoder 問題概略 N個の整数A1~ANが与えられる。i<jとなるAi,Ajを選んだ時、２つの積がKの倍数となる組み合わせを求めよ 制約 1≦N≦200,000 1≦Ai≦109(1≦i≦N) 1≦K≦109 Ai, K はいずれも整数 解法 N^2では間に合わない。組み合わせ問題でよくあるまとめ上げを使う。 ２つの積がKの倍数になる -> Kの約数でないものは考えなくていいため、Aたちの中からKの約数だけを取り出し、それぞれ何個あるかを持っておく。 あと</jとなるai,ajを選んだ時、２つの積がkの倍数となる組み合わせを求めよ>…

C - すぬけそだて――ごはん―― 問題概略 A以上B以下の数から0個以上選ぶ時、それらが互いに素になる組み合わせはいくつか 制約 1≤A≤B≤10181≤A≤B≤1018 B−A≤35 解法 高々35個しかないので、偶数の中から0個か1つ選び、奇数の中から選ぶ数を全探索できる(18 * 2^1…