勉強会に参加したい方は概要を確認してください。

定期宣伝

弊社はエンジニアを熱烈募集しています．以下から気軽にカジュアル面談申し込んでください．就職・転職を考えている知人にも積極的に宣伝してください．

この勉強会の宣伝もお願いします．参加者が増えるほど質や頻度が上がると思います． #Acompany競プロ勉強会で実況や感想，質問を呟くなども．

不定期宣伝

暗号文を作りました。 12月までに解くと抽選で５名にAcompanyのTシャツが当たります。

第一回も抽選期間は終わりましたが問題自体はとても面白いです：Acompanyからの暗号文 #1

この勉強会についての記事を書きました。

<aside> ❓

given

$N$ 頂点で各頂点 $v$ に $s_v\in\{”0”, “1”\}$ がついた根付き木 $T$

output

$T$ に対するトポロジカルソート $q$ について $s_{q_1}s_{q_2}\cdots s_{q_N}$ の転倒数の最小値

ただし $N$ の順列 $q$ が $T$ に対するトポロジカルソートであるとは、 $T$ の任意の頂点 $v$ について、その親を $p_v$ とした時、 $q$ において $p_v$ が $v$ より先にあるようなものを指す。

また、01列 $s$ の転倒数は $|\{(i,j)\mid i<j, s_i = 1, s_j = 0\}|$ のことを指す。

</aside>

少し一般化して、各 $s_v$ が “0” $x_v$ 個と “1” $y_v$ 個が連結した01列の場合を考える。

例えば $x_v=2,y_v=3$ の場合は $s_v$ として “00111” や “01110” が考えられるが、ここの区別は考えなくて良い（どちらであっても最適解の構造は変わらないため）。したがって $s_v$ と $(x_v, y_v)$ を同一視して考えられる。