hotpepsiの練習帳

Google Code Jam 2016 Round 1A

23:19

https://code.google.com/codejam/contest/4304486/dashboard

A. The Last Word

問題

• 文字列Sが1文字ずつ与えられる
• 与えられた1文字を先頭か末尾に加えていく
• Sで作れる辞書順最大の文字列を求める

方針

• 与えられた文字が、今の先頭と同じか、大きければ、先頭に
• そうでなければ末尾に
• PHPで
• https://github.com/firewood/topcoder/blob/master/gcj_2016/R1A_A.php

B. Rank and File

問題

• N×N人の兵士がいる
• 各兵士は、前からうしろ、左から右、それぞれについて高さが昇順に並んでいる
• それぞれの並びを2×N行にメモしたが、そのうちの1行が失われた
• 1行内では高さがすべて異なる
• 2×N-1行が与えられるので、失われた行を求める

方針

• それぞれの並びは2回カウントされる
• 奇数になっている値が答え
• Perlで
• https://github.com/firewood/topcoder/blob/master/gcj_2016/R1A_B.pl

C. BFFs

問題

• N人の生徒がいる
• 各生徒には永遠のベストフレンド(BFF)が一人いる
• 生徒を円環状に並ばせたとき、各生徒の両隣のどちらかは必ずBFFになるようにする
• 輪の大きさの最大人数を求める

方針

• とりあえずnext_permutationで列挙してチェックするのしか思いつかない
• Cで蟻本のnext_permutationを写経
• (終了後)
• 閉路ならそのまま使えるが、3頂点以上だと、他の閉路は結合できない
• 2頂点の閉路(相思相愛)の場合、相思相愛同士を連結して輪にできる
• さらに、相思相愛のそれぞれの頂点に向かう頂点群は連結できる
• ABが相思相愛のとき、C->D->A<->B<-E<-Fのような感じでCDやEFは繋げられる
• 閉路かどうかをDFSで検出
• 逆方向の辺を持っておいて、相思相愛のときは、片方向の最長経路をDFSで検出
• 3頂点以上の閉路と、相思相愛を結合したものの、大きい方が答え
• https://github.com/firewood/topcoder/blob/master/gcj_2016/R1A_C.cpp

結果

ooooo- 71pt 1420th/10145

Bは割とすぐ思いついたがC-largeが解けず。

http://togetter.com/li/963188