ITエンジニアのブログ

IT企業でエンジニアやってる人間の日常について

競技プログラミング

ARC018 [C]席替え

ARC018 の C 問題「席替え」を(解説を見ながら)解きました。 i 行 j 列 (i,j) の人の成績 G(i, j) とするとき、 (a,b) まず、 x_i = (x_(i-1) + a) % p で、 a%p!=0, m*n 成績がすべて異なる値をとるとき、行は floor(G[i][j]/m) で確定し、列は交差しない…

ARC017 [C]無駄なものが嫌いな人

N 個の数値のうち、好きなだけ選んで合計を X にできるパターンの個数を求めるという問題で、 N が小さい値ならばそのまま全探索(O(2^N))すれば良いんですが、 N が 32 だと時間切れになります。解説を読むと、N 個の数値を半分に分割し、片方の合計を p, も…

bit DP で TSP を解いてみた。

bit DP どころか DP すら碌に書いたことが無いレベルだが、 ARC016 の C 問題で bit DP を使うことになるようなので練習しました。学んだことを記しておきます。 bit DP とは 例えば TSP (巡回セールスマン問題)で、拠点 ABCD を回ることを考える場合、既…

ARC015 [C]変わった単位

競技プログラミングに慣れていないので、幅優先探索や深さ優先探索を素早く記述することができないし、ダイクストラについては擬似アルゴリズムを見ないとかけないという状態なので練習します。 AtCoder Regular Contest 15 の C 問題「変わった単位」 一行…