ABC/ARC
https://atcoder.jp/contests/arc059/tasks/arc059_c 問題概要 N人の子どもがいる。それぞれ、はしゃぎ度という整数値A[i]があるとする。 この時、それぞれの子どもが飴をB[i]個もらっているとき、全体の活発度は以下のように求められる。 $$ \Pi _ {i = 1} …
atcoder.jp 概要 Nが与えられる。最初がx=1で、高橋君と青木君が交互に次の操作のうちのどれかをする。先手は高橋。 xを2xにする。 xを2x+1にする。 自分の番で操作してNを超えたらその人の負け。Nが与えられるので、その時が誰が必勝なのかを答えてください…
atcoder.jp 概要 m段階の明るさを調節できるランプとリモコンがある。1回リモコンの「進む」ボタンを押すと、明るさが1段階上昇、一番上のレベルmの場合はレベル1に戻る。 もう1つ、「ショートカット」ボタンがあり、これは1回押すと、事前に決めたX段階の明…
atcoder.jp 概要 任意の自然数r, cを使って、(i==r && j = c)の部分を1円をかけて塗ることができる。 N*Nのグリッドが与えられて、そのうちのいくつかが既に塗られてるかもしれない。既に塗られたものに上書きにして塗ってもよい。 この時、全部塗り切るのに…
atcoder.jp 概要 Nの長さを持つ数列がある。(N
atcoder.jp 概要 ナップサック問題を解く。一つだけカバンに入れず持ち歩ける。個数は3000個まで、価値、重さはそれぞれ[1, 3000]、入れられる最大の重さは[1, 3000]。最大の価値は？
atcoder.jp 概要 最大30万枚のかーどがあたえられ、一枚のカードにはそれぞれ1~30万の数字がある。あなたはこの中からK枚のカード選び、それらを取り除く。この操作は何回できるだろうか？ただし、Kは1からNまですべて試しそれぞれ出力すること。
atcoder.jpこの問題から、次のような一般化された問題を考える。 問題文 N個のものを考える。高速でそのうちの1つを抜いた時の計算結果を求める。
atcoder.jp 概要 N(N )個の町をM(M )本の道がつないでる。それぞれの道には距離D(D )が設定されてる。あなたの車は最初燃料L( L )まで積んでおり、距離1走るごとに燃料1を消費する。町で燃料の補給ができるが、道の途中で燃料を切らしてはいけない。Q( Q )個…
atcoder.jp 概要 二回のコンテストが行われ、それぞれの参加者は∞人いた。高橋くんは一回目でa位、二回目でb位を取った。 この時、スコアをある参加者の二回のコンテストの順位の積と定義する。 高橋君よりスコアが上の参加者は最大何人いるのだろうか？ AC…
atcoder.jp 概要 文字列S, T(長さが最大 10^5)は'A', 'B'のみで構成されてる。 あなたは、 1. A -> BB , B -> AAに置換 2. AAA ->(nothing), BBB -> (nothing) と、3つ連続の同じものを消す ことを好きな回数だけ行える。この時、Q回(1 Sの[a, b]をTの[c, d]…
atcoder.jp 問題概要 長さNの数列で、1 区間において、すべての要素のxorと和が等しい(l, r)の組の数を数え上げよ。N
atcoder.jp因数定理の合同による式変形を知っていれば命題の同値条件でサクサク行く問題であった。その先にも少してこずるものもあり、800点としては妥当だと思う。(水色の雑魚が言ってる)この問題、はじめにxは任意の整数という条件になってる。ここで、受…
atcoder.jp O(1)atcoder.jp O(log B)[A,B]の区間の自然数をすべてXORしたらいくつになるでしょう？XORは同じものを重ねると0になり、0はXORの単位元なのでいくらあっても演算結果に影響がないので、累積和の要領で差分みたいなのをとればいい。また、解説に…
atcoder.jp 前回の続き。 しばらく普通のしゃくとりの例題と実装を説明するので上の問題の解説はしばらく後。 普通のしゃくとり法 普通のしゃくとり法は、条件を満たす区間の中で最善になる可能性のあるものを、区間の両端を動かすことにより求める。 たとえ…
atcoder.jp 最大20万の長さの自然数列を与えられ、そこにしきりを3ついれて、4つに分割する。4つの数列の和の最大値と最小値の差を最小化するとき、その差はいくつになるか。 例） 5 2 3 6 1 3 2 ベストな分割方法は{5}, {2, 3}, {6}, {1, 3, 2}にして和は5,…
arc073.contest.atcoder.jp ナップサック問題に制約、 Wがばかでかいので当然普通のdpではMLEする。 ここでＮが小さいときに注目、Ｎが小さいときにうまくいくのは全探索、全列挙的な手法となる。 100では全列挙は厳しいけど、ここで、重さは４通りしかない…
