けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

幅が小さいことを利用する

JOI 春合宿 2008 day3-1 Origami (難易度 6)

一見すると典型的な「座標圧縮」+「二次元いもす法」なのだが、それだと TLE / MLE してしまう。 ジャッジへのリンク 問題文へのリンク 問題概要 のグリッド上に 枚の長方形の紙を敷いていく。 枚目の紙は を満たす座標 を覆う領域に配置される。最も多くの…

JOI 予選 2018 E - おせんべい (AOJ 0525, 難易度 6)

幅が小さいので、幅についての 通りの探索が間に合う! 問題へのリンク 問題概要 のマス目がある。各マスの値は 0 または 1 である。次の操作を好きな順序で好きな回数だけ行うことができる。 ある行を選択して、その行の数値をすべてひっくり返す (0 を 1 …

JOI 予選 2014 D - 部活のスケジュール表 (AOJ 0595, 難易度 6)

J, O, I の 3 人しかいないと、意外と bit DP を発想しづらいかもしれない。でもこういうのめっちゃ見るね。 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 J 君と、O 君と、I 君の 3 人が所属する部活動がある。 日間の活動が行われる。それ…

AOJ 2858 Prime-Factor Prime (JAG 模擬地区 2017 C) (350 点)

貴重な区間篩の問題 問題へのリンク editorial 問題概要 2 つの正の整数 が与えられる。以下の条件を満たす整数 の個数を求めよ。 の相異なる素因数の個数が素数個 制約 考えたこと が小さいので、それを活かした解法が考えられそう。具体的には区間篩が使え…

AtCoder ABC 159 E - Dividing Chocolate (水色, 500 点)

制約が縦方向の bit 管理を要求している感満載 問題へのリンク 問題概要 のグリッドがあって各マスに 0 か 1 が書き込まれている。これに対し、縦横にラインでカットして、部分長方形区域に分けたい。どの区域も 1 の個数が 以下になるようにする。 これを実…

MUJIN 2018 H - タイル張り (1000 点)

コンテスト終了後に「もう少しで解けそうだったのに...」と言ったのんな。アレは嘘だったのん... 問題へのリンク 概要 H × W の盤面を白黒に塗り分ける方法のうち、白い部分を 1 × 2 の長方形のピースで隙間なく埋められるようなものは何通りあるか? (99824…