2017-12-01から1ヶ月間の記事一覧

パソコン詳しくない系競プロ勢向け正規表現

この記事は「競プロ!!」 競技プログラミング 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 を開催しました。 ご参加いただいたみなさま、ありがとうございました。 楽しんでいただけたなら幸いです。(そして毎年一緒に運営を手伝ってくれるじゃっぷるさんにも感謝です) あと、アンケートに回答してくださったみなさまありがとう…