うにゅーん、って感じだ

だいたいのコンテストサイトで橙か赤です、よく C#を書きます。

happy b1rthday 2 me 解説

yukicoder Advent Calender Contest

Advent Calender Contest 12日目の問題を担当しました、はい。

コンテストページ
順位表- yukicoder

問題
No.319 happy b1rthday 2 me - yukicoder


解説はこちら

www.slideshare.net
めっちゃ頑張って作ったしみんなみちくり～


最初のほう全然解かれなくて☆4の機運が高まってたけど、23時時点で24人の方々に解かれたので、まぁよかったかなぁ、という感じです

24時間で1問とか激ヤバ、かつペナルティなしなコンテストなので、多少実装がめんどくても、多少WA狙いなサンプルケースでもゆるしてちょ、って感じ＞＜

一応、想定解のコードっぽい何かです
http://yukicoder.me/submissions/62385


このような拙い問題を皆さま解いていただき、本当にありがとうございました


なんかそのうちもうちょい追記するかも

CODE FESTIVAL 2015 本戦、あさぷろ、リレー

CODE FESTIVAL

遅くなりましたが、コード祭りのすべての？問題が公開されたようなのでそろそろ書かないわけにはいかないなぁ、と。



本戦

わりとFAを狙ってCから解きました（ただしバグらせた模様）

C : 貪欲に🍣を作ればよい、というのはすぐに見えたんだけど、焦って101みたいなのを2個とカウントしたりとかして7分とかかかった

A : やるだけ

B : まぁN = 1を見落として1WA

D : N-1点、つらい……、という感じ。書きながら考察していくうちに、N点取るのと同じ人数必要か一人少なくても大丈夫か、というのは最大人数必要な時間を全て含有するような区間があるか、というようにすればよい、というのはわかったのだけれど、途中から時刻の最大値が100000だったのをNだと勘違いしてて10分くらい溶かした、死にたい

E : まぁ貪欲にパターンに当てはめて短くしてくんだろうなぁ、と思いはしたけれど、
これ'!'が含まれているときは、入力が0かそれ以外か、出力は1, 0, -1の3通りのみ、となるので、元の式に0と1を当てはめて、その出てきた値がどれになっているか、という9通りに対して全てあらかじめ最短コードを求めておけばよいのでは……！ っつって実装しました。
まぁコードを見てもらった方がはやいcode-festival-2015-final-open.contest.atcoder.jp
結局4通りしか見つからなくてそのままほい～、っつって投げたら通ってしまった、うん


と、ここまででちょうど1時間、といったところ

あとの2時間は何をしていたかというと、主にF問題の考察をしていたり、G問題の指数時間解を書いていたり（とほほ）していました
パーカーボーダーが5問になっていなかったらまた泣き寝入りしているところだった……
結果としては65位、感想とか思うところはこの前の記事で書いた気がするのでまぁいいや



あさぷろ
眠い、短縮王のせいで無限に眠い


ほんとは、短縮王についても自分の頑張りをすごくこの場で主張したいんだけど、普段からコードゴルフしているような人々にとってはあたりまえ体操だろうから出す先がない……
コードゴルフはこれから細々とやっていきたいっすね


閑話休題


あさぷろの問題については、Easyとの共通問題しか解けず

Aは普通に計算したけど、二分探索とかしても普通に間に合ったのかなぁ、どっちが実装楽かは個人差ありそうだけど
BはN = 100なので分割する場所をずらしながらLCSで{ O(N^3) }、LCSは適当にそこら辺からdpコピペしてきた

Cは終了後にLinkedListから普通の配列（しゃくとり）に直したら通った、つらみ


リレー
リレーは本戦65位なので7問目を解く
これcode-festival-2015-relay.contest.atcoder.jp

パッと見やべぇわかんねぇw とか思ったけどよく見たら副菜のdpテーブル作っておいてそこに主菜をひとつひとつ当てはめていったときのmaxを見ればいいだけ

っつって実装しに行ったら緊張してたのか、クソみたいなバグで10分くらい溶かした、死にたい

当日のACコードcode-festival-2015-relay.contest.atcoder.jp

あとはBを解いたりJを試すみたいなことをしていた

CODE FESTIVAL 2015 参加記（コンテストの問題については別記事で）

CODE FESTIVAL

いや、まぁ最高のコンテストだった、という感じ

コンテストの問題に関してはオープンコンテストのほうに自分の解答を上げなおしてからまた記事書きます。
（リレーとかあさプロとかのオープンコンテストどこですか）


