ABC063 ARC075
問題概要は雑に書いているのでどうせならコンテストページを見ようね♡
A - Restricted
A: Restricted - AtCoder Beginner Contest 063 | AtCoder
問題概要
二つの整数 A, B が入力されるのでA+B の値を出力
ただし、A+B が 10 以上の場合は、代わりに"error"と出力
まあ問題文通りに書けばおわり
if文知ってますかみたいな問題
B - Varied
B: Varied - AtCoder Beginner Contest 063 | AtCoder
問題概要
与えられた文字列に同じ文字が含まれないのであれば"yes"を、そうでないなら"no"を出力
sortして隣り合うものが同じかどうかで判断した
uniqueした方が楽だったかも
文字列の長さは26文字以下なので、それぞれの文字について今見ている文字と同じ文字がそれ以降の文字に含まれていないかどうかを2重ループで調べても大丈夫
C - Bugged
C: Bugged - AtCoder Regular Contest 075 | AtCoder
問題概要
N個の整数が与えられる。合計が10の倍数になると0として扱われてしまう条件で、N個の数字からうまく組み合わてできる最大の数を出力せよ。
コンテストでは脳を殺してDPしてしまった
N個の総和がもともと10の倍数でないのであればそれが答え
N個の総和がもともと10の倍数であれば、最小の10の倍数でない整数を総和から引いたものが答え、もしN個の総和が10の倍数かつ10の倍数でない数が一つもないのであればどう組み合わせても10の倍数になってしまうので0を出力
想定解法、頭いいなあってなった
綺麗な実装をすればDPをするよりも下の解法の方が早く実装できそう(してない)
D - Widespread
D: Widespread - AtCoder Regular Contest 075 | AtCoder
問題概要
N体の魔物がいて、それぞれの体力は h_1, h_2, ..., h_N である。
あなたは魔物に攻撃することができて、1回の攻撃につきN体の魔物のうち1体に A ダメージ、他の魔物には B ダメージが与えられる。(A > B)
全ての魔物の体力を0以下にすることができる最小回数を求めよ。
誤読してコンテストでは飛ばしました(ア
1体にAダメージ、その他にBダメージとしていると扱いが面倒なので変形して、
全ての魔物にBダメージ、そのうち1体に追加で (A - B) ダメージとすると、M回の攻撃で全ての魔物を倒せるかが O(N)でわかるので、いい感じに M を二分探索できることに気がつける
怖かったので二分探索する [l, r) の r の区間を大きくしていたらなぜかWAが出て、ギリギリまで小さくするとACするといった謎の現象に悩まされてテスト前の貴重な休日が吸われた(やめろ)
原因はまたあとで考えます
E - Mエアにんgふl Mえあん
E: Meaningful Mean - AtCoder Regular Contest 075 | AtCoder
問題概要
長さ N の数列 a 上の、連続した空でない部分列のうち、算術平均が K 以上であるようなものはいくつあるか？
わざわざ全部足して個数で割ってK以上か判定云々などしたくないですね、となる。
あらかじめ a の要素全てから K を引いておくと、合計が 0 以上かどうかだけで算術平均が K 以上かどうかがわかるのでそうしておく *1
愚直な解法として、あらかじめ累積和を持っておき、二重ループを回して全ての区間に対して 0以上かどうかを判定する、といったものが思いつく
r(x) を、あらかじめ全ての要素から K 引いておいた a の、 i 番目までの要素の総和としたとき、 r( j ) - r( i ) >= 0 ( i < j )であるような区間 ( i, j ]の算術平均は K 以上になることがわかる。
これを式変形すると r( j ) >= r( i ) となって、( i < j )であるような i と j の組み合わせの数が答えになることがわかるので、*2 それを座圧とBITを使って求めると勝利できる。*3
BITを使って求める部分は転倒数(もしくはバブルソートの交換回数)とかで調べます。
コンテストが終わってからも実装をバグらせていたので、テスト前の貴重な休日が吸われました
名前は言わないんですが、とある人たちが力を貸してくれたので助かりました ありがとうDEGwer3456 ありがとうLatteMalta
