筋トレ1日目：SRM573 Div1 Easy

■時間スケジュール
7:11　開始
7:47　submit　→system test fail
8:20　時間切れ
8:40　反省会終わり

■問題　SRM573 Easy 「Team Contest」
3*N人の「強さ」を渡されて、３人組をN個作りたい。
組の強さが「組内の最強+最弱」で定義される時、自分の組よりも強いチームの数の最大値はなにか。

■試した解き方
感覚的にGreedyで解ける気もしたが、最強と最弱を組み合わせないほうがいい場合がある気がして、アホなO(2^n）な解法でsubmitしてしまった。
（N=16（最大のケース）で試しても２秒以内に終了してたからいいのかな、と思ってしまった）
結果：
submit1：　時間がどうとか以前に単純なバグでsystem fail
submit2：　Execution Time Limit Exceeded
で撃沈

■解法
Editorialでもあまり満足に証明していないが、
1. 「最強の人と最弱の人の和が自分よりも強い場合は２番目に弱い人と３人で組み合わせる」
2. 「そうでない場合は、最弱の３人を組み合わせる」
の繰り返しで解ける。
証明は、そのうち補填。
<証明>

</証明>

■反省
・感覚でGreedyで解ける場合はやってしまったほうがいいのだろうか？SRMのプレッシャーの中で上記解法の有効性を証明出来る気がしない。
→実際のSRMの時は、他の人の動向（Submitまでの時間）を見て、早い人が多ければGreedyの回答をsubmitする、みたいな卑怯技も使える？
・Div1の問題でBrute Forceできる問題なんて存在しないことを肝に免じる。何個か例題で上手く行っても、かならず本番は時間切れする。せめてDPの使いどころを見つけろ。
・最初のsubmitでイージーミスを犯したのは論外。
・解法を読んでなかった場合、解法の(1)はやっていても(2)に気づかず、へんなバグを起こしそう。

■筋トレ記録
勝率 0%　0/1