CODE FESTIVAL 2015 本戦、あさぷろ、リレー
遅くなりましたが、コード祭りのすべての?問題が公開されたようなのでそろそろ書かないわけにはいかないなぁ、と。
本戦
わりと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で、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 参加記(コンテストの問題については別記事で)
いや、まぁ最高のコンテストだった、という感じ
コンテストの問題に関してはオープンコンテストのほうに自分の解答を上げなおしてからまた記事書きます。
(リレーとかあさプロとかのオープンコンテストどこですか)
……。
なんかめんどいんで自分のツイートをぺたぺた貼る記事にします。
六本木に着く
これ、矢印は前を指してるけどこれはワナでほんとは左後方 #codefes pic.twitter.com/I9KZcigreg
— りあん (@rian_tkb) 2015, 11月 14
#codefes pic.twitter.com/fPaRKveIIn
— りあん (@rian_tkb) 2015, 11月 14
本戦前
パーカーパーカーパーカーパーカーパーカーパーカーパーカーパーカーパーカーパーカーパーカーパーカーパーカーパーカーパーカーパーカーパーカーパーカーパーカーパーカー
— りあん (@rian_tkb) 2015, 11月 14
なんとかパーカーを得る(最終的に65位/200人)
お疲れさまでした pic.twitter.com/dOgvlbZcQp
— りあん (@rian_tkb) 2015, 11月 14
こっから2時間くらいツイートがないが、🍣食ったりコードゴルフしたりコードゴルフしたりしていた(はず)。
ホテルに移動
I'm at 品川プリンスホテル (Shinagawa Prince Hotel) in 港区, 東京都 https://t.co/0YlbmqpsnV
— りあん (@rian_tkb) 2015, 11月 14
なるほど #code_festival pic.twitter.com/qzOuk7JRs6
— りあん (@rian_tkb) 2015, 11月 14
ごちうさ、控えめに言って最高
#code_festival pic.twitter.com/NJd6NMpRWY
— りあん (@rian_tkb) 2015, 11月 14
姉が来て以来のココアのポンコツっぷりが面白い
— りあん (@rian_tkb) 2015, 11月 14
あぁ〜、心が洗われる〜〜〜
— りあん (@rian_tkb) 2015, 11月 14
#code_festival pic.twitter.com/9TdCpJF0go
— りあん (@rian_tkb) 2015, 11月 14
ちゃっくくん、葦くんと合流しアスタリスク、終物語を見つつ女子会
ちゃっく葦とアスタリスク見てる
— りあん (@rian_tkb) 2015, 11月 14
ポコポコチーンがポポポチンチンに聞こえたっつって3人で笑い転げてた
— りあん (@rian_tkb) 2015, 11月 14
結局まだちゃっく葦とIQ-10000みたいな話してる
— りあん (@rian_tkb) 2015, 11月 14
ようやっと解散した
— りあん (@rian_tkb) 2015, 11月 14
お風呂入ろうと思ったときになぜか短縮王の問題を開いてしまい、無限に時間を溶かす
これはACのやつだけ表示してるので、実際にはこの10倍くらい投げてる
結局寝たのは6時過ぎ(湯船で寝落ちしてた)
むり、ねむい #code_festival pic.twitter.com/T7GuuDDCKu
— りあん (@rian_tkb) 2015, 11月 14
睡眠時間:30分
あさプロの前に朝風呂してたら完全に湯船で寝ていた
— りあん (@rian_tkb) 2015, 11月 14
全ては短縮王が悪い
— りあん (@rian_tkb) 2015, 11月 14
二日目、あさプロ中も短縮王のD問題頭から離れず、なんとかEasyとの共通問題だけ通す、両端キューが欲しい人生だった
あさプロから1時間、ずっと短縮王を頑張り終了10分前になんとか1Byte更新してD問題C言語2位に(完全に自己満足)
更新した!!!!! pic.twitter.com/P5YiIGevWW
— りあん (@rian_tkb) 2015, 11月 15
shinh氏のトークライブとか見た、きがする。
そしてチーム対抗リレー、本戦65位なので7問目のG問題を解く
dpやるだけ問題をアホなバグらせかたして8分くらい使ったしつらたん
— りあん (@rian_tkb) 2015, 11月 15
ハッピータイムで無事にぼっちをし、コード祭り終了
総括
うーん、楽しかったけど昨年より力不足を感じる2日間だった…、
— りあん (@rian_tkb) 2015, 11月 15
順位的には65位だし悪くはないんだけど、やっぱもう一問解きたかったしそれ以外のコンテンツについてももうちょいうまくやりたかった
— りあん (@rian_tkb) 2015, 11月 15
宇宙ツイッタラーさんに顔を覚えられていて嬉しかった
— りあん (@rian_tkb) 2015, 11月 16
ほんとにこのツイートの通りで、予選A全完で突破したし、本戦の順位も上げたし、リレーでも比較的むずめな問題を通せたので結果だけを見ると地力があがっているようにも見えるのですが、内容を見ると必ずしもそうでない気がして、あまり去年から変われていないのではないか、もう成長できないのではないか……、という慢性的な不安に襲われてつらみ
おまけ
ゆびーと楽しすぎか? pic.twitter.com/MbsWHipFkK
— りあん (@rian_tkb) 2015, 11月 15
いや~、最高の2日間だったな!!!👍✌👌👏
CODE FESTIVAL 2015 予選A
お疲れさまでした。Dで無限にバグらせて94位でした。登録フェーズで落ちてなければ本戦へ行けるはず。
A問題 : 末尾の2014以外は大文字英字らしいので適当に置換してあげればよさげ
B問題 : sum = sum * 2 + a[i] を繰り返す
C問題 : (a[i] - b[i])が大きい順に使っていくのが最適
D問題 : まぁ二分探索。k分で終わるかどうかは左側から貪欲に塗っていくことにより で判定できる。よって全体で 。
自分のいる場所がまだ塗られていない場合は左から行ってUターンするか右から行ってUターンするかのどちらかよい方を選択する必要があることにしばらくしてから気づいた。
めんどいのであんま追記する気なし……
提出だけ置いときます。
http://code-festival-2015-quala.contest.atcoder.jp/submissions/all?user_screen_name=riantkb
Typical DP Contest I - イウィ
DPコンですが、深夜にこねくり回してたらDPを使わずに で通ってしまったので誰か撃墜求む、という感じ。
問題はこちらtdpc.contest.atcoder.jp
で、まぁ私の考えたこととしては、まずこれらが言えます。
文字列sに対し操作の回数の最大値を とおくと、
・端に"w"があっても変わらない
・"ww"があると、そこのwは操作により消すことができないので、そこで文字列が分割される
上の2つは簡単に言えて、これらを用いると任意の入力に対して、それを両端がiでかつwが連続しない文字列に分解してそれぞれの最大値の和を考えればよくなります。
ここからが重要で、上の分解により生成された両端がiでかつwが連続しない文字列に対し、以下の仮説が立てられます。
文字列sに含まれるiの個数を 、wの個数を とすると、上記を満たすsに対し、
つまり、両端がiでかつwが連続しない文字列は、適切な順番で操作を行っていくことによりwがなくなるもしくはiが1個以下になるまで操作ができる、というものです。めっちゃびっくり。
その方針で書いたのがこちらtdpc.contest.atcoder.jp
なるほど通ってしまった……。
自分でも反例を考えたのですが思いつかず。誰かつよいひとに正しいのかどうか判定してほしさがある。
なんだかんだ一晩で3問通し 10問/20問。ただ、後半はマジで解ける気がしない。
ナップザックもうまく解けたので記事書くかも
TTPC2015参加記
オンサイトでチーム参加してきました。相方はちゃっくくん。
ほんとは六本木で迷子になった話とか書きたいんだけど冗長になりそうなので略。
5時間悩み続けた結果、A~Fの6完。あと1, 2問解きたかった感もあるけどまぁ上々の出来じゃないすかね。
各問題について、格闘した時系列になんやらかんやら。
A : 3秒ほど眺めてこれはちゃっくくんに任せて大丈夫そうだ、と思いスルー。この間にFあたりまで読み進める。
B : 後ろから貪欲なのは少し実験してわかったので、ちゃっくくんに伝える(コーディングしないニート)。
C : 実験したら規則が見えたのでまぁ書くかぁ、という感じになり、ここでニートから脱却する。
無駄に2WA生やしたの何も言えねぇ。
D : 全探索~~~。全探索を書くのが大の苦手なのでちゃっくくんに投げる。
C++での string -> long long の変換方法がわからないクソ雑魚を晒したのと1は素数でないのでWAを生やす。
E : k = 10 なのでここを使うんだろうなぁ、と思いつついい案が思いつかず飛ばす。
F : 金額の桁が0か9のときしか3行一致しないのはすぐにわかったので、ちゃっくくんに貪欲を書いてもらったがまぁWA。飛ばす。
G : 最大流問題かなぁ、っつって大量に辺を張った。一個の頂点に一回しか来れないようにする方法(inとoutで一点を二点に分け、間に容量1の辺を張る)は覚えてたのだが来た辺によって行ける辺を制限する方法はわからず、試行錯誤して9WAとか生やす。冷静に考えて通らなさそうだしさっさと退散すべきだったか。
F : 仕方ないし桁DPやるかぁ、っつって見えてたけど見ないふりをしていた桁DPで書く。なんかよくわかんないDPをしてしまったが大きくバグらせることもなくAC。
E : ちゃっくくんが必死にEをやっているのを横目で見て、嘘解法ちっくなの書いてみるか……、っつって色を反転させた周囲3行3列にだけ注目したコードを書く。forループが6重とかなってぅゎなにこれきもぃ、って感じだったけど通る。
しばらくGを考えた後、Jの部分点を狙いに行くがめんどい、死ぬ~~~、っつって死んだ。終了。
あと、H問題に関してはコンテスト中の考察は完全に解説の通りであとは実装するだけ、みたいな感じだったのですが、幾何めんどい(点と直線の位置関係とか点と三角形の内包判定とか四角形の面積とか)ってなってやめました。おわり。
楽しかったですがやはり力不足を痛感したので、もっと精進します、といった感じですね……。
あとは、やっぱり後半少しちゃっくくん退屈させちゃったかなぁ、というのもある。
地力つけて来年はもっと頑張るぞ~~~