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に負けないように頑張ります。
JAG夏合宿2017 参加記 part1
3日間泊まりで参加しました。
～遡ること一か月前～
院試の発表まだだけど家で落ち着いている気分じゃないし大阪旅行に行こう！
ということで、急遽ICPCチームメンバーのpolyominoと大阪旅行に行くことに。
大阪旅行2日目。
実家に帰っていたパチコ様(pachicobue)とUSJへ。フライングダイナソー考えた奴頭おかしい。コースター系多すぎてぐったりしました。
夕飯は前日夜量が少なすぎて失敗した串カツのリベンジ。その席でのこと。
ホハム(mtsd)「JAG夏合宿行こう！！！」
ICPCでのキャプテンhyksmは行かないとのことだったので、パチコ様を半ば強引にチームに誘ってその場で参加登録させました。めでたしめでたし。
～1か月後～
全然コード書いてない！！！！！やばい！！！！！
院試発表が終わってからというもののチームメンバー3人とも全然コーディングしていないということが発覚。
全員実装力が低いのでどうするどうするという話に。結局どうしようもないという結論で合宿日へ。
～1日目～
住建(smiken)と昼ごはんは代々木商店へ。懐かしい感じがしました。
その後オリセンへ。懐かしい感じがしました。
そんなこんなでチーム集合。まさかのパチコ様のみ宿泊しないことが発覚するなど。
パチコ様は1995年生まれなので、うちのチームIQ94じゃないじゃん！という話に。
じゃあIQ94.333333にしよう！としたが、Atcoderでは.(ドット)が使えません。。。
よってIQ_about_94ということになりました。
そして初めての5時間セットへ・・・。果たして手持ち無沙汰になってしまうのか・・・
Japan Alumni Group Summer Camp 2017 Day 1 - Japan Alumni Group Summer Camp 2017 Day 1 | AtCoder
配られたものをとりあえず分配することに。
とりあえずA問題を僕が見てこれは簡単！もう書いちゃうと宣言。
パチコ様はB問題を読む。
polyominoは僕にパソコンの使い方を教えながらそれ以降の問題を確認。
A問題 しりとり
n個の単語のしりとりの文字の総数の最小値を求める問題。
直観的にa→ab→b→...→z→za→(2文字のもの全て)→(3文字のもの全て)→...
でokと即決。あとの二人のコーナーケース大丈夫？って目線を受けながらもコーディングへ。
26^mを計算するのに電卓使いたいって言ったらpolyominoがpythonを起動してくれました。
AC (12:18)
そうしてる間にpolyominoから「これ数学だからやって」とパチコにC問題が投げられて、パチコが数学を解いていた（三角形の相似をわちゃわちゃやっていた）。
答えを出力する感じでAC(20:36)
このタイミングで順位表を見てみるとA問題がFAであることに気づく。おかしいなと思って表をよく見るとまだ見てすらいなかったJ問題クッパを他のチームが解きまくっていて、焦って問題文を読み始める。
J問題 クッパ
約数の和が98になるような正整数を全て求めよ。
こんなん算数やんけやるだけやるだけという気持ちになって、約数の和の公式を使って手計算。52が出てくる。52だ52だと伝えてtextで52を提出。WA。
あれれ？？？改行してないんじゃね？？？2WA
あ、97は素数！！！！ AC (25:01)
はい。やらかしました。（適当にぶん投げていたけど、ペナルティが20分ということに後から気付いて後悔）
普通に回せばよかったのでは・・・
その後、各自がどの問題を解こうかと模索。とりあえず解けそう（他チームが解いてそうな問題）
mtsd H問題 イベルタル
パチコ B問題 リス K問題 パンプキン
polyomino E問題 ベクトル式 F問題 部分文字列
あたりを考え始める。
僕はH問題をマス目を書いて最小値を埋め始める。
その間にパチコ様がK問題は和でソートすればいい！と主張。すぐに理解できず、マジ？？？ってなり、とりあえず書いてくれと言って書いてもらう。AC(48:54)
polyominoによるとEはやりたくない。Fはライブラリがない可能性があるので険しいかも。ということになり、とりあえずパターンが見えたHを定式化して倒しに行く。
僕が式を求めてその間にpolyominoがコードを書く。連携が上手く行った。AC(67:22)
ここからどれを解けばいいんだ～となる。
G問題は見るからにヤバそうだし全然通されてないので読みもせず。同様にI問題もパス。
C問題も数学っぽいけど全然通されてないし、FFTとかそういう類の匂いを感じスルー。
E問題は時間内に通せるか危険。残るはB問題リス、F問題極小部分列。
パチコがFは端から貪欲でよさそうと実装を始める。
その間にB問題をpolyominoと考え始める。
全員到着したときの順番が分かっていれば上手く行くか？
まずどうやってその配列を生成するか？
を考え始める。polyominoがこういうのはクエリを後ろから処理すればいいというのでその方向性で考える。すでに後から何番目までに何個埋まってるのかが分かってればよくない？という話になりこれ典型BITだよとpolyominoが指摘。じゃあ後半もBITで貪欲かよっしゃ解けた解けた！と喜ぶ。
F問題の方の実装が終わったというので、テストケースを実行するとなんかあってない。
部分文字列としてはあってるけど最短のものを出力できてないという話に。
適当に後ろからもう一回貪欲で回せばいいんじゃん？と言ってみたらそうっぽいなという話に。
実装したら上手く行ってそうなので投げる。AC(128:54)
後50分。B問題絶対通すぞ！という感じになる。
BITを蟻本から書き写す。ワチャワチャ実装。0-indexと1-indexで大混乱。35分くらいたってようやく動いたので提出。→WA
配列足りてないぞ！直せば通るだろ→半分くらい通るもWA
よく考えると後半は貪欲じゃない！と分かり、どうしよどうしよとなる。
パチコ様参戦。前からi番目にいるのが何番目に来たやつかは分かっていて、この番号が昇順になるように取っていけばいいんだけど・・・と伝えると、それただのLISやんと言われる。
あっそうじゃんとなり、また蟻本書き写し。ぎりぎりAC(174:58)
終了。7完。無駄ペナを積んでしまったけど、チーム的にはキャプテンを失った割にかなり上手く行って大満足。
パチコはそこそこ遠いのに宿泊なしで帰宅。あとの二人は今回単独参加の住建と一緒にダラダラ。あんまり他チームと交流できなかったのが残念。
ここまで書いていたのが2週間前。大分忘れてしまっていてpart2以降があるかはわかりません！part1完！
AtCoder Regular Contest 083
参加しました。
C問題 sugar water
100aか100bの水を入れる、もしくはcかdの砂糖を入れるを繰り返してf以下の重さの最も濃い砂糖水を作れ（ただし、100に対してeしか砂糖は溶けず溶け残りがあってはいけない)という問題。
不等式をきちんと立ててa,bのありうる値を全部やればいい。
0gの砂糖水は僕は存在すると思います(1WA)
D問題 Restoring Road Network
N個の都市があり、N*Nの行列Aが与えられた時、Au,vが都市uから都市vへの最短距離に成るような構造はありますかという問題。あったら道の長さの総和の最短を計算せよ。
u,vに対してAu,v=Au,w+Aw,vみたいなwが存在したらその時点でu,v間に道はなくていいねという感じ。N<=300なのでu,v,w全部について試して、可能な限り道を消す。
その後、作ったグラフに対してワーシャルフロイドをして、本当に行列Aのようになっているか確認すれば良い。
E問題 Bichrome Tree
もうなんか面倒なので問題の内容省略。
各頂点について(Xi,Yi)みたいな感じのものでYiが最小に成るものを計算し、ナップザックに帰着しました。
バグらせました。
for(int i=n;i>=1;i++){
直したら通りました。はいさようなら。
179位 パフォーマンス2071 レート1987(+10)
来週こそ黄色へ
Atcoder Regular Contest 80
参加しました。
C問題 4-adjacent
長さNの a=(a_1,a_2,...,a_N) の数列を並び替えて隣り合う数の積が4の倍数になるようにできるかを判定せよという問題。
4の倍数がp個、4の倍数でないが2の倍数であるものがq個とすると、
2*p+1>=Nかq+2*p>=Nなら達成できるのでそれを書くだけ（適当に並べればいい）。
D問題 Grid Coloring
縦H横Wのマスと色iで塗りたいマスの数a_iが与えられたときに、同じ色は連結であるような塗り分け方を一つ求めろという問題。
1行目の一番左から順に折り返すように色を塗っていけばいい。
E問題はsegtreeを始めて書きました（バグらせました）
以上。
225位 パフォーマンス1993 レート1977(+1)
減らなかったのでオーケー
AtCoder Regular Contest 079
参加しました。
C問題 Cat Snake and a Voyage
N個の島にM種類の定期船があって1とNをつなぐ定期船がないとき、2種類の定期船を使って1からNへ行けるか判定する問題。
1と直接つながっているかとNと直接つながっているかを調べて、どっちともつながっていたらPOSSIBLE。そうでなければIMPOSSIBLE。
D問題 Decrease (Contestant ver.)
長さNの非負性数列{a_i}に対し、数列の最大値がN-1以下になるまで以下の操作を繰り返し行う。
・数列の最大の要素を1つ選んで、この要素を-N。それ以外を+1。
ちょうどK回で操作が終わるようなNと数列{a_i}の組を一つ求めよ。という問題。
Kの値がむちゃくちゃでかいので構成は簡単にできるんだろうなと思った。
とりあえず1回につき全体の和は-1されていくのでその方針で考えていくことに。
m,m,...,mに対してN回操作を行うと、m-1,m-1,...,m-1になるので、この方針で考えた。
全ての操作後、n-1,n-1,...,n-1に成るような数列を考える。n=50とする。
まずn-1+k/n,n-1+k/n...,n-1+k/nにして残った回数k%n回について逆操作を順にやっていけば出来上がり。(制約条件に引っかかって1WA)
E問題 Decrease (Judge ver.)
D問題の逆で、数列が与えられた時に操作回数Kを求める問題。
a_iについて他の項は考えず何回Nを引けばN-1以下になるかv_iを計算。その和をSとする。
そのような操作を全部やると、
a_i = a_i - v_i*N + (S-v_i)
これをS=0になるまで繰り返した。
F問題はまあグラフの操作ができないマンでした。
順位 84位 パフォーマンス 2486 レート 1976(+77)
黄色チャンスですね！（m期ぶりn回目）
Atcoder Grand Contest 18
参加しました。
A問題 Getting difference
箱にN個のボールがあって各ボールにはA_iという数字が書いてある。以下の操作を行って数字Kが書いてあるようなボールを箱に入れることができるか？
・箱から二つボールを取り出して、その差の絶対値を書いたボールと共に箱に戻す
問題文をまず誤読して、箱から取り出したボールはもう使えないのかと最初思っていました。
最初に、{A_i}の最大値よりもKが小さいかどうかチェック。
{A_i}の最大公約数を調べて、Kがその倍数なら作れます。
終わり。
B問題以降は消え去りました。完。
順位531位 パフォーマンス1516 新レート1899(-37)
レートがみるみる溶けていくぅ～～～
2017 ICPC国内予選
参加しました。
チーム名はIQ94(由来は1994年生まれだから)
チームメンバー hyksm ホハム(mtsd) polyomino
でした。
始まる前のチームとしての作戦は以下の通り。
hyksm : (重そうな)実装担当
polyomino : 考察+実装
mtsd : 考察
要するに(私は使い物にならないので) hyksmとpolyominoで交互にコーディングしていこうという話でした。
各人の適正を考えるとこうするしかないという感じでした。
（要するに僕は考察でどうにか成果を出せということ）
では実際。
スタート直後、印刷をpolyominoが、hyksmがA問題をそのまま解き始める。
polyominoの印刷スピードは最速感があった。
最初の問題の割り振りは以下のようになった。
B問題:polyomino
C問題:mtsd
読んでるうちにAを通す。polyominoがBを解き始める。hyksmにC問題の概要を伝えると、「もっと後ろを解いて」とのこと。
とりあえず、全体の問題を流し読みして、F問題のような話は数学の問題として見たことがあったので自分が解きにいかないとという気持ちになる。
B問題polyominoが実装で微妙に詰まったらしく、hyksmにコーダー交代。先にCを解いてそのままBを解くという流れに。
その間にD,E,Fを2人で考えることに。
DはXORをとって0になるような選び方の最大値だよなぁと思ったがよくわからない。制約どうやって使うんだ？多分DPでしょ？ナップザック問題だけどbitDPは無理だな？？と分からない。
Eは論理変数も少ないし、文の長さが十分短いので全部先に列挙させればいいな、構文解析やればいいなという感じに。
A~Cを解いたhyksmと、polyominoがEをどっちが書くか相談。hyksmに一任。
あとの二人はDとFを考える。
Ｆは0-indexで始めると絶対見通しがいいと思って図をひたすら書く。一回折り曲げた後は重なった部分は同一視して～～とかいろいろ考えるも泥沼にはまっていく。2^3のパターンとかを書き始めるが、これで本当に分かるのか？と悩み始めツライ感じに。延々1時間半は悩む。
（shurikenがこうすりゃいいんじゃん！みたいなことを言っているのが聞こえてさらに心がやられる)
hyksmがEを通し、DとFをチーム全員で考え始める。とりあえずそれっぽいことをhyksmに適当に言ったら、（たぶん関係なく）hyksmが4分割すれば行けそう！と言い始めそのままコーディングへ。
polyominoとDを考え始める。2部グラフでどうにかする？無理そう、流石にＤじゃでないだろみたいな感じでやっぱDP系か～という感じに。変数としてpair<それまでの選んだ個数、XORした値>みたいなものを考えるんかなぁ～という話になり、もしかしてsetにバンバン追加してけばいいんじゃね！？という感じに。適当な（嘘）計算量解析によりなんか行けそう！とか適当に言ってみる。とりあえず紙コーディング。
ここらへんで上位陣が全部東大でひえぇ～～～～って思う。
F上手く行かないということになり、コードを印刷して、デバッグへ。その間にDを書き始める（残り30分切っていた）。
ついに僕がコーディングすることに。10行くらい書いたところでpolyominoが印刷から帰ってきたので交代。ペアコーディングに。一通り書ききって動かしたら止まらない。setの追加の位置がダメ→修正→string用に書いたXORがおかしい→修正→サンプル通る！
ギリギリのケースで間に合うか不安になるもとりあえずテストケースを投げる。やはり時間がかなりかかって焦る。
hyksmがFを修正しながら、後でDの答えが返ってくるのを待つ（残り15分くらい）。
D1個目通る！D2個目へ。hyksm怒涛のF修正！
D2個目もプログラムが終了！提出！Congratulation!!(2:50:59)
残り10分、Fの修正を見守る。なんかオーバーフローが起きている→1<<n を(ll)1 << n に修正→サンプルあってる！
テストケースを落として提出！Correct!もう一個提出！Congratulation!!(2:56:50)
終了～
結果 6完 11位（学内順位7/10) （学内予選酷すぎる）
shurikenチームはおめでとうございます。
結果、完全にhyksm様様でした。
F、チーム作戦的にも問題的にも自分が解けないといけない問題だったのにやらかしてしまって本当に悲しい。焦ってもいいことはないね。算数勢辞めます。
来年はhyksm神がいないので、もっと研鑽を積んで実装の鬼になろう（か他のプロを呼んできたい）と思います。
おまけ。
家に帰って最初にやったこと。
う～んｗ終わり！ｗ
