組み合わせを計算する問題は、計算の視点がうまく合わせられないとなかなか計算できなくて、頭を抱える...。
結局、公式の解法を見て通した。
問題概要
個のブロックが一列に並んでいて、
番目のブロックの重さは
である。
このブロックを1つずつ取り除くが、このブロックを取り除く際のコストはその時点で繋がっているブロックの重さの総和になる。
ブロックの取り除き方は通り存在するが、この
通りの各順番の操作コスト和の総和をmod
で求めよ。
AtCoder: 全国統一プログラミング王決定戦本戦 - G問題: Greatest Journey
コンテスト中は(E問題でハマってて)見なかった問題。後日公式の解説見ながら通した。
問題概要
1からNまでの番号が付いた個の頂点を持つ木がある。
この木の上を1からMまでの番号がついた人の人が移動し、
番目の人は頂点
からちょうど
回辺を伝って頂点を移動する。
この時、番目の辺を通ると
点得られる。
各人について、
回の移動で得られる最大の点数を求めよ。
AtCoder: 全国統一プログラミング王決定戦本戦 - E問題: Erasure
本戦中にはなんとか解けたけど、通り数計算まわりで無限にハマってつらくなった問題。
こんなハマり方はしないようにしたい...。
問題概要
1からまでの番号付きの
個のブロックがある。
を満たす
を選び、
以上
以下のブロックを消すことを考える。
この時、各で消すか消さないかの組み合わせは
通り考えられる。
この組み合わせの中で個のブロック全て消せる組み合わせは何通り存在するか？
で割った余りで答えよ。
CodeChef February Challenge 2019: Xor Decomposition
CodeChef February Challenge 2019 の問題: Xor Decomposition (Code: XDCOMP)
問題ページ: https://www.codechef.com/FEB19A/problems/XDCOMP
問題概要
1からの番号が付いた
頂点の木と一つの整数
が与えられる。
グラフの各頂点には重みが付いており、頂点の重みは
である。
ここから、木の辺をいくつか削除する。そして、できた森に含まれる各木について、その木に含まれる頂点すべての重みのXORをとった値がになるようにしたい。
このような辺の削除の仕方は何通り存在するか。で割った余りで答えよ。
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からまでの番号が付いた
頂点の木が与えられる。
また、頂点と頂点
の距離を
とする。
が与えられるので、各頂点
について、
となる頂点
が
個以上になるような最大の
を求めよ。
DPまとめコンテスト - O問題: Matching
問題: O - Matching
気づき含めた解法メモ
問題概要
人の男性と
人の女性がいる。
男性と女性
の相性の良し悪しが
によって与えられ、1なら相性が良く、0なら相性が悪い。
ここで、相性の良い男女同士のペア組を作るとき、これは何通り存在するか。
で割った余りで求めよ。
CodeChef December Cook-Off 2018: Swag Subsets
CodeChef December Cook-Off 2018 の問題: Swag Subsets (Code: SOSTD)
問題ページ: https://www.codechef.com/COOK101A/problems/SOSTD
コンテスト中に無限に実装バグらせて解けなくて、後で解いたやつ。
問題概要
２つの整数の列 と
が与えられる。
ここで、 となる空でない部分集合
に対してswagnessを
で定義する。
通り考えられる空でない部分集合
のswagnessの全ての和をMOD
で求めよ。
