Takefumi Yamamura's blog

This blog is for my memorandum.

Takefumi Yamamura's b!og

This blog is for my memorandum

二分探索

AtCoder Regular Contest 029 B 高橋君と禁断の書

問題 arc029.contest.atcoder.jp 解き方 二分探索するまえに(A ≤ C かつ B ≤ D)もしくは(A ≤ D かつ B ≤ C)を満たせば"YES"。 満たさなければ、角度で二分探索する。 このとき、中の本を傾けて行って、傾けたときの片方の長さのみに注目して2分探索する。 指…

Sparse Search

problem Given a sorted array of strings that is interspersed with empty strings, write a method to find the location of a given string. how to solve If it were not for the empty strings, we could simply use binary search. With empty string…

値を固定して2点間の最短距離を求めるのを二分探索 AtCoder Beginner Contest 020 C - 壁抜け

問題 abc020.contest.atcoder.jp note 値を固定して二分探索するよくあるやつ。2点間の最短距離を求める必要があるのでダイクストラかワーシャルフロイドを使う。

AtCoder Beginner Contest 026 D - 高橋君ボール1号

D - 高橋君ボール1号 時間制限 : 2sec / メモリ制限 : 256MB 問題文 高橋君は野球が得意です。高橋君は、高橋君ボール 1 号という変化球を投げることが出来ます。 このボールは、投げてから t 秒後のボールの位置を f(t) とすると、 f(t)=A×t+B×sin(C×t×π) …

AtCoder Beginner Contest 013 D 阿弥陀

D - 阿弥陀 時間制限 : 4sec / メモリ制限 : 256MB 問題文 古くより伝わる日本の伝統的なくじ引き、あみだくじをご存知だろうか? あみだくじを行うときは、まず N 本の平行な縦線を引く。次に、M 本の横線をその中に引いていく。それぞれの横線は隣り合う 2…

AtCoder Beginner Contest 030 C 飛行機乗り

C - 飛行機乗り 時間制限 : 2sec / メモリ制限 : 256MB 問題文 ウナギの高橋くんは飛行機に乗ることが趣味です。今回は空港Aと空港Bを往復することにしました。 空港Aから空港Bの飛行機には X 時間かかり、空港Bから空港Aへの飛行機には Y 時間かかります。 …