torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

二分探索

AtCoder Beginner Contest 324, E : Joint Two Strings

問題文 https://atcoder.jp/contests/abc324/tasks/abc324_e 問題概要 英小文字からなる $N$ 個の文字列 $\{ S_i \}_{ 0 \leq i $0 \leq i, j 制約 $N \in \mathbb Z^+$ $1 \leq N \leq 5 \times 10^5$ $\sum |S_i| \leq 5 \times 10^5$

AtCoder Beginner Contest 260, D : Draw Your Cards

問題文 https://atcoder.jp/contests/abc260/tasks/abc260_d 問題概要 $1$ 以上 $N$ 以下の整数が重複なく書かれたカードが $N$ 枚あり,山札として積まれている.上から $i$ 番目のカードに書かれているのは $P_i$ である. ここで,次の操作を $N$ 回繰り…

AtCoder, エイシングプログラミングコンテスト 2022 (AtCoder Beginner Contest 255), D : ±1 Operation 2

問題文 https://atcoder.jp/contests/abc255/tasks/abc255_d 問題概要 項数 $N$ の数列 $\{ A_i \}_{ i \in [ 0, N ) }$ が与えられる.この数列を以下のように変更することを「操作」と呼ぶ. $0 \leq i $A_i$ を $A_i + 1$ または $A_i - 1$ のいずれかで…

AtCoder Beginner Contest 172, C : Tsundoku

問題文 https://atcoder.jp/contests/abc172/tasks/abc172_c 問題概要 本のスタックが 2 つあって,片方には $N$ 冊の本が,他方には $M $ 冊の本が積まれている.$N$ 札の本の内,上から $i$ 番目は読むのに $A_i$ 分かかり,$M $ 冊の本の内上から $j$ 番…

TopCoder, Single Round Match 642, Division 2, Level 3 : TallShoes

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13523&rd=16085 問題概要 不思議の国の王様は,底の高い靴を履くのが好きである. 不思議の国には 個の町と,それらを結ぶいくつかの道路がある.道路の情報は 3 つの配列 によって表され…

Codeforces #271, B : Worms

問題文 http://codeforces.com/contest/474/problem/B 問題概要 ユニークな通し番号を付けた虫たちを 個の塊に分ける。結果、 番目 ( 1-indexed ) の塊には 匹の虫がいて、その通し番号は( 0 番目の山にいる虫の数を便宜的に とおけば) である。 以下の形…

Codeforces #219, Division 1, A ( Division 2, C ) : Counting Kangaroos is Fun

問題文 http://codeforces.com/contest/372/problem/A 概要 n 匹のカンガルーがいて、i 番のカンガルーの大きさは である。二匹のカンガルー i, j について、 であれば、i は j のポケットに入ることができる。ポケットに入ったカンガルーは他のカンガルーを…

Codeforces #213, Division 1, A ( Division 2, C ) : Matrix

問題文 http://codeforces.com/contest/365/problem/C 概要 数字からなる文字列 s が与えられる。 行列 b の ( i, j ) 要素を とする。 行列 b 内部の長方形領域であって、要素の和が a となるものの数を求めよ。

AtCoder Regular Contest #014, D : grepマスター

問題文 http://arc014.contest.atcoder.jp/tasks/arc014_4

TopCoder SRM 582, Division 1, Level 1 : SpaceWarDiv1

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12604&rd=15502 概要 N 人の魔法少女がいて、それぞれの強さの情報が与えられる。 また、敵について、「ある強さの敵が何体いるか」という形式で情報が与えられる。 魔法少女は、敵の強さ…

Codeforces #188, Division 2, B : Strings of Power

問題文 http://codeforces.com/contest/318/problem/B 概要 英小文字からなる長さが 以下の文字列が与えられる。 この文字列の部分文字列の内、"heavy" をプレフィックスにもち "metal" をサフィックスにもつ部分文字列の数を求めよ。 (元の文字列に於ける…

Codeforces #172, Division 2, B : Nearest Fraction

問題文 http://codeforces.com/contest/281/problem/B 概要 分数 が与えられる。 分母が n を超えない既約分数のうち、 との差の絶対値が最も小さいものを求めよ。

2013 TCO Algorithm - Round 1C, Level 2 : TheOlympiadInInformatics

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12456&rd=15585 概要 あるプログラミングコンテストで、自分以外の参加者は N 個の部屋に別れて参加している。 各部屋に何人の参加者がいるかは分からないが、各部屋の参加者の合計得点は…