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

今日も明日もｄｒｄｒ

CodeChef February Challenge 2019: Yet Another Tree Problem

ProCon CodeChef

CodeChef February Challenge 2019 の問題: Yet Another Tree Problem (Code: TRDST)
問題ページ: https://www.codechef.com/FEB19A/problems/TRDST

問題概要

頂点に1から {N}までの番号が付いた {N}頂点の木が与えられる。
また、頂点 {u}と頂点 {v}の距離を {d(u, v)}とする。

{K_1, K_2, ..., K_N}が与えられるので、各頂点 {i}について、 {d(i, v) > D_i}となる頂点 {v}が {K_i}個以上になるような最大の {D_i}を求めよ。

続きを読む

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

続きを読む