うにゅーん、って感じだ

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

No.335 門松宝くじ, No.336 門松列列

yukicoder

奇跡的に全完できたけど、普通にクソ苦手なセットだった
門松列の流行早く終わってくれ

No.335 門松宝くじ - yukicoder
No.336 門松列列 - yukicoder



門松宝くじは、当確率である2つの数字が選ばれたとき、3つの数字が門松列かつ3つの数字のmaxが最大になるようにもう1つの数字を選ぶようにして、そのときのmaxの期待値を出す問題（自分でも何を言っているのかわからない…）

普通に全部の選ばれる数字の組（{_nC_2}通り）に対して ({n-2})通り全探索すると {O(n^3)} となりダメ（最初、800^3 = 2400万だと勘違いしてこれで出した）


そこで、選ばれた2つの数字について具体的に考えていきます

  • 選ばれた2数a, b(a < b)について、元の順列におけるindexが index[a] < index[b] のとき

下図(横軸 : index, 縦軸 : 数値)で適当に赤く塗られたところの数をあと一つの数として選べば、3数は門松列になります
f:id:riantkb:20160118132310p:plain

ここから、実は区間のMaxとminさえ持っていれば良いことがわかります

max[i][j]を区間[i, j]におけるMax、min[i][j]を区間[i, j]におけるminとすると、

max[0][index[b] - 1] > b のとき ...... 得点は max[0][index[b] - 1]
max[0][index[a] - 1] > a のとき ...... 得点は b
min[index[b] + 1][n - 1] < b のとき ...... 得点は b
min[index[a] + 1][n - 1] < a のとき ...... 得点は b
上のいずれにも適さないとき ...... 門松列を作れないので得点は 0

max[i][j], min[i][j] を前もって {O(n^2)} で求めておけば、各組に対して定数時間で求めることができ、結果 {O(m n^2)} となります

index[b] < index[a] のときも同じような感じで求めることができます



門松列列は、順列の並び替えの中でジグザグな列は何通りあるか、という問題
（どっかで見たことある気がするけど、題意は {a_i < a_{i + 1} < a_{i + 2}} または {a_i > a_{i + 1} > a_{i + 2}} となる i が存在しないことと同義）


まぁ、DPを考えます。


i - 1番目の数がi番目の数より大きかったかどうかで、i + 1番目にどのような数を置けるかが決まります
（例えば ......, 6, 4 というところまで数列を作っていたら、次の数は5以上でなければならない）


使える数字は決まっていて、一度使った数字は使えないので、次に置ける数字がm個、次に置けない数字がn個だとすると下図のようになります
f:id:riantkb:20160118135420p:plain

このとき、次のような漸化式が成り立ちます

dp[m + n][m] = dp[m + n - 1][n] + dp[m + n - 1][n + 1] + ... + dp[m + n - 1][m + n - 1] (dp[0][0] = 1)
（dp[m + n - 1][k] は、次に置ける数の中でk - n + 1番目に小さい数を選んだときの場合の数）


これをこのままループを回すと {O(N^3)} となりますが、
sum[i][j] = {\sum_{k = 0}^{j - 1}} dp[i][k]
を順次求めておけば {O(N^2)} となり、間に合います


求めるものは、sum[N - 1][N] * 2 です


なんかすごい変なDPをしている自覚はあります......


それぞれ、提出はこんな感じです
#71404 No.335 門松宝くじ - yukicoder
#71459 No.336 門松列列 - yukicoder

(P,Q)-サンタと街の子供たち 解説(?)

yukicoder Advent Calender Contest

なんかめっちゃ面白い問題だなぁ、と思いかつ上手くハマって解けたので、つたないですが解説記事を書かせていただきます。
(お昼に間違ってフライング投稿しちゃってて慌てて非公開にしましたごめんなさい＞＜)


問題はこちら
No.321 (P,Q)-サンタと街の子供たち - yukicoder


ナイトはチェス盤のすべてのマスに到達できるが、それ以外の距離の移動のみではどうなるか？ というもの


まずは、例外処理から（以下、{p \leq q} とし、各座標はすでに絶対値を取ってあることとします）

  • (p, q) = (0, 0) のとき

自明に動けないので、 {(x_i, y_i) = (0, 0)} となる点がいくつあるか探します（ {i \neq j \Rightarrow (x_i, y_i) \neq (x_j, y_j)} が書いてなかったように思うのですが、できればどちらか明記していただけるとありがたかったかも、書いてあったらごめんなさい＞＜ ）。

  • p = 0 のとき

{gcd(x_i, y_i) \% q = 0} ならばいけるので探します。

  • gcd(p, q) > 1 のとき

必要条件として、{gcd(x_i, y_i) \% gcd(p, q) = 0} が挙げられます。かつ、p, q が互いに素となる状態にして後述の条件を満たすか判別すればよいです。

  • p, q が互いに素のとき

とりあえず、チェス盤を考えます。
f:id:riantkb:20151214140311p:plain

まず、ナイトと同じな (p, q) = (1, 2) のときを考えると、最初は (0, 0) の白マスにいて、移動した先は必ず黒マスになっています。
次に、(p, q) = (1, 3) を考えると、白マスにしか到達することができず、絶対に黒マスに到達することができません。


ここで、次のような仮定をすることができます。

「すべてのマスに到達できる ⇔ gcd(p, q) == 1 かつ (p + q) % 2 == 1」
　かつ、
「gcd(p, q) == 1 かつ (p + q) % 2 == 0 ⇔ すべての白マス( (x + y) % 2 == 0 ) に到達できる」

本番では、私はこれを証明せずに投げて通してしまいました。


ここに証明を書いてもいいのですが、writerさんが解説ページで証明っぽいのをなされているのでここでは割愛させていただきます（めんどいし）。
http://yukicoder.me/problems/849/editorial


23分ほどでACし、7番目くらいでした。あんまこじらせないでさっと行けてよかった……。

自分の提出
http://yukicoder.me/submissions/65503

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日間だったな！！！👍✌👌👏