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

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

2019-09-16から1日間の記事一覧

AtCoder ABC 054 C - One-stroke Path (水色, 300 点)

グラフの探索を頑張る問題。現代の AtCoder であまり見ないけど、教育的な全探索問題!!! 問題へのリンク 問題概要 頂点数 、辺数 の無向グラフが与えられる。このグラフ上で頂点 1 から出発するハミルトンパスが何本あるかを数え上げよ。 なおハミルトン…

AtCoder ABC 057 C - Digits in Multiplication (緑色, 300 点)

整数に関する問題でまずは直面する典型的な事柄を学べる教育的問題!! 例えば整数 が素数かどうかを判定するのは、実は から まで順に試し割りすればよいという話など。 ただ、現代の ABC なら灰色 diff になりそうである。 問題へのリンク 問題概要 正の整…

AtCoder ABC 064 C - Colorful Leaderboard (茶色, 300 点)

あるあるあるある。 問題へのリンク 問題概要 人がいてそれぞれの AtCoder レーティングが与えれている。1 以上 4800 以下で、400 ごとに色が変わるという設定。 今、レーティング 3200 以上の人は自由に色を変えることができる。このとき、 人の中に存在す…

AtCoder ABC 141 F - Xor Sum 3 (黄色, 600 点)

Xor Sum シリーズしゃん。典型てんこ盛り!!! XOR は各桁ごとに独立に考えるとよい XOR に関する問題は mod. 2 での方程式みたいになることも多い であることから上位の桁から辞書順的に優先で考えるような貪欲が決まる などなど。 問題へのリンク 問題概…

AtCoder ABC 140 C - Maximal Value (灰色, 300 点)

数学嫌いの方は問題文読んだ瞬間に一瞬敬遠心が生まれてしまうかもしれない...でも落ち着けば難しくはない 問題へのリンク 問題概要 長さ の数列 (具体的な値はわからない) に対して を満たす数列 が与えられます。 の総和として考えられる最大値を求めてく…

AtCoder ABC 061 C - Big Array (緑色, 300 点)

「k 番目を求める」に関する典型的な処理を要求される問題。 問題へのリンク 問題概要 空集合 に対して、以下の 回の操作を行う: に整数 を 個挿入する 回の操作後の S において 番目に小さな値を求めよ。 制約 考えたこと この問題の注意点として、 を具体…

AtCoder ABC 141 D - Powerful Discount Tickets (緑色, 400 点)

問題を読み替えつつ Greedy!!! 問題へのリンク 問題概要 個の品物があって、それぞれ 円で売られている。今 枚の魔法の割引券があって、品物を買う際に割引券を好きな枚数使うことができる。 円の品物を買う際に 枚の割引券を使った場合、その品物を 円で…

AtCoder ABC 141 C - Attack Survival (灰色, 300 点)

ちょっと視点を変える感じ。 「反対側とか補集合とか余事象とか考えてみると解ける」という感じの問題は、300 点あたりからよく出てくる 問題へのリンク 問題概要 人がいてそれぞれ ポイントずつもっている。 これから ラウンドのクイズがあって、 ラウンド…

AtCoder ABC 141 E - Who Says a Pun? (水色, 500 点)

文字列検索に関するライブラリが充実していれば怖いものがない。でも文字列のことを知らなくても実は DP でも解ける!!! Suffix Array Z-algorithm (editorial 解) ロリハ + 二分探索 「ロリハ + 二分探索」の高速化 (editorial のラスト 3 行で言及された…