B: 交通費 - codeFlyer （bitFlyer Programming Contest）オープンコンテスト | AtCoder概略 N人が一直線に立っている。Qでcとdが与えられる Xi−c ≤d のとき、 Xi−c 円 そうでないとき、d 円 お金がかかる。 何円かかるか毎クエリ答えるN 10^5解法 累積和、…

B - Moderate DifferencesNこのマスがあり、左端にAが、右端にBが書かれている 隣接する全てのマスで、整数の差がC以上D以下に出来るか判定せよ3 A 10^9 B 10 ^9 0 自分の解法一マスごとに足した場合の区間と引いた場合の二通りの区間があるため、答えに近い…

B - Contiguous Repainting 概略N個のマスが横に並んでいて、整数aiが書かれている。以下の操作を好きなだけ行う・連続するK個のマスを全て白く塗るか、黒く塗る。黒いマスの合計を最大化したい 制約 ・1 ・1 ・ |ai| 解法 000000000 111100000 111000000 11…

B - Median Pyramid Easy 解法22のように繋がったものが中央にあれば良い。または、45のような時、隣の数がなんでも答えは4,5のどちらかになる。（中間の数がないため）それを利用して真ん中に345 のように置くと、上も同じようになる。 問題の芯 とりあえず…

B - Backfront問題 数列からいくつかの数字を前と後ろへ移動させてソートしたい。数列からいくつかを選んで、前後に動かした時、動かさなかったものは4567のような1ずつ増える数列である。つまりそのような最長の部分列を探したい。 数字の場所のインデック…

B - Minimum Sum 解法5 1 4 8 2 6 7 3 たとえば2がminで選ばれる回数は、Lが4,8,2の時でかつRが2,6,7の時なので9回ある。つまり、自分より大きくて左右で地続きになっているものの個数が分かれば解ける。初めは数を大きい順に見ていき、union-find木に入れて…

D - 3N Numbers要素数3Nの数列からN個の要素を取り除き、前からN個の合計から後ろのN個の合計を引き、それを最大化したい解法 左から大きい数をN個選び、右から小さい数をN個選びたい。この時左から選んだ物は全て右のものより左にある。 よって境界ができる…

B - Colorful SlimesN種類のスライムを最短で手に入れたい２つの操作が行える ai秒でスライムiを手に入れる x秒で全てのスライムの添字を魔法で1増やす(スライムNはスライム1になる)制約2 1 1解法初めに考え違いをした。 スライムiを手に入れる最小コストはa…

D - Simple Knapsack 1≦N≦100 1 W 10^9 1 wi 10^9 w 1 vi 10^7与えられる重さが4種類しかないナップザック [i個目を選ぶ時][選んだ個数][端数の合計を足した]の3次元で解いてみた問題の芯 範囲が広くても、複数のまとまりになっていると分かる場合は、調べる…

D - 連結 / ConnectivityD - 連結 / ConnectivityD - 連結 / Connectivity ２種類の連結が与えられ、それぞれの街で二重に連結されている街の個数を数える問題 2 解法2種類の親が同じなら、aとbは二重に連結していることがわかる。aとbのとり方は無限にある…

D: サプリメント - AtCoder Beginner Contest 017 | AtCoder 複数のサプリメントを食べる方法を考える. 1,2,3,4,3,5,2,6,5,6,7みたいな場合 0 1 2 3 4 5 6 7 8 9 10 個食べる組み合わせ 1 1 2 4 8 今日何個食べるかを考えると、自分から左へ自分を含まないと…

C - Strange Bank https://abc099.contest.atcoder.jp/tasks/abc099_c 問題概要 Nが与えられる。以下の数を足してNを作るには、最小で何回の操作が必要か 1 6 、62(=36) 、63(=216) 、… 9 、92(=81) 、93(=729) 、… また、同じ数字は何度でも使える 制約 1≤N…