・これまでの最大の高さ以上の時:解を1増やす&最大の高さを更新する・これまでの最大の高さ未満の時:何もしないというループをまわせば良い。よって、両方のケースについて何枚塗り替える必要があるかをそれぞれカウントし、小さい方が解となる。online.atcoder.jp解法ある一定の区間の0、1を反転させることを繰り返し、連続する1をどれだけ長く出来るか、という問題です。基本的に1を反転させる意味は無いので、出来るだけ長い1の連続を作るには、1回の操作で連続する0の区間を反転させていけば良いことが分かります。ここで、連続する0の区間がK個以下であれば、全てを1に出来るので解はNになります。問題となるのは、連続する0の区間の数がKより多い場合です。仮に連続する0の区間がL個だとすると、K個からL個選ぶことになるので、全探索だと間に合いそうに無いです。そこで、次のように考えます。1の連続を長くするには、反転させる連続する0の区間は連続していた方が良いです。以下のような並びについてK=3で考えた場合、連続する0の区間は5カ所ですが、選び方は3通りしかありません。よって、しゃくとり法などを使って前から順に見ていけば、O(N)で解くことが出来ます。通信ができないアンテナの組が存在するかどうか」は距離が最も離れているアンテナの組の距離がk以下であれば存在しないと言えます。よって、最も距離が離れるaとeの距離を比較すればよいです。各料理が10の倍数の時刻にしか注文できないということは、ある料理の調理時間がA分だとすると、次の料理を注文できるまでの時間は、「A以上の10の倍数」となります。次に「最後の料理が届く最も早く」するには、最後の料理をどの料理にするかがポイントです。調理時間が10で割り切れない料理が存在する場合、10で割った余りが最小の料理を最後に注文すれば、全体の時間が最短になります。運べる人数が少ない交通機関がボトルネックになるので、全ての交通機関の運べる人数を最少のものにそろえても結果は同じになります。全てのケーキの組み合わせを求めてから上位K個を求めると、組み合わせが109となり間に合いません。そこで次のような工夫をします。上位K個に入るものは、各キャンドルのケーキのうち美味しさが上位K個以内に入っているものの組み合わせに必ずなる「1のキャンドルの上位K個」と「2のキャンドルの上位K個」の組み合わせを全て求めてそのうち上位K個と「3のキャンドルの上位K個」の組み合わせを求めてから上位K個を求めるこのようにすれば、組み合わせはK2のオーダーに抑えることが出来るので十分間に合います。高さH、幅Wの長方形から高さh、幅wだけ除いた残りなので、(H-h)x(W-w)になります。各ソースコードiについて、それぞれ条件を満たすかどうかを判定してカウントしていくだけです。「最小で何円あればM本の栄養ドリンクを買い集めることができるでしょうか。求めるのは買うのに必要な金額なのでどの店舗でいくらの栄養ドリンクを何本買うかは特に考慮する必要はありません。各値段の栄養ドリンクが何本存在するかをまとめる(値段のリストは配列、各値段毎の本数はハッシュで管理する)安い値段の栄養ドリンクから優先的に買っていき、M本に到達したらその時点の金額が解となるという流れで実装します。online.atcoder.jp解法A、Bの範囲が最大で1012なので、実際に全ての数字を列挙してXORをとるのは時間的に間に合いません。この問題の考え方として、1bitに着目した場合のXORの特徴として以下の点を知っているかがポイントになります。1の数が偶数の場合に0奇数の場合に10の数は無関係つまり、2進数で考えた場合の桁毎の1の数がいくつになるかを考えればよいです。次のポイントは以下の式に気づくかどうかだと思います。$$図にするとわかりやすいと思いますが、以下のように0〜A-1の部分のビットは同じなので、XORをとると互いに打ち消し合って0になります。よって、A〜BのXORだけが残ります。次にf(0,A)の求め方です。これが定数時間で求めることが出来れば問題は解決です。「任意の偶数とその次の奇数のXORは必ず1になる」という性質に着目します。これは偶数とその次の奇数を2進数で表した場合に、1bit目だけが異なることから明らかです。よって、Aを4で割った余りが0の時:f(0,A)はN1の時:f(0,A)は12の時:f(0,A)はN^13の時:f(0,A)は0となります。文字列の長さが最大で10なので、前から順番に3文字ずつ選んで整数に変換し、753との差の絶対値をとっていき、その最小値を解とすればよいです。online.atcoder.jp解法300点にしては意外と難しかったです。Nは最大で999999999なので、全ての整数をチェックしていくのは現実的では無いです。3のみからなる数字がどれくらいあるか考えます。この場合、39なので19,683個しかありません。3がそれぞれ1回以上現れる必要があるので、これより少なくなります)よって、全ての七五三数を探索してN以下のものを数え上げればよいです。3がそれぞれ1回以上」というのがちょっと面倒です。3からなる整数を作っておき、後で各数字が1回以上あるかどうかを判定しています。七五数の条件である、「約数をちょうど75個持つ正の整数」について最初に考えます。これは素因数分解すると以下の形で表すことができます。p4q4r2そこで、N!の素因数分解を行い、N!の約数のうち上記のパターンで表せるものを数えていきます。N!の素因数分解は、1〜Nをそれぞれ素因数分解し、各指数部分を加算していけば求めることが出来ます。実装Rubyのpermutationメソッドを使って組み合わせを列挙し、計算結果がN!の約数かどうかをチェックして数え上げていきます。online.atcoder.jp解法1円玉には制限があり、500円玉は無制限。500円玉で払える分は最大限支払い、残りを持っている1円で払えるかを判断すればよいです。よって、Nを500で割った余りが1円の所持枚数A以下であればYes、そうでなければNoとなります。online.atcoder.jp解法AliceとBobは交互にカードを選ぶそれぞれ自分の得点を最大化するように最適な戦略を取るということは、AliceもBobも残っているカードのうち大きい数字からとっていくことになります。よって、カードを降順にソートすれば、(0インデックスで)偶数番目をAlice、奇数番目をBobが選ぶことになります。Bobの点数なので、解としては偶数番目は加算、奇数番目は減算すればよいです。online.atcoder.jp解法300点にしてはちょっと難しかったです。cとa、bの関係を表すと以下のようになります。(a1,a2,a3,b1,b2,b3)が存在すると仮定すると、aにxを足したものとbからxを引いたものも、つまり、(a1+x,a2+x,a3+x,b1-x,b2-x,b3-x)も条件を満たすことがわかります。(上の式に当てはめてみるとわかります)よって、xを調整すれば、a1が0のパターンもあり得ることになります。よって、a1を0としたときの残りのを求めることができます。求まった数について、求めるのに使った式以外の式を満たすかどうか判定し、矛盾すればNo、問題無ければYesとなります。迷路の探索問題の応用でとけます。最初に(1,1)から(H,W)までの最短経路を深さ優先探索などで解きます。最短経路のマス数)を求めれば良いです。実装のポイントとして、マスの境界値の判断ロジックをシンプルにするために、事前に外枠を黒マスで囲んでおきます。\rfloor\)になる。4種類」なので、黄色(Y)が1つでもあれば4種類、そうでなければ3種類となる。組み合わせの条件は以下の2つです。どれかから始まっている同じ文字から始まる名前を持つ人が複数いない1つ目の条件より、入力のうちM,A,R,C,Hで始まらないものは無視して良いことがわかります。2つ目の条件より、3人の組み合わせとして有効なのは、(Mで始まる人、Aで始まる人、Rで始まる人)(Mで始まる人、Aで始まる人、Cで始まる人):のような組み合わせになります。Rで始まる人の人数で求めることが出来ます。よって、最初に以下の5つの数を計算しておき、そこから3つを取り出した時の組み合わせ毎にその積をとって、その総和を出せば解になります。実装rubyで組み合わせを求める場合、配列のcombinationを使うと簡単です。online.atcoder.jp解法LからRへDずつ移動した際の距離の総和を求める問題です。L、Rは最大9万なので、距離を求めるのが1回であれば、Dずつ移動しながら移動距離の総和を出せば良いです。与えられるL、Rの組み合わせの数Qは最大105なので、都度Dずつ移動しながら距離を計算するのは時間がかかりすぎます。よって、L、Rが与えられた時に定数時間で移動距離を出す方法を考える必要があります。考え方のポイントとしては、Dは常に一定である、という点です。入力例1のように、Aが1〜9でDが2である場合、移動パターンは以下の2種類しかありません。8よって、奇数の場合は1からの累積距離、偶数の場合は2からの累積距離、を事前に求めておくことで、任意の点間の移動距離を定数時間で求めることが出来ます。計算すれば、4から8への移動距離を求めることが出来ます。online.atcoder.jp解法ワーシャルフロイド法をベースにしてその考え方を応用することで解けます。問題を「道路の構造が存在するかどうか」と「存在する道路の長さの和が最小となるようなもの」の二つに分けて考えます。道路の構造が存在するかどうか表Aが「都市間の道路に沿った最短距離を表した表」なので、表Aに対してワーシャルフロイド法を適用し、表内の値が更新されることがあった場合に表Aは矛盾することになります。(iからkへの距離)+(kからjへの距離)のような場合に、表Aはそもそも矛盾することになります。よってそのような組み合わせが一つでもあれば、’-1’を出力して終了すれば良いです。存在する道路の長さの和が最小となるようなものどのような場合に道路が存在しないといけないかを考えます。(iからkへの距離)+(kからjへの距離)のようなkが存在した場合、k経由で迂回しても距離は変わらないので、iからjへの道路は不要ということになります。よって、表のサイズと同じ表を用意しておき、道路が必要か不要かをtrue/falseなどで記憶しておき、最後にtrueな経路の距離だけ加算すればよいです。