この記事は「競プロ!!」 競技プログラミング Advent Calendar 2017の記事として書かれたものです。 上のリンク先にはリンクが張られていないので書いておきますが、競プロadvent calendarはもう１つあります。 昨日の記事 / 明日の記事（明日の記事がすでに…

問題 | 解説まとめまずはコードです。 このコードでやっていることを解説します。まず、各マスには「黒」または「白」ではなく、「黒」または「(1,1)~(4,4)」を割り当てることにします。 ただし、(j,k)は「j番目の白マスグループのk番目のマス」を表すものと…

問題 | 解説まとめリアクティブ・encode/decode系の変わった問題。 部分点はmax(x)に関する関数にしてもよかったかなぁ。 部分点１ 割と効率が悪くてもACできますがそこまで簡単ではないと思います。 例えばNが小さければフィボナッチ数列でいけますが、N=30…

問題 | 解説まとめ作問slackに最初に投稿した問題。 今年はこんな感じの問題にするぞという思いも込めて作りました。解法：ペイント等でゴールのラインに縦線を引き、バケツツールで塗りつぶすと・・・答え：ACEFGHNPQSYZ ペイントってBFSができるんですねぇ…

問題 | 解説まとめ1~5は全探索ができる大きさのランダムケース、6~10は大きいけれどそれぞれなんらかの性質を持ったグラフとなっています。 手元で全ての答えを計算して埋め込めばいいですね。Nが全ての入力で異なるので、ケースの特定も簡単です。 1~5 1は…

問題 | 解説まとめこのセット随一の普通の問題です。 少し言い換えると、Sから'A'をいくつか削除し、Tから'B'をいくつか削除することによってSもTもUにすることができるような文字列Uが存在するかを判定すれば良いです。 「dp[i][j] = S[0]~S[i]とT[0]~T[i]…

Xmas Contest 2017 を開催しました。 ご参加いただいたみなさま、ありがとうございました。 楽しんでいただけたなら幸いです。（そして毎年一緒に運営を手伝ってくれるじゃっぷるさんにも感謝です） あと、アンケートに回答してくださったみなさまありがとう…

IOI2017を観戦しました。師匠が圧倒的な１位を取り、日本チーム自体も金３銀１と過去最高成績で激アツでした。 金３も１，４，５位で凄すぎる。 おめでとう＆お疲れ様！ 本番から１時間遅れで問題を閲覧することができ、yandexにjudgeが立っていたので何問か…

snuke.hatenablog.com上の記事では記事中の注釈の通りMPを紹介したので、KMPとは何かを大雑把に解説しておきます。 KMPは、上の記事で紹介したMP（Morris-Pratt）にKnuthパワーが加わったものです。 さらなる考察がされて、文字列検索の効率が向上した感じで…

なんか、twitterとtweetdeckのアイコンが突然丸くなった。 四角を想定して作られたアイコンの四隅が切り取られるのはアレなので、CSSをいじって直した。 twitter社はなにを思ってこんなことをしてしまったんだろう・・・？ 直し方 まず、CSSをカスタマイズで…

通過しました。 初のGCJ決勝進出です。 GCJは現時点での第一目標だったのでとても嬉しい。 次はTCOかぁ、きっつい。今回はどれも解法がすらすらと分かったので、GCJと相性が良いのかもしれない。 （けど謎の問題（sortアルゴリズムを推測せよとか、乱択とか…

つい最近まで最小費用流の負辺除去、「なんか上手いことやれば出来ることもあるらしい」程度の認識だったんですが、ちゃんと考えてみたら自明やんってなったので書いておきます。 この記事を読めば多分、自明かどうかはともかくとして、かなり見通しがよくな…

ARC075Fとりあえず桁数を1~18まで全部試します。 例えば6桁なら、 D = fedcba - abcdef = 99999*(f-a) +9990*(e-b) + 900*(d-c)となるようなa~f（0≦a~f≦9, a≠0）の個数を数えれば良いです。 (f-a),(e-b),(d-c)みたいに端から決めていくんですが、 解説ではD…

ICPCのWFまたは多くのアジア地区予選では持ち込めるライブラリのページ数が決まっています。 また、PDFの右上にページ番号、左上に大学名を入れろという指定がついてきます。 PDF化するコマンド sublimeに印刷機能がなかったし、ページ番号と大学名を入れる…

HonestOrUnkind解いた。 面白かった、と思ってたけど想定解と違ったのでメモ。 想定解の方がシンプルで頭良い。正直者を１人特定するところが違った。まず人の組をN/2組作る。Nが奇数なら１人余る。 各組(x,y)について? x yを質問する。 'N'なら正嘘、嘘正、…

Two Faced Cardsのコンテスト中に書いてた別解です。 O(N√N logN) なのでTLEして悲しいけど紹介しておきます。 （想定解も理解したけどadhocで面白かった） 下ごしらえ とりあえずC（とA,B）を0~Nに変換しておきます。 Ai＜Biのカードは裏で使うメリットがな…

りんごさん方式の記事 正当性を証明するにはユニークな多項式の形にしてmodを素数にしておけば、Schwartz–Zippel lemmaを使えて良いっぽい？ multisetのハッシュ、0になりやすいなぁと思ったけど0になる確率がat most n/modなのか。 記事での根付き木のハッ…

ローリングハッシュや木の同型判定など、競プロでハッシュを使う機会はあるけど、衝突確率とか必要な値域についてあまり考えたことがなかったので計算してみた。ハッシュを使う場合、以下の２通りではそれぞれ衝突確率がかなり異なる。（少し考えれば当たり…