hotpepsiの練習帳

SRM 690

22:03

https://competitiveprogramming.info/topcoder/srm/round/16729/div/1

Div1 Easy (250) WolfCardGame

問題

• 1から100までの100毎のカードのうち、K枚(15以下)選ぶ
• K枚のカードのうち任意の枚数を捨て、値に正負どちらかの符号をつけて合計する
• どういう組み合わせでも総和がNにならないようなK枚を構築する

方針

• Nが奇数のときを考えると、全てのカードが偶数ならNになることはない
• 一般化すると、Nの約数でない倍数で構築すればいい
• コーナーケースはNが30か60か90のとき
• 2・3・5で割り切れるので、7の倍数で構築することになるが、最後の数が100を超えてしまうので、適当な数を使う(100でも良い)
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_690/WolfCardGame.cpp

結果

o-- -1 104.72-25 = 79.72pt 103rd/258 rating 1343 -> 1410 (+67)

randome_shuffleしているコードをchallengeしたけど失敗。

http://togetter.com/li/970758

Google Code Jam 2016 Round 1B

21:03

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

A. Getting the Digits

問題

• 数値を桁毎に桁名の英単語(ONE,TWO,...)に置換し、結合し、順序をばらばらにしたものが与えられる
• 桁を復元し、昇順にしたものを求める

方針

• 一つしか出てこない英文字を含むものはそれで確定(ZEROのZなど)
• 確定したものは、それに関連する文字を取り除く(Zが2回出てきたらZ,E,R,Oを2個取り除く)
• SIXを取り除いたあとのSはSEVENの個数なので...というように一位に決まる
• Pythonで
• https://github.com/firewood/topcoder/blob/master/gcj_2016/R1B_A.py

B. Close Match

問題

• Coders対Jammersの試合が行われた
• スコアボードにスコアが表示されている
• 何桁かのスコアボードは破損している
• スコアの差が最小になるときのスコアを求める
• 同じ差であれば、Codersのスコアが最小のもの
• 同じCodersのスコアであれば、Jammersのスコアが最小のもの

方針

• Smallは全部試すだけ
• Rubyで
• https://github.com/firewood/topcoder/blob/master/gcj_2016/R1B_B.rb

C. Technobabble

問題

• 前の単語と後ろの単語、二つの単語からなるトピックがある
• 偽トピックは、既存のいずれかのトピックを2つ選び、それらの前の単語と後ろの単語をセットにしたものである
• N個のトピックが与えられる
• 偽トピックの最大値を求める

方針

• Small
• 単語に通し番号をふっておく
• 使用するトピック(使う・使わない)の組み合わせをビットで全列挙
• 使う組み合わせで、単語が網羅されているかどうかをビットで調べる
• 全部の単語が網羅されているものの最小値が答え
• (終了後)
• 少なくとも前の単語の総数Aと後ろの単語の総数Bだけ必要
• 前の単語と後ろの単語とで2部マッチングすると、マッチした数Cは、前の単語と後ろの単語の両方を使っている
• ので、N－(A+B-C)が答え
• 全ての頂点を通る辺の最小数=最小辺カバーらしい
• https://github.com/firewood/topcoder/blob/master/gcj_2016/R1B_C.cpp

結果

ooo-o- 47pt 1405th/7886

数値の桁を操作する問題が苦手。

http://togetter.com/li/969380

SRM 689

23:52

https://competitiveprogramming.info/topcoder/srm/round/16710/div/1

Div1 Easy (250) ColorfulGarden

問題

• 横にn列、縦に2段の升目状の花壇がある
• 各升目の花の色が与えられる
• 縦または横に同じ色が隣り合わないように並べ替える

方針

• 多い順に、市松模様に並べる
• 文字ごとにまとめて、多い順にソートしてジグザグに並べる
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_689/ColorfulGarden.cpp

結果

o-- 118.99pt 233rd/464 rating 1283 -> 1343 (+60)

ソートしせずにジグザグに並べると、奇数桁のときに失敗するので、ソートしておいてよかった。

batch testは、結果が文字列のときは結果が正しく表示されないバグがあるようだった。

答えが一意でなく、条件を満たしたものを構築すればいい問題はロシアゲーと呼ぶらしいことを知った。(Codeforces由来?)

http://togetter.com/li/966489

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

SRM 688

22:36

https://competitiveprogramming.info/topcoder/srm/round/16709/div/1

Div1 Easy (250)

問題

• 括弧だけの文字列が与えられる
• 閉じ括弧の対応が正しくなるよう、任意の範囲を反転する
• 最大10回反転できるとき、反転する範囲を求める

方針

• (終了後)
• 長さが奇数なら不可能
• 対応関係があるものを除去すると、必ず ))))(( の形になるので、2回反転させればいい
• ただし、閉じ括弧の数と開き括弧の数は一致しないことがある
• 1文字ずつ処理して、対応関係のあるものは消し、そうでないものは元の位置を覚えておく
• 最後の閉じ括弧の位置を覚えてく
• 先頭から最後の閉じ括弧の位置までを反転すると全てが開き括弧になる
• このとき、覚えておいた元の位置の情報も反転する必要がある
• 残った文字列の半分から末尾までを反転すればよい
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_688/ParenthesesDiv1Easy.cpp

結果

--- -1 -25pt 493/xxx rating 1429 -> 1283 (-146)

元の位置を覚えておかなければいけないのが厄介。

http://togetter.com/li/963028