問題解決の宝石箱

競技プログラミング/数学ネタ置き場

AtCoder Grand Contest #043-D : Merge Triplets

典型てんこ盛り、地力が問われるいい問題。 問題文は日本語に付き省略。 atcoder.jp

ARC #081-F : Flip and Rectangles

日本語につき問題文は略。 atcoder.jp 公式解説 とは着眼点が異なる別解を紹介する。

Educational Codeforces Round #10-F : Ants on a Circle

問題 Educational Codeforces Round #10-F : Ants on a Circle 【Educational Codeforces Round #10-F : Ants on a Circle】 \(N\) 匹の蟻が長さ \(M\) cm の円周上に乗っている。 蟻は1秒に付き1cm、円周上を一定の向きに動き続ける。 蟻が円周上でぶつかる…

区間に含まれる区間の数をカウントするクエリにたくさん答えたい

区間がたくさん与えられるので、別に与えられる区間に含まれるものはいくつあるか?というクエリに効率良く答える方法を、オフライン版、オンライン版共に紹介。

ARC #068-F : Solitaire

日本語につき問題文は略。 atcoder.jp 比較的理解が容易*1な解法を紹介する。 *1:個人の感想

SRM691 Div1Medium : Moneymanager

問題 SRM691 Div1Medium : Moneymanager 【SRM691 Div1Medium : Moneymanager】 $N$ 個のタスクがある。各タスクには数値 $ a_{i}, b_{i} $が決められている。 $i$番目のタスクを完了すると以下のことが順番に起こる。 - 経験値(以下、EXPと表記)が $ a_{i} …

JOI春合宿 2012年 Day3-B カンガルー

今度こそ*1 今年最後の記事。 問題 JOI春合宿 2012年 Day3(PDF) 【JOI春合宿 2012年 Day3-B : カンガルー】 $N$ 匹のカンガルーがいる。それぞれの体の大きさは 、ポケットの大きさは $B_{i}$ である。 カンガルーたちは、以下の条件を満たす限り、カンガル…

Wunder Fund 2016-F : Double Knapsack

おそらく今年最後の記事。 問題 Wunder Fund 2016-F : Double Knapsack 【Wunder Fund 2016-F : Double Knapsack】 長さ $N$ の正の数列が 2 つ与えられる($A, B$ とおく)。 数列に含まれる数は 1 以上 $N$ 以下の整数である。 $A, B$ から空でない部分列を…

鳩の巣原理特集

Competitive Programming Advent Calendar 2016 23日目の記事です。 鳩の巣原理と、競技プログラミングでの使われ方を紹介します。 鳩の巣原理とは 昔々あるところに、5羽の鳩がおりました。彼らをすべて巣箱に入れたいのですが、あいにく巣は4つしかありま…

SRM700 Div1Medium. CrazyFunctions

SRM700 Div1Medium. CrazyFunctions 整数 , が与えられる。以下の条件を満たす関数 を数え上げよ。 の定義域および値域は 1以上n以下の整数である。 を満たす。関数 の定義は以下の通り。 は の最小値を返す関数。 は任意の非負整数。 は 集合 の要素数。 は…

CODE FESTIVAL 2016 予選B E. Lexicographical disorder

日本語につき問題文は略。 code-festival-2016-qualb.contest.atcoder.jp 解法を2つ紹介する。

指定区間の最大値/最小値のインデックスを求めるクエリにたくさん答えたい part2

hama-du-competitive.hatenablog.com 前回の記事の最後で紹介した練習問題の解答編。問題を整理して再掲する。 長さ の数列 が与えられる。クエリに 個答えよ。 全ての問題において、制約は以下の通り。 数列の長さ: 要素の値: クエリの数: 問題1 i 番目…

Codeforces Goodbye 2015 D. New Year and Ancient Prophecy

Codeforces Goodbye 2015 D. New Year and Ancient Prophecy 桁の数が与えられる。桁の間にいくつか*1線を引いて分割し、新たな数列を得ることを考えよう。 例えば、数 314159265358979 を 3 | 141 | 592 | 6535 | 8979 のように分割すると、数列 が得られる…

指定区間の最大値/最小値のインデックスを求めるクエリにたくさん答えたい part1

区間内の最大値/最小値のインデックスを求めるRMQの実装を求めています。— tookunn (@tookunn_1213) October 6, 2016 この問題を以下のように定式化した。効率よく解けるだろうか? 長さ の数列 が与えられる。以下のクエリに 個答えよ。 クエリ1 : i 番目の…

AGC #005-D ~K Perm Counting

日本語につき問題文は略。 agc005.contest.atcoder.jp

与えられた数列の区間中の種類数を求めるクエリにたくさん答えたい

長さ の数列 が与えられる。以下のクエリにたくさん答えよう。 クエリ : 区間 中に出現する数の種類数を求めよ 以下の制約で、効率的に解くことはできるだろうか? 数列の長さ: 要素の値: クエリの数: 以下、解法を3つ紹介する。