GCJ Round 2 Problem A. Rather Perplexing Showdown

https://code.google.com/codejam/contest/10224486/dashboard#s=p0&a=0

T シャツが獲得できて嬉しい。GCJ で T シャツを獲得するというのは、去年の自分では想像もできなかった。

問題

2^N の人でジャンケンのトーナメント戦を行う。トーナメントが行われている最中は手を変えることはない。このため、場合によってはあいことなるペアができてしまい試合が終わらなくなってしまう。

このようなことを避けるために、マッチする相手と引き分けにならないようなトーナメントを構成したい。構成できるなら辞書順最小のものを示せ。

解法

とりあえず辞書順最小は無視しよう。

優勝者の手をグーに決めてみる。

下まで繋ぐ。

グーが勝ったということは、戦った相手はチョキである。

下まで繋ぐ。

これを繰り返すとトーナメントが決まる。

木の左右は交換可能なので、左部分木と右部分木のうち最小のものを前に置けば辞書順最小になる。

GCJ Round 2 Problem A. Rather Perplexing Showdown

辞書順最小を見落としてたけど、大した変更じゃなかったので良かった。
はじめて yahoo 翻訳使ってみたんだけど、一文ずつ翻訳してくれて便利だね。