この記事は、「『競プロ!!』 競技プログラミング Advent Calendar 2017」の 20 日目の記事として書かれました。「数え上げテクニック集」を pdf として公開しました。最近の数え上げの問題を解くテクニックを体系的にまとめた資料です。想定している対象読者…

解説に少し頼りました。 問題概要 http://agc012.contest.atcoder.jp/tasks/agc012_f 思考の道筋 ある操作で作りうる列を数えるときは、同じ列ができる操作列の同値類から代表元を一個取ってきてそれを数える(できた列に対して、何らかのgreedyで操作列を一…

twitterで「たとえ頭が良くても、相手の気持ちを汲み取らず、正論を振りかざして相手を傷つけるのは許されない」という主張を見たので思ったことを述べる。 まず、主張自体はよくあるものであり、我々がよくやるように「ただの僻み根性」として一笑に付して…

Petrozavodsk campの北朝鮮セットであった問題で知見を得たので書き記しておきます。 問題 分割数の N 番目を求めよ。 解法 まず、DP[N][K]: K個の和でNを作る場合の数 とする。 1を使う場合と使わない場合に分けると、DP[N][K]=DP[N-1][K-1]+DP[N-K][K] が…

こんにちは。たまには有機的な投稿をします、DEGwerです。twitterで基本情報技術者試験、というものが話題に上がっていたので、過去問を解いてみることにしました。 筆者紹介 大学3年。中学3年のときに競技プログラミングを始める。開発経験なし、開発意思な…

解説を読んで実装した。FFTの練習。 問題概要 愚直DPを高速化してください 解法 DPの遷移の係数を求める式を見ると、DP列とある列との畳み込みになっている。FFTして一件落着！と行きたいところだが、DP[i]を求めないとDP[i+1]が求まらないので、オンライン…

問題概要 {1,2,...,N}^K の点を頂点とした K 次元超直方体を重ならないように M 個置く方法は何通りあるか。 解法 超直方体同士が重ならない どこかの次元でその超直方体が占める区間がdisjoint なので、1次元の場合に区間がどういう重なり方(M 区間のそれぞ…

見た目が解けるものに見えないが、実は解ける。見た目とのギャップがすごい。 問題概要 平面上にN点与えられるので、N点全てを一回ずつ使うサイクルを作って、隣り合う2点間のマンハッタン距離の総和を最大化せよ。 解法 x座標の中央値とy座標の中央値で切っ…

前4問は何だったのかという感じの良問。問題概要: 区間がN個与えられる。この区間たちに 1 or -1 を割り当てて、どの座標でもそれを含む区間の値の和の絶対値が 1 以下になるようなものを構成せよ。解法: まず全座標がdistinctなときにできるなら適当に順番…

最近、おかしな夢をよく見る。居眠りをしているときに、よく見る夢だ。 その夢は、それを見たのかどうかすらも分からないほどに抽象的で、一切の物理的な動きを、五感の働きを、焦りを、緊迫を含まない。一切の具体的な印象は、残らない。ふと目が覚めると、…

何かに熱心になること、そのことしか考えられないほど熱中すること、そして、純粋に好きという気持ちだけでそれを続けられること。 それは素晴らしいことだと思うし、皆そう思っている。寝るのも忘れてバットを振る野球選手は美しいし、ただひたすらに作品を…

変な問題だけど解法はそこそこきれい。パス長とサイクル長のペアたちが満たすべき条件は、 各サイクル長に対し、パス長0の点の数はサイクル長の倍数(サイクルをいくつつくるかの条件) 各サイクル長に対し、パス長xの点が存在しないならパス長x+1の点も存在し…

新年初AC。GoodByeのボス。今年(去年)のは骨がない。s-t間に2本の辺素パスが取れるという条件は、Mengerの定理より1点を取り除くとs-tが非連結になるという条件と同値なので、1点白いマスを除いてs-tを非連結にできるか判定すればいい。これは、追加する黒い…