2016-12-15
TCO16 Algorithm R2B
https://competitiveprogramming.info/topcoder/srm/round/16739/div/1
Easy (300) TriangleTriples
問題
- 三角形の辺の長さになりうる3つの数を三角形数とする
- 1以上A以下のa、1以上B以下のb、1以上C以下のcの三つの組み合わせの三角形数の総数を求める
方針
- (終了後)
- pekempeyさんのを写経
- 1辺が2辺の合計より長くなる領域は三角錐(を削った形)になる
- 直方体から3つの三角錐を引く
- ただし、1辺がすごく長いときは二重に削るので、その分は戻す
- https://github.com/firewood/topcoder/blob/master/tco_2016/TriangleTriples.cpp
結果
--- 139th/693 0pt 1543 -> 1523 (-20)
これは難しかったので座ってるだけだった。
C >= Aの領域がよくわからなくなったのでRで図を描いた。
三角錐は天地逆の感じ。
縦がC、横がAで、AがCより小さいときは、カットされた形になる。
2016-12-13
TCO16 Algorithm Round 2A
https://competitiveprogramming.info/topcoder/srm/round/16736/div/1
Easy (400) LCMGCD
問題
- 2^a×3^bの数からなる配列がある
- 任意の2つの要素を選び、その要素を削除する
- 2つの要素のGCDかLCMを求め、配列に追加する
- 配列の要素が1つになるまで繰り返したとき、値をtにできるかどうかを求める
方針
- GCDはmin,LCDはmaxを取るのとほぼ等しい
- Failed System Test
- 乱択でもいけるらしい
- 10万回くらい試行すればsystem testは通る
- https://github.com/firewood/topcoder/blob/master/tco_2016/LCMGCD.cpp
- 2軸のmin/maxのため、x・yそれぞれで大・等・小の3通り、計9通りにわける
- xとyどちらも等しい状態に遷移できるか探索すれば良いっぽい
結果
x-- +1 50pt rating 1410 -> 1543 (+133)
変則400点。写経ボーナスをもらった。
2016-12-12
TCO16 MM R2
https://competitiveprogramming.info/topcoder/marathon/round/16703
StarTraveller
また記念submitで終わってしまった。
SRMの復習が終わったら復習するつもり。(いつになるやら...)
2016-12-11
競技プログラミングの練習方法について
Competitive Programming Advent Calendar 2016 (その2)の11日目の記事です。
今年、PEAK(超一流になるのは才能か努力か？)という本を読んだ。
練習と能力向上について、
- できないことに挑戦することが大切(惰性で練習してもスキルは上がらない)
- 練習の結果を評価し、改善すること(良いコーチを持つなど)
- 効果的な練習をすることでスキルに特化した脳内イメージができる
というようなことが書かれている。モーツァルトのエピソードなど、なるほどと思うことが多かった。
これを読んで今年はピアノの練習を少し工夫し、前より効果的に練習できた気がしたので、競技プログラミング(以下競プロ)にも適用できたらいいなと思っている。
(以下は思いつきでありまだ実施していない)
PEAKの中で3F(focus、feedback、fix)というのが出てくる。苦手なところを集中して練習し、結果を考察し、悪い部分を直す、というサイクルをまわすとよいという話である。
そのためにはまず苦手なところを見つける必要がある。
SRMのような短時間の競プロの場合、全体としては、問題文や制約条件を理解する→方針を立てる→実装というような流れになる。
それぞれのフェーズについて、
- 問題文の理解の間違いは仕様理解バグ
- 適切な方針やアルゴリズムを選択できていないのは方針バグ
- 正しく実装できていないのは実装バグ
として、自分のSRMのdiv1で結果がどうだったかを分類してみた。SRM526から702まで159回出ていて、期間を3回にわけた。
| 期間 | 総数 | AC | 実装バグ | 方針バグ | 仕様理解バグ | 未提出 |
| SRM526～599 | 57 | 28 (49.12%) | 5 (8.77%) | 9 (15.795%) | 3 (5.26%) | 12 (21.05%) |
| SRM600～650 | 50 | 31 (62.00%) | 8 (16.00%) | 8 (16.00%) | 0 | 3 (6.00%) |
| SRM651～702 | 52 | 22 (42.31%) | 4 (7.69%) | 10 (19.23%) | 0 | 16 (30.77%) |
| 全体 | 159 | 81 (50.94%) | 17 (10.69%) | 27(16.98%) | 3 (1.89%) | 31 (19.50%) |
自分の場合は方針バグが多いので、そこを直すべきである。また、実装バグも少なくない。
実装結果は提出記録を見ればよいが、方針については時間がたつと全く思い出せないので、その場なり、直後なりでメモを取って読み返せるようにしたほうがいい。
同僚のhama_duさんが一人Slackをやっているそうで、良さそうなので真似するつもり。
というような感じで、
- 対象を分解する
- 現状を知る
- どこを直せばよいかを見つける
のように、多少意識的に取り組めればいいかなと考えている。来年以降試す予定。
また、全く別の側面として、スキルを上げることだけを目的にすると楽しさが失われがちになるので、続けられるようなバランスでやっていきたい。
(良い練習方法があったらtwitterなどでぜひ教えてほしいです)
明日はzukky162さんと(フライングで公開済ですが)Komakiさんです。
2016-12-05
Google Code Jam 2016 Round 1C
https://code.google.com/codejam/contest/4314486/dashboard
Contest Analysis
https://code.google.com/codejam/contest/4314486/dashboard#s=a
A. Senate Evacuation
問題
- 議会場が火事になった
- N個の政党の議員を二人ずつ退避させる
- いかなる瞬間においても、過半数を取る政党がないように保つ必要がある
- 退避させる手順を求める
方針
- priority queueで多い順に1人ずつ取り出す
- https://github.com/firewood/topcoder/blob/master/gcj_2016/R1C_A.cpp
B. Slides!
問題
- 1からB番までのB個のビルがある
- 1からB番への移動経路がちょうどM通りになるよう、B番以外の任意のビルに片方向の移動手段(辺)を追加する
方針
- small
- 閉路があると経路が無限になるので、DAGである必要がある
- 番号が大きなビルへしか行かないようにする
- 辺の有無をbitの有無で全て試す。DPで経路数を求める。
- https://github.com/firewood/topcoder/blob/master/gcj_2016/R1C_B.cpp
C. Fashion Police
問題
- ニューヨークでは同じ恰好をすると逮捕されるので、毎日違う格好をする必要がある
- J枚のジャケット、P枚のパンツ、S枚のシャツを持っている
- 毎日それぞれから一つずつ選ぶ
- J、P、Sの三つが全て同じ組み合わせだと即逮捕
- 二つが同じ組み合わせのときは、K回までは許容される
- 逮捕されない最大日数を求める
方針
- small
- ひたすらランダムで試す
- https://github.com/firewood/topcoder/blob/master/gcj_2016/R1C_C.cpp
- MODを求めるらしい
結果
oox-o- 32pt 1671st/5950
C問題が面白すぎ。
Bの出力を空白区切りにしてしまい、smallも通らなかった。diffを取るようなMakefileを書くのが良さそう。
largeの方針は立たなかったので、いずれにせよ今年は厳しかった。
multiple languagesの部は、最終的に13言語を使って5位タイだった。色々調べるのが楽しいので、来年も10言語くらいは使いたい。
https://www.go-hero.net/jam/16/multilang