累積和

[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' について

Atcoder 典型90問 076★3[二分探索][累積和]

■要約  問題の流れは理解していたが,実装が難しかったことと,二分探索で条件を満たすRを見つけるという考え方が浮かばなかった.確かに二分探索ならO(logN)で見つけることができるので,こういう使い方もできるかのと勉強になった.  簡単に問題を解く流れを書くと以下のよう. ①連続するピースを表せるように,ケーキ2周分に配列を拡張する.▶ N番目から数える連続するケーキの組み合わせを表現できる ②累積和Bを求める. ③Br - Bl = Bn/10 となるrを探す旅に

ABC 典型90問 010(★2)[累積和]

■要約  生徒は2クラスあって,各クラスのある区間のテストの点数の和を求める問題.まず,①各生徒のテストの点数の保持の仕方に工夫がいる.最初は辞書とかがいいのかと思ったがいつか解いた問題で使った,N個の長さの配列を2つ用意してi番目に得点を代入すればよいことが思いついた.次にQ個のクエリについて,毎回指定範囲の和を求めると計算量がO(NQ)でTLEしてしまうことに気がついた.今回はある区間の総和を求めればよいので②累積和を使うことに気がついた.コードは少し冗長になったが以下

スキ
1

ABC014-C 備忘録 p.47

itsukiです。 AtCoderの過去問を解いた様子です。解説記事ではありません。 考察の流れimos 法か? 適当な配列(例えば table[10^6] )を用意して、取得のたびに table[a_i]++;  table[b_i+1]--; していく 入力例1 の場合、すべてのアンケート情報をまとめると下記のようになる  table[0] = 1  table[1] = 0  table[2] = 2  table[3] = -1  table[4] =

AGC023-A 備忘録 p.45

itsukiです。 AtCoderの過去問を解いた様子です。解説記事ではありません。 考察の流れかの有名な Zero-Sum Ranges に挑戦!累積和と知っている以上、すんなり AC 可能(予定) 累積和 -> ソート -> nC2 とさらっと書いて、サンプルも通ったので意気揚々と投げたところ WA… その後も WA を重ね、他の方々の解説やソースを見るも、さっぱり AC できず驚異の 21WA そしてついに AC!原因は、ソートするときの compare 関数オ

スキ
1

AtCoder Beginner Contest 188 備忘録

AtCoder Beginner Contest 188 の備忘録です。 問題はこちら↓ 今回はABCD4完でした。 ・A問題:Three-Point Shotバスケットボールの試合が行われており、現在の両チームの得点は X 対 Y です( X ≠ Y )。現在劣勢のチームが3ポイントシュートを1本成功させて相手よりも高い得点となるか判定する。 X と Y をのうち得点の低い方に3点追加し相手よりも多いか比較すれば良い。 解答例(Python) https://atc

ABC183 参戦記録 p.28

itsukiです。 AtCoder Beginner Contest 183 に参戦した様子です。解説記事ではありません。 結果は A, B, C の 3完でした。 考察の流れA - ReLU「関数の定義」を見て一瞬怯む 普通にif文だった #include <stdio.h>int main(){ int x; scanf("%d",&x); if(x<0){ printf("0\n"); } else{ printf("%d\n",x); }

AtCoder Beginner Contest 183 備忘録

AtCoder Beginner Contest 183 の備忘録です。 問題はこちら↓ 今回はABCD4完でした。 ・A問題:ReLUReLU関数を次のように定義する。 ・ReLU(x) = {x (x >= 0) , 0 (x < 0) 整数 x が与えられるので ReLU(x) を求める。 ReLU関数の定義から x が 0 以上であれば x 、0 未満であれば 0 となるので、max( x , 0 ) を出力すれば良い。 解答例(Python) https:/

東京海上日動プログラミングコンテスト2020 C - Lamps【Ptyhon】

問題はこちら。 import syssys.setrecursionlimit(10**6)read = sys.stdin.readreadline = sys.stdin.readlinereadlines = sys.stdin.readlinesdef main(): N, K = map(int, readline().split()) A = list(map(int, readline().split())) for _ in range(m

AtCoder Beginner Contest 182 備忘録

AtCoder Beginner Contest 182 の備忘録です。 問題はこちら↓ 今回はABCD4完でした。 ・A問題:twiblrSNSのフォロー数が 2 * ( フォロワー数 ) + 100 を超えないようにフォローする事ができるので、あと何人フォローする事ができるか求める。 上記の式で計算をしてそのまま出力すれば良い。 解答例(Python) https://atcoder.jp/contests/abc182/submissions/17994742

スキ
1