……。


なんかめんどいんで自分のツイートをぺたぺた貼る記事にします。


六本木に着く



本戦前


なんとかパーカーを得る（最終的に65位/200人）


こっから2時間くらいツイートがないが、🍣食ったりコードゴルフしたりコードゴルフしたりしていた（はず）。


ホテルに移動



ごちうさ、控えめに言って最高





ちゃっくくん、葦くんと合流しアスタリスク、終物語を見つつ女子会





お風呂入ろうと思ったときになぜか短縮王の問題を開いてしまい、無限に時間を溶かす
f:id:riantkb:20151116130727p:plain
これはACのやつだけ表示してるので、実際にはこの10倍くらい投げてる

結局寝たのは6時過ぎ（湯船で寝落ちしてた）


睡眠時間：30分



二日目、あさプロ中も短縮王のD問題頭から離れず、なんとかEasyとの共通問題だけ通す、両端キューが欲しい人生だった


あさプロから1時間、ずっと短縮王を頑張り終了10分前になんとか1Byte更新してD問題C言語2位に（完全に自己満足）


shinh氏のトークライブとか見た、きがする。


そしてチーム対抗リレー、本戦65位なので7問目のG問題を解く


ハッピータイムで無事にぼっちをし、コード祭り終了


総括



ほんとにこのツイートの通りで、予選A全完で突破したし、本戦の順位も上げたし、リレーでも比較的むずめな問題を通せたので結果だけを見ると地力があがっているようにも見えるのですが、内容を見ると必ずしもそうでない気がして、あまり去年から変われていないのではないか、もう成長できないのではないか……、という慢性的な不安に襲われてつらみ


おまけ


いや～、最高の2日間だったな！！！👍✌👌👏

CODE FESTIVAL 2015 予選A

CODE FESTIVAL AtCoder

お疲れさまでした。Dで無限にバグらせて94位でした。登録フェーズで落ちてなければ本戦へ行けるはず。


A問題 : 末尾の2014以外は大文字英字らしいので適当に置換してあげればよさげ

B問題 : sum = sum * 2 + a[i] を繰り返す

C問題 : (a[i] - b[i])が大きい順に使っていくのが最適

D問題 : まぁ二分探索。k分で終わるかどうかは左側から貪欲に塗っていくことにより { O(M) } で判定できる。よって全体で { O(M \log N) }。
自分のいる場所がまだ塗られていない場合は左から行ってUターンするか右から行ってUターンするかのどちらかよい方を選択する必要があることにしばらくしてから気づいた。

めんどいのであんま追記する気なし……


提出だけ置いときます。

http://code-festival-2015-quala.contest.atcoder.jp/submissions/all?user_screen_name=riantkb

Typical DP Contest I - イウィ

AtCoder TDPC

DPコンですが、深夜にこねくり回してたらDPを使わずに { O(N) } で通ってしまったので誰か撃墜求む、という感じ。

問題はこちらtdpc.contest.atcoder.jp

で、まぁ私の考えたこととしては、まずこれらが言えます。

文字列sに対し操作の回数の最大値を { M(s) } とおくと、
・端に"w"があっても変わらない
{ \displaystyle M("w" + s) = M(s + "w") = M(s) }
・"ww"があると、そこのwは操作により消すことができないので、そこで文字列が分割される
{ \displaystyle M(s + "ww" + t) = M(s) + M(t) }

上の2つは簡単に言えて、これらを用いると任意の入力に対して、それを両端がiでかつwが連続しない文字列に分解してそれぞれの最大値の和を考えればよくなります。

ここからが重要で、上の分解により生成された両端がiでかつwが連続しない文字列に対し、以下の仮説が立てられます。
文字列sに含まれるiの個数を { s_i } 、wの個数を { s_w } とすると、上記を満たすsに対し、
{ \displaystyle M(s) = Min(s_i / 2, s_w) }

つまり、両端がiでかつwが連続しない文字列は、適切な順番で操作を行っていくことによりwがなくなるもしくはiが1個以下になるまで操作ができる、というものです。めっちゃびっくり。

その方針で書いたのがこちらtdpc.contest.atcoder.jp

なるほど通ってしまった……。

自分でも反例を考えたのですが思いつかず。誰かつよいひとに正しいのかどうか判定してほしさがある。


なんだかんだ一晩で3問通し 10問/20問。ただ、後半はマジで解ける気がしない。

ナップザックもうまく解けたので記事書くかも