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

今日も明日もｄｒｄｒ

AtCoder: エクサウィザーズ2019 - D問題: Modulo Operations

ProCon AtCoder

これ解くのに1時間はかかりすぎた。反省回。
atcoder.jp

問題概要

${N}$ 個の整数からなる集合 ${S}$ と整数 ${X}$ が与えられる。

この集合 ${S}$ に含まれる1つの整数 ${y}$ を取り除き、整数 ${X}$ を ${X}$ mod ${y}$ に書き換える。この操作を集合 ${S}$ が空になるまでの ${N}$ 回行う。

集合 ${S}$ の整数を取り除く順序は ${N!}$ 通り存在するが、全ての順序における最終的な整数 ${X}$ の値の総和を ${10^9 + 7}$ で割った余りで求めよ。

続きを読む

AtCoder Grand Contest 032 - D問題: Rotation Sort

ProCon AtCoder

コンテスト中に悩んで解けなかった。想定解法のメモ。
atcoder.jp

問題概要

${1, ..., N}$ の順列 ${p = (p_1, ..., p_N)}$ が与えられる。

この順列に対し、以下の操作を行える。

あるを選び、を一つ左にシフトする
- コストは ${A}$ かかる
あるを選び、を一つ右にシフトする
- コストは ${B}$ かかる

${p}$ を昇順に並べるために必要な最小のコスト操作を求めよ。

続きを読む

AtCoder: 早稲田大学プログラミングコンテスト2019 - D問題: Choose Your Characters

ProCon AtCoder

コンテスト時間中に解いた。解法メモ。

問題概要

とあるアクションゲームにおいて、 ${1, 2, ..., N}$ の番号が振られた ${N}$ 種類のキャラがいる。
これらのキャラには、対戦する際の有利不利、もしくは五分の関係がある。
(キャラ ${i}$ がキャラ ${j}$ に対し有利である場合は、必ずキャラ ${j}$ はキャラ ${i}$ に不利)
この有利不利の関係は ${M}$ 個与えられ、それ以外のキャラ同士の関係は五分となっている。

この時、以下を満たすような区間 ${[L, R]}$ を選ぶことにした。

相手が任意のキャラを選んでも、そのキャラに対し五分もしくは有利になるキャラ ${i \in [L, R]}$ が1体以上存在する。(相手と同じキャラは除外して考える)

この区間 ${[L, R]}$ の幅が最小となり、選べる同じ幅の中でも ${L}$ が最小となる ${L, R}$ を求めよ。

続きを読む

AtCoder: AtCoder Grand Contest 028 - B問題: Removing Blocks

ProCon AtCoder

組み合わせを計算する問題は、計算の視点がうまく合わせられないとなかなか計算できなくて、頭を抱える...。
結局、公式の解法を見て通した。

問題概要

${N}$ 個のブロックが一列に並んでいて、 ${i}$ 番目のブロックの重さは ${A_i}$ である。

このブロックを1つずつ取り除くが、このブロックを取り除く際のコストはその時点で繋がっているブロックの重さの総和になる。

ブロックの取り除き方は ${N!}$ 通り存在するが、この ${N!}$ 通りの各順番の操作コスト和の総和をmod ${10^9 + 7}$ で求めよ。

続きを読む

AtCoder: 全国統一プログラミング王決定戦本戦 - G問題: Greatest Journey

ProCon AtCoder

コンテスト中は(E問題でハマってて)見なかった問題。後日公式の解説見ながら通した。

問題概要

1からNまでの番号が付いた ${N}$ 個の頂点を持つ木がある。

この木の上を1からMまでの番号がついた ${M}$ 人の人が移動し、 ${i}$ 番目の人は頂点 ${V_i}$ からちょうど ${L_i}$ 回辺を伝って頂点を移動する。
この時、 ${x}$ 番目の辺を通ると ${C_x}$ 点得られる。

各人 ${i}$ について、 ${L_i}$ 回の移動で得られる最大の点数を求めよ。

続きを読む

AtCoder: 全国統一プログラミング王決定戦本戦 - E問題: Erasure

ProCon AtCoder

本戦中にはなんとか解けたけど、通り数計算まわりで無限にハマってつらくなった問題。
こんなハマり方はしないようにしたい...。

問題概要

1から ${N}$ までの番号付きの ${N}$ 個のブロックがある。
${1 \le l \le r \le N, r - l \ge K}$ を満たす ${(l, r)}$ を選び、 ${l}$ 以上 ${r}$ 以下のブロックを消すことを考える。

この時、各 ${(l, r)}$ で消すか消さないかの組み合わせは ${2^{(N-K) (N-K+1)/2}}$ 通り考えられる。
この組み合わせの中で ${N}$ 個のブロック全て消せる組み合わせは何通り存在するか？ ${10 ^ 9 + 7}$ で割った余りで答えよ。

続きを読む

CodeChef February Challenge 2019: Xor Decomposition

ProCon CodeChef

CodeChef February Challenge 2019 の問題: Xor Decomposition (Code: XDCOMP)
問題ページ: https://www.codechef.com/FEB19A/problems/XDCOMP

問題概要

1から ${N}$ の番号が付いた ${N}$ 頂点の木と一つの整数 ${x}$ が与えられる。
グラフの各頂点には重みが付いており、頂点 ${i}$ の重みは ${a_i}$ である。

ここから、木の辺をいくつか削除する。そして、できた森に含まれる各木について、その木に含まれる頂点すべての重みのXORをとった値が ${x}$ になるようにしたい。

このような辺の削除の仕方は何通り存在するか。 ${10^9 + 7}$ で割った余りで答えよ。

続きを読む