日々ｄｒｄｒする人のメモ

今日も明日もｄｒｄｒ

DPまとめコンテスト - O問題: Matching

ProCon AtCoder

問題: O - Matching

気づき含めた解法メモ

問題概要

{N}人の男性と {N}人の女性がいる。

男性 {i}と女性 {j}の相性の良し悪しが {a_{i,j}}によって与えられ、1なら相性が良く、0なら相性が悪い。

ここで、相性の良い男女同士のペア {N}組を作るとき、これは何通り存在するか。 {10^9 + 7}で割った余りで求めよ。

続きを読む

CodeChef December Cook-Off 2018: Swag Subsets

ProCon CodeChef

CodeChef December Cook-Off 2018 の問題: Swag Subsets (Code: SOSTD)
問題ページ: https://www.codechef.com/COOK101A/problems/SOSTD

コンテスト中に無限に実装バグらせて解けなくて、後で解いたやつ。

問題概要

２つの整数の列 {A_1, A_2, ..., A_N} と {B_1, B_2, .., B_N} が与えられる。

ここで、 {S \subseteq \{1, 2, ..., N\}}となる空でない部分集合 {S}に対してswagnessを

{ \displaystyle ( \max_{(p \in S)} A_p ) \cdot ( \max_{(p \in S)} B_p ) }

で定義する。

{2^N - 1}通り考えられる空でない部分集合 {S}のswagnessの全ての和をMOD {10^9 + 7} で求めよ。

続きを読む

競プロライブラリのページをAsciiDocで作った話

blog Asciidoctor

この記事は、"IQ1 Advent Calendar 2018"の13日目の記事です。
adventar.org

今回は、自分用の競プロライブラリのWebページを最近AsciiDocで作ったので、この話を書きます。競プロよりもAsciiDocメインの記事です。
tjkendev.github.io

続きを読む

CodeChef August Challenge 2018: Safe Partition

ProCon CodeChef

CodeChef August Challenge 2018の問題: Safe Partition (Code: SAFPAR)
問題ページ: https://www.codechef.com/AUG18A/problems/SAFPAR

問題概要

{N}個の要素を含む数列 {A}がある。

この数列を、各要素がいずれか1つの列に属するように、連続したいくつかの部分列 {S_1, S_2, ..., S_K}に分割する。
この時、全ての部分列について {\min(S_i) \le |S_i| \le \max(S_i)}を満たすようにしたい。

このような分割の仕方はいくつあるか？MOD {10^9 + 7}で求めなさい。

続きを読む