日々drdrする人のメモ

今日も明日もdrdr

CodeChef December Cook-Off 2018: Swag Subsets

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

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

問題概要

2つの整数の列  {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で作った話

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

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

続きを読む

CodeChef August Challenge 2018: Safe Partition

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}で求めなさい。

続きを読む

CodeChef August Challenge 2018: Chef at the River

Code Chef August Challenge 2018の問題: Chef at the River (Code: RIVER)
問題ページ: https://www.codechef.com/AUG18A/problems/RIVER/

問題概要

Chefと {N}の動物が川の左岸におり、ボートを使って何回か往復することで全員右岸に渡りたい。
ボートは必ずChefが同行しなければならない。

 {N}匹の動物の中には、相性が悪いペアがおり、Chefと一緒にいない時に彼らが一緒にいてはいけない。
この悪いペアの関係は {N}頂点のグラフで表現され、 {u} {v}が辺で繋がっている時、 {u},  {v}は相性が悪いことを表す。

最初は頂点1のみの根付き木になっており、 {2, 3, ..., N}の頂点がこの根付き木に繋がっていく。
2の頂点が繋がった時から、 {N}の頂点が繋がった時までの各 {N-1}の状態について、制約を満たしながらChefと動物全員を対岸に渡すために必要な最小のボートの容量を求めよ。

続きを読む