[ARC130] C - Digit Sum Minimization

[Q] https://atcoder.jp/contests/arc130/tasks/arc130_c かなり貪欲だけど1発で通る。ラッキーパンチあてたと思っている。 考察してみる。繰り上げ発生ごとに、桁の総和が9減少することに気づく。 Q. 入力例A = 253B = 266・もし繰り上げがなければ532266---798 = 7+9+8 = 24これは、全部の総和 2+5+3+2+6+6 = 24 と一致する。・繰り上げが1回発生した場合は 532 662---

[ABC229] G - Longest Y

[Q] https://atcoder.jp/contests/abc229/tasks/abc229_g にぶたん + 累積和で15msくらい。O(NlogN)。 1. それぞれの 'Y' について、0indexからのドット数 A[] をとる 2.  A[] の累積和 acc[] をとる 3. 要素数で二分探索。要素は連続して取る。つど、開始indexを全探索する。 swap回数は、選んだ要素の中央値との差分。 Q 入力例1YY...Y.Y.Y.21. 'Y' について

D - Double Landscape

[Q] https://atcoder.jp/contests/keyence2019/tasks/keyence2019_d BITで80msくらい。1度ACすると効率化できるのがわかる。でもバグりそう。 0.  A[] も B[] も順番関係ないので、sortしておくと考えやすいかも。 1. 一番大きい数 N*M から盤面に入れていくことを考える。1まで探索。 次の4通りで場合分け。 2. 盤面に入れる数字 x を、N*M ~ 1 まで探索していく。もしxがAに2つ以上

F - Potion

[Q] https://atcoder.jp/contests/abc192/tasks/abc192_f 1. N=100と小さめ。O(N^4)でDPする。 2. DP[maxmod][index][mod] = maxval で管理。 maxmod は 1~N index は 0~N mod は 0~(N-1) Q. DP[3][1][2] = 5 は?A. 最終的に3個(maxmod)とる場合の探索だけど、今は1個(index)とった時点。その総和を3(maxmod)

C - 節制

[Q] https://atcoder.jp/contests/abc013/tasks/abc013_3 1. はじめに食べれるだけ食べちゃって、終了日ぎりぎりまで絶食すればいい。 2. どれだけ食べるかは、普通の食事を0 ~ N回全探索する。 3. 普通回数が決まれば、質素回数と食事抜き回数は、O(1)で求まる。 4. 普通以外を全部食事抜きとした場合に、不足する満腹度が出る。質素におきかえれば、質素 + 食事抜きの減少分が増加量。 Q. 例14 5100 4 60

[ARC129] C - Multiple of 7

[Q] https://atcoder.jp/contests/arc129/tasks/arc129_c 1. 7で割れる組み合わせ数を稼ぐには、"777...777"を作ればいい。nC2通りの組み合わせが作れる。 2. nC2を作ってNを消費させる。Nがまだ残っているなら、いったん7以外の文字で区切って、再度"777...777"を作る。 これを繰り返せば、効率よく解答文字列を作れそう。 3. ダミー文字を何にしよう?(3WA) Q. 2020をどんどん削っていく。1)

[ARC129] B - Range Point Distance

[Q] https://atcoder.jp/contests/arc129/tasks/arc129_b AよりBのほうが簡単かもしれない。 1.  Lの最大値と、Rの最小値を常に更新すればいい。 2.  Lmax - Rminで法則がみつかる。 Q. 31 32 45 61.) 1 3 を考える。1~3 が 0 で、それ以外は距離がスコアになっているので、こう。0 1 2 3 4 5 6 7===============1 0 0 0 1 2 3 4 // Lmax =

[ARC129] A - Smaller XOR

[Q] https://atcoder.jp/contests/arc129/tasks/arc129_a 1. 範囲[L, R]の答えは、[1, R]の答えから、[1, L-1] の答えを引けばいい。 2. Nのbitを考察する。Nのbitが立っている箇所にxのbitをたてれば、それより下のbit桁を自由に選択できる。 Q. 例210 2 191. 19 以下の答えを全部出した後、1 以下の答えを引くことを考える。ans = solve(19) - solve(1)なる

[ABC228] F - Stamp Game

[Q] https://atcoder.jp/contests/abc228/tasks/abc228_f 1. 白の長方形の大きさ (h2, m2) は、黒より大きくても意味をなさないので、h2 = min(h1, h2) w2 = min(w1, w2) をとっておく。 2. 二次元累積和で、白と黒の面積を求めておく。 3. 黒の面積を全探索。つど白の最大妨害値を探す。 4. しかし愚直な白探しにO(黒の面積) かかっちゃう。 4. 白探しの高速化のために、まずx座標を

スキ
1
+2

ABC228(トヨタシステムコンテスト2021)参戦記

はじめに 11月20日21:00-22:40に開催されたABC228(トヨタシステムコンテスト2021)に参戦しました。結果は40分16秒ABC3完ノーペナで2694位/6298人中、パフォーマンス782でレーティングは前回863から-8の855となりました。 A問題ここのところA問題から骨のある問題が出ることが多いABCですが、今回も気を付けないとペナルティを出しそうな問題でした。慎重に場合分けを検討して8:02で提出。無事にACしました。 #include <bit

スキ
7