もふふろぐ

2月29日のゆるふわ競技プログラミングオンサイト at FORCIA #3に参加しました。

参加者はconnpassで募集、抽選されました。 感染症の流行の影響でキャンセル者が多かったものの、前回を超える人数が集まっています。

Twitterのハッシュタグは#ゆるふわオンサイト

コンテスト

ゆるふわ競プロオンサイト #3 (Div. 1)

7問2時間のコンテスト。 結果はABCeの1600点（1:58:36）で68位（スコア51位タイ）になりました。

A New Comers

300点 (7:22)

差集合を求める問題。 set<string>。

B Median Permutation

400点 (66:10)

午前中に映画鑑賞をしたせいで、このあたりで眠気が限界に至り30分ほど眠っていました。

次の条件を満たす順列が何通りあるか求める問題。

• $1 \leq i \leq N$ かつ奇数であるすべての $i$ について、 $a_i$ は数列 $a_1, a_2, \dots a_i$ の中央値である。

$a_i$ を後ろから考えると、 $i$ が偶数のときは未使用の要素 $i$ 個のどれを選んでもよく、奇数のときは中央値を選ばねばならないので、二重階乗になります。

C Bananas Multiplier

300点 (93:50) + 200点 (93:11)

入力された木の2頂点を指定するクエリが与えられるので、最短経路に含まれる辺の重みの積を求める問題。 Easyの制約では、クエリごとに最短経路に含まれる辺を列挙することができますが、Hardでは前処理が必要になります。

根を適当に決め、根から頂点 $i$ までの辺の重みの累積積 $p_i$ を計算しておけば、「頂点 $a$ $\rightarrow$ 根 $\rightarrow$ 頂点 $b$」のような経路のクエリを $p_a \times p_b$ で処理できます。 経路に根を含まない場合についても考えると、最短経路は頂点 $c$ を最近共通祖先 (LCA) として「頂点 $a$ $\rightarrow$ 頂点 $c$ $\rightarrow$ 頂点 $b$」です。 したがって、 $(p_a \div p_c) \times (p_b \div p_c)$ が答えになります。

mod上での割り算やLCAの知識、あるいはライブラリ整備が必要です。 LCAを実装したことがなかったため、検索して見つけたコードを貼りました。

D Banana Game

🍌

E Sweets Distribution

400点 (118:36) + 0点

Easyは簡単でしたがHardは解けませんでした。

懇親会

ピザ🍕が振舞われました。