torus711 のアレ

主に競技プログラミングの問題について書きます

二分探索

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 個の部屋に別れて参加している。 各部屋に何人の参加者がいるかは分からないが、各部屋の参加者の合計得点は…