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

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

JOI予選

JOI 二次予選 2021 E - スパイ 2 (AOJ ????, 難易度 10)

面白かった。 問題へのリンク 問題概要 人がいて、それぞれ「スパイ」か「非スパイ」かのどちらかである。 人のうち、何人かについてはスパイかどうかが予めわかっている ( で与えられる)。 個の証言がある。各証言は人 が証言者によってなされ、「人 はスパ…

JOI 二次予選 2021 D - 安全点検 (AOJ ????, 難易度 7)

難易度 8 でもおかしくないと思った。 B や C より易しい気がしなくもないけど、本番の緊張感で B や C を飛ばして D を本気で考える決断はなかなかできなさそう。今回は B - パンケーキを見て冷静になれたか勝負だね... 問題へのリンク 問題概要 個の工場が…

JOI 二次予選 2021 C - イベント巡り (AOJ ????, 難易度 8)

これはアレだ!!! DP の最適値そのものの値を利用して次の遷移を作る系。フクロモモンガなんかもそういう系の問題だった覚えがある。 問題へのリンク 問題概要 2 つの町 (1 と 2) がある。 個のイベントがあって、それぞれ町 において発生し、時刻 に始ま…

JOI 二次予選 2021 B - パンケーキ (AOJ ????, 難易度 8)

難しかった!!! 予選の問 2 からこういうの出るのびっくり!!! 問題へのリンク 問題概要 "A", "B", "C" からなる文字列 に対して、以下の操作を繰り返すことでソートされた状態 ("A" の前には "B" や "C" がなく、"B" の前には "C" がない状態) にするこ…

JOI 二次予選 2021 A - 往復すごろく (AOJ ????, 難易度 5)

結構アドホックで難しいと思った! 問題へのリンク 問題概要 マスが横一列に並んだすごろくが与えられる ( と番号づけされている)。すごろくの各マスは . と x と # のいずれかである。 マス とマス は X である 他のマスは長さ の文字列 で与えられる X は…

JOI 予選 2010 E - 通勤経路 (AOJ 0547, 難易度 6)

JOI 難易度 6 の中では難しい方だと思った! 問題へのリンク editorial 問題概要 のグリッドの左下マス から右上マス へと至る最短経路 (上または右にのみ移動可能) のうち、以下の条件を満たすものの個数を 100000 で割ったあまりを求めよ。 曲がってから、…

JOI 予選 2009 C - 連鎖 (AOJ 0534, 難易度 6)

いろんな実装方法がありそう。でも が間に合うので、すべての書き換え方法について でできるなら十分。 問題へのリンク 問題概要 1 と 2 と 3 のみからなる長さ の数列が与えられる。同じ数値が 4 個以上連続することはない。 この数列のうちの 1 箇所の値を…

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

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

JOI 予選 2012 E - イルミネーション (AOJ 0569, 難易度 6)

ハニカムつらい 問題へのリンク editorial 問題概要 下図で表されるようなハニカム状のグリッドが与えられる (図は問題文より)。 黒色マスは建物があるマスを表している。赤太線は、「外側」から見て見える外壁を表している。 このような のマップが与えられ…

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

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

JOI 予選 2016 D - JOI国のお散歩事情 (AOJ 0622, 難易度 6)

手を動かしてみると、どうなってるかが見えてくる! 問題へのリンク 問題概要 人がそれぞれ座標 に並んでいる (単調増加、負もありうる、各 は偶数)。そして時刻 0 において、 人はそれぞれ正の方向 ( で与えられる) または負の方向 ( で与えられる) に 1 秒…

JOI 二次予選 2020 D - テンキー (AOJ 0675, 難易度 7)

本選参加のボーダーとなった問題らしい!それにしても JOI は実装が重たい...!!! 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 初期状態では下図のようなテンキーの「0」のところにカーソルがある。 上下左右への移動 ボタンを押す (315 …

JOI 予選 2015 F - 財宝 (AOJ 0613, 難易度 8)

スライド最小値の練習 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 個のアイテムがって、それぞれ市場価値 と貴重度 が与えられる。 今、A さんと B さんがそれぞれアイテムのうちの何個かをとる。このとき、A さんと B さんは同じアイテム…

JOI 予選 2019 D - 日本沈没 (AOJ 0655, 難易度 6)

これまたちょっと重たい。。。 問題へのリンク 問題概要 折れ線グラフが与えられる。これは に対して () を結んでいる。あらゆる水平な直線を考えたときの、折れ線グラフのうち直線の上に来ている部分を連結成分ごとに分解したとき、連結成分の個数として考…

JOI 予選 2019 E - イルミネーション (AOJ 0656, 難易度 7)

区間についてどうのこうのする問題、大抵は DP! 問題へのリンク 問題概要 個の整数 がある。これらのうちいくつか選んだ合計を最大化したい。ただし、 の区間 [ ] があって、選んだ数のどの 2 つをとっても同一区間上にならないようにしなければならない。 …

JOI 予選 2019 F - 座席 (AOJ 0657, 難易度 11)

挿入 DP。。。TDPC O - 文字列を複雑にした問題。アイディアはシンプルだけど詳細詰めが重たい。。。 問題へのリンク 問題概要 個の正の整数 が与えられる。 が 個 が 個 ... が 個 を合わせた 個の数を並べる方法のうち、どの隣り合う箇所も数値の差が 以上…