問題ページ Aizu Online Judge Arena 解法 桁DPをする。dpテーブルを dp[i桁目][j,下3桁][k,N未満確定か][l,ごちうさ数か] とする。次の桁の数をnxtとしたとき下3桁は j%100*10 + nxt となる。N未満かは k || nxt < lim とする桁DPのよくあるやつで確認でき…

問題ページ Aizu Online Judge Arena 解法 a,b,c の3頂点で閉路となっていてこのような閉路がN個ある。閉路の3辺から1つの辺を選んで構成したグラフでのs-t間の最短経路を求めたい。 経路a->bよりも経路a->c、c->bとたどっていくような経路の方が短くなるこ…

問題ページ Aizu Online Judge Arena 解法 dp[i][j] = (i番目まででj個の区画を作った状態での水の高さの合計のmax) とする。 dp[i][j] -> dp[k][j+1] へ配るDPとして書くと、漸化式は dp[k][j+1] = max(dp[k][j+1], dp[i][j] + (区間(i,k]の平均)) となる。…

問題ページ Aizu Online Judge Arena 解法 sigmaさんのコードを参考にさせてもらった。 multi_setの同型判定をハッシュを用いて行う。a[i]に対応するハッシュ値を乱数で決める。multi_setのハッシュ値を (存在している値のハッシュ値) * (存在している数) の…

問題ページ Aizu Online Judge Arena 解法 写像fが全射であれば問題の条件を必ず満たす。 もし全射でなければf(x)として現れない数が必ず存在している。そのような数zについてg(z) != h(z)となるように構成すればよい。 ソースコード #include <bits/stdc++.h> using namesp</bits/stdc++.h>…

問題ページ Aizu Online Judge Arena 概要 N個の自然数a[i]が与えられる abs(a[i]-a[j]) = 0 (mod n-1) を満たすような組(i!=j)を一つ示せ 解法 N <= 1000 でO(N^2)が間に合うので全てのペアについて探索すればよい ソースコード #include <bits/stdc++.h> using namespace </bits/stdc++.h>…