日々drdrする人のメモ

今日も明日もdrdr

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

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

atcoder.jp

問題概要

とあるアクションゲームにおいて、 {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

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

atcoder.jp

問題概要

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

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

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

続きを読む

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

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

atcoder.jp

問題概要

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

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

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

続きを読む

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

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

atcoder.jp

問題概要

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

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}で割った余りで答えよ。

続きを読む

CodeChef February Challenge 2019: Yet Another Tree Problem

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

問題: O - Matching

気づき含めた解法メモ

問題概要

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

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

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

続きを読む