片腕生活記録

twitter.comこけて骨にヒビが入り、片腕生活になった。 利き腕が無事だったのが唯一の救いだった。片腕ギプス生活で困ったことと、以外に困らなかったことをまとめて行こうと思う。 困ったこと 寝る ギプスの厚みもあり、腕の置き場に困る 腕の下にクッショ…

CodeForces #485 Div1 C AND Graph

Um_nik回のCが面白かったので。 あと、自分の解法が想定解と違ったっぽいので。 問題概要 ビットの二進数 が 個与えられる。 のとき頂点 に辺を張ったグラフの連結成分数を求めよ。制約 はdistinct

正規表現は便利なので知らない人には少しだけでも知ってほしい(競プロ勢向け)

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

Xmas Contest 2017 I問題 SAT Puzzle 解説

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

Xmas Contest 2017 H問題 Ango 解説

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

Xmas Contest 2017 G問題 Maze 解説

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

Xmas Contest 2017 F問題 Tree Disassembly 解説

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

Xmas Contest 2017 E問題 String Problem 解説

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

Xmas Contest 2017

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

IOI2017

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

KMPのK

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

丸くなってしまったtwitterアイコンを戻す方法

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

Google Code Jam 2017 Round 3

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

最小費用流の負辺除去

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

ARC075 F 「Mirrored」 速い解法

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のライブラリPDFの生成

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

ARC070 F「HonestOrUnkind」別解

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

AGC013F「Two Faced Cards」別解(TLE)

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

根付き木のハッシュ

りんごさんがちゃんとしたハッシュについての記事を書いてくれたのでそちらを推奨しておきます。 正当性を証明するにはユニークな多項式の形にしてmodを素数にしておけば、Schwartz–Zippel lemmaを使えて良いっぽい? multisetのハッシュ、0になりやすいなぁ…

ハッシュの衝突

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

Xmas Contest 2016 I解説

I問題の解説です。

Xmas Contest 2016 F解説

F問題の解説です。

Xmas Contest 2016 B解説

B問題のギャラリーと解説です。

Xmas Contest 2016 A解説

Aの解説です。

Xmas Contest 2016 H解説

H問題の解法と雑な証明です。div.pg{display:none;}p{margin:0px;}.btn{vertical-align:text-top; margin:0px;margin-right:3px;}$(document).ready(function(){$(".pg").css("margin-left","15px");});function tgl(id,btn){$("#"+id).slideToggle("fast");…

Xmas Contest 2016

Xmas Contest 2016 にご参加いただいた皆様、ありがとうございました&お疲れ様でした。難易度が高すぎて順位表が大変なことになっていましたね。。 1問をじっくり考えるのに慣れていない方には少しつらいセットだったかもしれないです。 でも、なんだかん…

ACC2016 24日目「色塗り2」解説

Advent Calendar Contest 2016 24日目の問題「色塗り2」を出題させていただいたので、その解説 問題はこちら。div.pg{display:none;}p{margin:0px;}.btn{vertical-align:text-top; margin:0px;margin-right:3px;}$(document).ready(function(){$(".pg").css…

IOIへの出題について - 解説編

div.pg{display:none;}p{margin:0px;}.btn{vertical-align:text-top; margin:0px;margin-right:3px;}$(document).ready(function(){$(".pg").css("margin-left","15px");});function tgl(id,btn){$("#"+id).slideToggle("fast");s=btn.src;btn.src=(s.charAt…

IOIへの出題について

※この記事はCompetitive Programming (その2) Advent Calendar 2016 - Adventarの2日目の記事です。 IOIにあまり興味が無い方は、下の方の僕が出題した問題の方だけをお読み下さい。 IOIとは IOIへの問題の応募 IOIに問題が採用された時の流れ IOI 2016に…

ICPC Tsukuba 2016 参加記

慶應義塾大学のチーム「Running」として参加し、3位の銅メダルでした。 メダルを取ることが出来たのは初めてで、とても嬉しいです。時系列順で感想を羅列していきます。 コンテスト前日 つくばエクスプレスの車内で合流して、つくばのリンガーハットでご飯…