250点問題
簡単な賭博シミュレーション.
一瞬int型でサイズが足りるのかと思うけどよく考えたら足りる.
なんてことない.
追記
そうそう, Room2位だったので賞金をもらえるのだけど, 手続きがかなり面倒で萎え萎えです... $23もらうために$30の手数料が必要な予感ッッッ!!
STL
それで嬉しくなってしばらくGCCのSTLのソースコードを眺めていました. "M-. RET"でカーソル周辺の単語をtags-searchしてくれるので関数階層を下るのも簡単. 以下分かったこと.
- sortは基本的にはquick sort. pivotはリスト中の3要素のmedian, 再帰が対数回を超えたらあとはheapsortする. またquick sortの再帰は最後まで行わず*1, 最後にinsertion sortで全体を整える.
- stable_sortは基本的にはmerge sort. 十分なバッファが確保できなかったらinplaceで行うためにコードはややこしい. inplaceの場合は最悪計算量がO(n * log(n))になるかは怪しい.
- nth_elementはリスト中の3要素のmedianをpivotとして使うpartitionベースのselection.
*1:具体的には各小リストの長さが16以下になったらやめる.
追記
と, 思ったら1129点で次回もDivision 2だったorz. なんだかなー.
Single Round Match 337 Division 2
終了しました.
250点問題
与えられた文字列をなるべく少ない文字の置換で回文に変えるとかなんとか.
まんなかから鏡対象の位置にある文字の対を全て見てやって辻褄をあわせるだけ.
500点問題
intの配列が与えられて, そのなかから適当に取ってならべかえてなるべく長い連続列を作ってその長さを求める問題. sortしてuniqueした後はforループを2回まわせばいいんだけど, どんな数字の代わり にも使えるジョーカーがあってそれが面倒くさいことにしてます.
1000点以上の問題
与えられた文字列の並べ替えで辞書式順序で指定された番号のものを求める問題.
それぞれ個ずつ
種類の文字が存在する文字列の並び替えの数は, 文字列の長さを
として
とかになるのであとは適当に部分文字列にさかのぼって探せばOK.
Coding Phaseは250点問題と500点問題を解いて終了. Challenge PhaseではChallenge1つ成功. みんな500点問題で落ちまくっていたようでした. submitした問題はSystem Testに通っていたので次はDivision 1に戻れるでしょう. 神の子KIDのようにならないように, 頑張ってリベンジします.
