読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

GCJ Round 2 Problem A. Rather Perplexing Showdown

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

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

問題

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

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

解法

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

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

f:id:pekempey:20160529125633p:plain

下まで繋ぐ。

f:id:pekempey:20160529125640p:plain

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

f:id:pekempey:20160529125704p:plain

下まで繋ぐ。

f:id:pekempey:20160529125727p:plain

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

f:id:pekempey:20160529125757p:plain

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

GCJ Round 2 Problem A. Rather Perplexing Showdown

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