問題概要

$1\leq A _ 1 \leq A _ 2 \leq \cdots \leq A _ N \leq M$ という長さ $N$ の数列がとりうる最大の得点を求める
$A _ {b(i)} - A _ {a(i)}=c(i)$ だと得点 $d(i)$ が入る

解説

長さ $N$ が $N \leq 10$ 、さらに $M\leq 10$ なので数列の数は $10 ^ {10}$ よりも少なく、広義単調増加だということを考えればこれよりもっと少ないとわかるので全探索してよいです。

全探索するので数列があったら得点を計算してくれる関数を作っておきます。

integer function calc()
   integer::i
   calc=0
   do i=1,Q
      if(X(b(i))-X(a(i))==c(i))calc=calc+d(i)
   end do
end function

わかりづらいかもしれませんが $X$ が数列です*1。

さて準備が整ったところで数列を一つ一つ作っていきます。どのようにすれば数列を全部作って計算できるんでしょうか。これには深さ優先探索が良いそうです(思いつかなかった)。

これはなんででしょうね。1,1,1,1,1,1,1,1,1,1のような数列を計算したあとに、1,2,3,4,5,6,7,8,9,10のような突拍子もない数列よりも1,1,1,1,1,1,1,1,1,2という数列を作って計算したい。というのはなんとなく感じるので、もっとはっきり1,1,1,1,1,1,1,1,1までいったら最後の数字全種類の数列をコンプリートしてから次にいきたい、と気持ちを分析してみると、前の数字から決めて行って数列ができたら計算すればいいんだ、なーみたいな気持ちになるんでしょうか（ふわふわ）

こんな深さ優先探索がかけました。Kは数列の何番目を決めるかを表しています。KがN+1になったら数列作成が終わったということなので、得点を計算させています。

recursive subroutine DFS(K)
   integer::K
   integer::i
   if(K==N+1)then
      ans=max(ans,calc())
      return
   endif
   do i=X(K-1),M
      X(K)=i
      call DFS(K+1)
   end do
end subroutine

そうしてコードがかけました。

program cm
   implicit none
   integer::N,M,Q
   integer,allocatable,dimension(:)::a,b,c,d
   integer,allocatable,dimension(:)::X
   integer::i
   integer::ans=0
   read*,N,M,Q
   allocate(a(Q),b(Q),c(Q),d(Q))
   do i=1,Q
      read*,a(i),b(i),c(i),d(i)
   end do
   allocate(X(0:N))
   X(0)=1
   call DFS(1)
   print"(I0)",ans
contains
recursive subroutine DFS(K)
   integer::K
   integer::i
   if(K==N+1)then
      ans=max(ans,calc())
      return
   endif
   do i=X(K-1),M
      X(K)=i
      call DFS(K+1)
   end do
end subroutine
integer function calc()
   integer::i
   calc=0
   do i=1,Q
      if(X(B(i))-X(A(i))==c(i))calc=calc+d(i)
   end do
end function
end program cm

X(0)=1としているのはX(1)の範囲を1からMにするためです。

おしまい

補足

実はX(1)は1に固定してもよくて、そうすると計算量が減って5ms速くなります。

*1:fortanはAとaを同時に使えないので仕方ない

しずくぶろぐ

競技ぷろぐらみんぐしたり、なんかしたりします

不定期解説記事企画 ABC165C #雫ぷよ

問題概要

解説

補足