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

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

2020-03-22から1日間の記事一覧

AtCoder ABC 159 F - Knapsack for All Segments (600 点)

ごちゃごちゃとばぐらせながら何とか通した... 問題へのリンク 問題概要 要素の数列 が与えられる。この数列の 通りの区間それぞれについての 区間内の要素の部分集合であって総和が であるものの個数 の総和を求め、998244353 で割ったあまりを求めよ。 制…

AtCoder AGC 018 A - Getting Difference (300 点)

操作の仕方が Euclid の互除法そのものになっているタイプの問題。 問題へのリンク 問題概要 要素数 の数列 が与えられる。これに対して以下の操作を好きな回数だけ行うことができる: 整数を 2 つ選び、その差の絶対値をとり、それを数列に新たに挿入する 整…

AtCoder AGC 043 D - Merge Triplets (1200 点)

めちゃくちゃ楽しかった 問題へのリンク 問題概要 長さ の数列を 個用意する。ただしこれらのなす 個の値は が 1 個ずつ登場するようにする。これらの数列から以下の操作を繰り返して、長さ の順列を作る。 空にならずに残っている数列のうち、先頭の要素の…

AtCoder AGC 043 C - Giant Graph (900 点)

これはマジで天才やと思うやが... いや本当にどこから Grundy 数を導けるのか、わからぬ... 問題へのリンク 問題概要 頂点数 のグラフが 3 つ与えられる。それらのグラフのカルテシアン積を考える。この頂点数 のカルテシアングラフの独立集合のうち、以下の…

AtCoder AGC 043 B - 123 Triangle (700 点)

答えが 0, 1, 2 の三通りしかないとなれば、mod で絞るのをやりたくなる! 受験数学では定番のテクニックだ!!! 問題へのリンク 問題概要 長さ の、1, 2, 3 のみからなる数列が与えられる。この数列に対して、 隣接する要素の差を書き出す という操作を、…

AtCoder AGC 043 A - Range Flip Find Route (400 点)

「予め盤面をいじることができる」という設定の問題にはある程度の定石があるように思う! 問題へのリンク 問題概要 の盤面が与えられ、左上から右下まで行きたい。'#' マスは壁を表し、'.' マスは通路を表す。 予め盤面に以下の操作を行うことができる。最…