hotpepsiの練習帳

SRM 658

15:13

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

Div1 Easy (300) OddEvenTree

問題

• N個の頂点からなる木がある
• それぞれの頂点の距離の偶奇が与えられる
• 構成が可能なら辺を求める

方針

• まず必要条件について考える
• 同じ頂点同士は距離ゼロなので偶数
• 隣り合う頂点は奇数なので、一つ以上奇数が存在すること
• 頂点が3以上のときは、一つ以上偶数が存在すること
• 頂点a-b-cについて、経路a-bの偶奇と、経路b-c+c-aの偶奇が一致すること
• 必要条件を満たしたら、奇数同士の頂点aとbを辺で結び、残りの頂点をaとbの偶奇からどちらかに追加していく
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_658/OddEvenTree.cpp

結果

o-- 146.27pt 271st/497 rating 1313 -> 1350 (+37)

これが正しいとすると、奇数を一つ見つけてから貪欲につなげて、そのあと矛盾があるかどうか判定したほうが楽そう。

http://togetter.com/li/817290

Google Code Jam 2015 Round1B

01:56

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

Problem A. Counter Culture

問題

• 1からNまでを順番にカウントする
• ただしズルができる
• 各カウントにおいて、一つ前の番号の+1か、桁を逆転したもののどちらかを選べる
• カウントの総回数の最小値を求める

方針

• 1000から10000を作ることを考える
• 1009を逆転するより1099を逆転するほうが良い
• という感じで、目標となる桁になるまでは、今の桁の半分までを埋めてから逆転する
• 目標となる桁になったら、端の桁から順番に、逆転したほうが有利かどうか調べていく
• https://github.com/firewood/topcoder/blob/master/gcj_2015/R1B_A.cpp

結果

Aのみ 25pt 1503rd

Aだけで二時間くらいかかってしまった。難しかった。

http://togetter.com/li/815961

SRM 657

11:29

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

Div1 Easy (250) ProblemSets

問題

• SRM用の問題がある
• 問題はEasy専用、EasyまたはMedium用、Medium専用、MediumまたはHard専用のいずれかである
• EasyとMediumとHardの一つずつをセットにするとき、最大何セット作れるかを求める

方針

• 適当にminとmaxで貪欲に書く
• Challenge Succeeded
• (終了後)
• にぶたん
• それにしか使えないものでまず作る
• 残りで作れるかどうか調べる
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_657/ProblemSets.cpp

結果

x-- 0pt 239th/319 rating 1384 -> 1313 (-71)

SRMの開催に失敗しました...

http://togetter.com/li/813968

TCO15 Marathon Round1

21:09

https://competitiveprogramming.info/topcoder/marathon/round/16445

SmallPolygons

問題

• 2次元座標上にてNP個の頂点が与えられる
• 頂点を線で結び、1個以上N個以内の多角形を作れ
• ただし、各頂点は必ずいずれかの多角形に属すること
• それぞれの線分は交わらないこと

方針

• 近い座標同士で三角形の候補を作る
• 面積が近いもの同士をマージしていく
• https://github.com/firewood/topcoder/blob/master/marathon/tco15r1/SmallPolygons.cpp

結果

688.39pt 109th rating 1215 -> 1194 (-21)

ビジュアライザをC++で書き直して、提出するだけで終わってしまった。

ビジュアライザの交差判定をそのまま持ってきたらintオーバーフローしていて時間を食ってしまったりした。

最初の方針からしていまいちだったっぽい。

http://togetter.com/li/799735

Google Code Jam 2015 Round1A

00:27

https://code.google.com/codejam/contest/dashboard?c=4224486

Problem A. Mushroom Monster

問題

• キノコ大好き
• 10秒毎のキノコの残量が与えられる
• (A)任意の量食べると仮定する(B)一定速度で食べると仮定する
• としたとき、食べる最小の量をそれぞれ求める

方針

• (A)は減った分を数えるだけ
• (B)は減った最大値Sをまず覚えておいて、各区間ごとに、残量かSの小さいほうを加える
• https://github.com/firewood/topcoder/blob/master/gcj_2015/R1A.py

結果

Aのみ 15pt 4437th

他の用事をしながら参加してしまい全然だめだった。専念してもたぶん通らなかったけど。

http://togetter.com/li/809843