yukicoder contest 438 概要

2024-07-26 21:20:00〜2024-07-27 00:00:00 (2h40m)のコンテストです。
参加登録などはありません。問題が公開されたら、回答を提出すれば大丈夫です。
誤回答によるペナルティーはありません。

# ナンバー 問題名 レベル 作問者 テスター Solved Fav
A 2819 Binary Binary-Operator 🦠みどりむし FplusFplusFFplusFplusF viral8viral8 achapiachapi AngrySadEightAngrySadEight 83 11
B 2820 Non-Preferred IUPAC Nomenclature 🦠みどりむし achapiachapi FplusFplusFFplusFplusF viral8viral8 AngrySadEightAngrySadEight 67 0
C 2821 A[i] ← 2A[j] - A[i] 🦠みどりむし achapiachapi FplusFplusFFplusFplusF viral8viral8 AngrySadEightAngrySadEight 67 1
D 2822 Lights Up! (Tree Edition) 🦠みどりむし FplusFplusFFplusFplusF viral8viral8 achapiachapi AngrySadEightAngrySadEight 36 2
E 2823 PEX (Predecessing Excluded Value) Game 🦠みどりむし achapiachapi FplusFplusFFplusFplusF viral8viral8 AngrySadEightAngrySadEight 22 4
F 2824 Lights Up! (Grid Edition) 🦠みどりむし FplusFplusFFplusFplusF viral8viral8 achapiachapi AngrySadEightAngrySadEight 17 0
G 2825 Sum of Scores of Sets of Specified Sections 🦠みどりむし achapiachapi viral8viral8 FplusFplusFFplusFplusF AngrySadEightAngrySadEight 20 1
H 2826 Earthwork 🦠みどりむし FplusFplusFFplusFplusF viral8viral8 achapiachapi AngrySadEightAngrySadEight 13 1

コンテストセッター : 🦠みどりむし🦠みどりむし

ヒント集 (コンテスト終了後に更新)

A - Binary Binary-Operator
0 $P$ を適当に決めて実験をしてみると...？
1 求めるべきは $1$ bit の値で、質問によって得られる情報も $1$ bit です。
B - Non-Preferred IUPAC Nomenclature
0 与えられるアルカンは、木構造の一種と見なせますね。
1 根を適当に定め、有向木と考えることで見えてくるものが...？
C - A[i] ← 2A[j] - A[i]
0 迷ったら実験をしてみるのも手です。
1 数列の要素を数直線上にプロットして、適当に何度か操作をしてみましょう。
操作による各点の動きを幾何的に表現すると...？
2 点が少ないときに注目してみましょうか。
たとえば点が $3$ つのとき...どこかで見たことがあるような？
D - Lights Up! (Tree Edition)
0 任意の $i$ に対して $P_i = i - 1$ のとき、すなわち与えられる木がパスグラフであるときについて解いてみましょう。
この問題はよく知られています。
1 パスグラフの場合が解けたら、それをいくつか適当な方法で合成して、もとの問題を表現できないだろうか？
という視点を持ってみましょう。
E - PEX (Predecessing Excluded Value) Game
0 不偏ゲームですね。Nim に帰着させたいです。
1 数直線にプロットしてみると、少し見通しがよくなる？でしょうか。
2 有効そうな変換は色々あります。色々試してみましょう。
3 $v \in S$ なる各 $v$ について、「$1 \leq v' < v$ かつ $v' \not\in S$ なる $v'$ の個数」($f(v)$ とします) に着目してみましょうか。
4 適当な非負整数 $c$ について「$f(v) = c$ なる $v$ の個数」を考えてみると...？
F - Lights Up! (Grid Edition)
0 一つ、自明な必要条件がありますね。
各行各列の排他的論理和に着目したくなります。
1 $2^{N^2}$ 通りのグリッドのうち、先述の必要条件を満たすものはいくつあるでしょうか。
2 実は、ちょうど $2^{(N-1)^2}$ 通りなのです！
うまく変換を施すことで、縦横が $N - 1$ マスのグリッドに対応付けてみたいです。
3 「累積和」という変換にたどり着いた皆様、おめでとうございます。
第 $2$ ラウンドはこちらになります。
4 各操作は変換後のグリッドにおいて、どのように表現できるのでしょうか。
5 引き続き、各行各列の排他的論理和に着目してみましょう。
6 どうやら $N$ の偶奇によって性格が異なっていそうです。
G - Sum of Scores of Sets of Specified Sections
0 適当な順列 $P$ の二次元平面へのプロット $(i_, P_i)$ を考えてみます。
$P$ の転倒数を幾何的に表現してみると...
1 数値の書かれたグリッドを見ると、行列が脳裏をよぎります。
行列と転倒数というと、行列式と何か関係があるかもしれません。
H - Earthwork
0 題中のすべての条件は、高々 $2$ つの変数 ($H'$) に対する不等式として表現できます。
1 もし、すべての条件を $2$ 変数の差分に対する不等式の形で表現できれば、これはいわゆる牛ゲーを利用して解決できます。
2 ところで、グリッドグラフは二部グラフです。
3 負閉路を持たないグラフにおける SSSP には、実行可能なポテンシャルが存在します。
適当なポテンシャルを与えられれば、ダイクストラ法によって問題が解けそうです。