CODE FESTIVAL 2017 Final (Parallel)
参加しました。（久しぶりの更新）
その前に今年のコドフェス振り返り。
予選A
これはJAG夏合宿2日目夜に出ました。隣には住建という状況。
C誤読して大幅に書き直すはめになった記憶。Dは頭がバグって完全に停止しました。
住建はずっとデバッグで苦しんでたように見えました。
355位 通過できず。
koprickyは通過できる順位だったのに参加登録していなくて通過できず。
予選B
Cは直観ゲーだったはず。D問題に全然覚えがありません。確かどん詰まりしたと思います。
200位 通過できず。
予選C
Cまでは早く解けてるけど、Dで完全にストップ。予選BもCもDP苦手過ぎるに尽きる。
291位 通過できず。
パチコ様(pachicobue)が通過！めでたい！LINEグループ名を"コドフェス通過待ったなし！"にしといてよかったよかった。
CODE THANKS FESTIVAL確定！
そんなこんなでまあレート上がるかなって感じでParallelへ。
A問題 AKIBA
文字列にAのみ挿入してAKIHABARAにできるか判定する問題。
頑張って挿入しましょう（こういうの苦手でサブマリンしようかと逡巡）
B問題 Palindrome-phobia
a,b,cだけからなる文字列を並び替えてどの連続部分文字列も回文にならないようにできるか判定する問題。
まずaとbだけだと絶対無理だなと思う。aが連続,1個飛ばししてもダメだからaを最大限詰め込むとするとa○○a○○a...か。
b,cにも同じことがいえるからabcabcabcabc的な感じにすれば回文なしか。
max(aの数,bの数,cの数) - min(aの数,bの数,cの数) <= 1が条件だろ。
適当に出してみる。通る。やったぜ。
C問題 Time Gap
問題設定がややこしい。要するに二つの都市の時計の時刻の差がdの時、本当の時差は24-dの可能性もあるという話。
ある一人を基準に時計の時刻の差が全員分与えられているとき、二人の時差の最小値を最大化しろという問題（問題文を読んだ方が分かりやすい）
入力に同じ時刻の差の人が3人以上いたら絶対時差0の二人がいるな～
貪欲に配置するのが最適じゃね？
適当に書いて出す。通る。やったぜ。
D問題 Zabuton
n人がいてそれぞれの身長（座布団基準）とその人がつみあげる座布団の枚数が与えられる。その人の身長よりその時の座布団タワーが低ければ全部一気に積むけどその人の身長より高い時は1枚も積み上げられません。並び順を上手くやると最大何人の参加者が詰めますか？という問題。
一年前のコドフェスで楽しそうに競プロ強者数名が食事の配給所の座布団を積んでいたところから問題が作られたのか？と思った（そもそもそれ以前から座布団を積み上げる文化が競プロ界隈にあるのか？？？と思ったりもする）
最初どこまで積み上げられるかという話だと思って早とちり（多分これの方がむずい）。
とりあえず何らかのソートを行って、dpだなという雰囲気を感じる。
とりあえず身長でソートして、dp[何人目][その人含め何人詰んだか]をやる。WA
身長低い人が無茶苦茶積むような状況がダメなケース。
とりあえず積む枚数で人をソート。これもWA
JAGの時にもあった(身長+積む枚数)でソート。これが通る。やったぜ。
正当性なんて考えてません。
E問題はパス
F問題 Distribute Numbers
入力なしの構成ゲー。
N枚の紙に1枚につきK個の相異なる数字を書き込み、相異なる2枚の紙を取ってくると必ず1つだけ数字が一緒のものがあうようにしたい。
但し全体では1~KをN個ずつ書かれていないといけない。
N=3,K=2だと
12
23
31
的な感じ。1000<=N<=2000になるようなケースを1個提出する問題。
Kをベースに考える。
K=3の時
123
145
167
をまず書く。後は
246
257
347
356
とすると上手く行きます。ハハーンなるほどとなる。
最初のK枚は1を共通のものにしてガリガリ作ります。その後は最初のK本の紙をみて
そのまま下に読む、1個ずつ横にずらしながら読む、2個ずつずらしながら読む...
なおここから怒涛のデバック地獄。この程度の実装でバグらせまくるのは本当に悲しみしかない。
G問題 Mancala
問題省略。
操作を1回やると1個ずつ全体から石が減っていくので、何回操作できるかを考えましょうという話。i番目のマスが何回操作できるか考えるとそれより前の1~i-1番目の情報は要らないので、後からDPしましょう！
解法はほぼ分かってたんだよ分かってたんだよ！！！
これも簡単な実装のところでバグバグの実を食べました。実装力。
得意系の問題が並んでいたように思うので、G通して気持ちよくなりたかったです。
parallel 26位 パフォーマンス2564 レート2151(+58)
最近調子がいいので週末のTHANKSはやったるで～～～
kopricky,smikenに負けないように頑張ります。
