不定期解説記事企画 第6回JOI-C #雫ぷよ

GWなので今日も記事を書いていきたいと思います。 今日は第６回日本情報オリンピック 本選 C 最古の遺跡です。

問題のリンクを下に貼っておきます。

atcoder.jp

自力で解けたと言えば解けた感じがします。

問題概要

問題概要については、公式解説PDFがわかりやすいので引用します。

要するに, 平面上に n 個の点 p1, . . . , pn が与えられるので, 与えられた点でできる正方形のうち面積が最大のものを探せ, という問題である. はい。

解答までの道のり

正方形の頂点に反時計回りに頂点1,2,3,4と名前をつけます。 すると、頂点1と頂点2をきめたら、頂点3と4の場所は一意に定まります。 頂点1,2の座標をとすると 頂点3,4の座標はそれぞれ

となります。

なので頂点1と頂点2を決めて頂点3と頂点4の場所に柱があるかを確認し、あったら答えの面積を更新していけばよさそうです。

そんな感じで実装したものがこちらです。

program am
    implicit none
    integer::N
    integer,allocatable,dimension(:)::x,y
    logical::Pillar(0:5000,0:5000)=.false.
    integer::ans=0

    integer::i,j
    read*,N
    allocate(x(N),y(N))
    do i=1,N
        read*,x(i),y(i)
        Pillar(x(i),y(i))=.true.
    end do
    do i=1,N-1
        do j=i+1,N
            if(POINT3(i,j).and.POINT4(i,j))ans=max(ans,(x(i)-x(j))**2+(y(i)-y(j))**2)
        end do
    end do
    print"(I0)",ans
contains
logical function In_area(a,b)
    integer::a,b
    In_area= a>=0 .and. a<=5000 .and. b>=0 .and. b<=5000
end function

logical function POINT3(k,l)
    integer::k,l
    POINT3=.false.
    if(In_area(x(l)+y(k)-y(l),y(l)+x(l)-x(k)))POINT3=Pillar(x(l)+y(k)-y(l),y(l)+x(l)-x(k))
end function
logical function POINT4(k,l)
    integer::k,l
    POINT4=.false.
    if(In_area(x(k)+y(k)-y(l),y(k)+x(l)-x(k)))POINT4=Pillar(x(k)+y(k)-y(l),y(k)+x(l)-x(k))
end function
end program am

柱のある場所はと決まっているので、この中の点全てについてそこに柱があるかないか、という情報を持たせました。

これでうまくいったと思ったのですが、提出してみるとMLEがでてきてしまいました(Fig.1)。

Fig.1まばらに出るMLE

おそらく全ての点について情報を持つのはよくばりすぎていたのでしょう。そこで柱がある点についてのみ記録することにしました。

PythonやC++のような今めかしい言語のようにFortranにはmapやdictがありませんがue1221さんがtree map をさくせいしていらっしゃったのでそれを使うことにしました。

qiita.com

これはinteger をkeyにしているので、点の座標をintegerに変換する関数も作りました。

integer function Pillar_ID(a,b)
    integer::a,b
    Pillar_ID=5001*(a-1)+b
end function

これで実装した結果がこちらです。(ue1221さんの作成したmodule部分は抜いてあります)

program am
    use mod_tree_map
    implicit none
    integer::N
    integer::x(3000),y(3000)
    type(t_tree_map)::Pillar
    integer::ans=0

    integer::i,j

    read*,N
    do i=1,N
        read*,x(i),y(i)
        x(i)=x(i)+1
        y(i)=y(i)+1
        call put(Pillar,Pillar_ID(x(i),y(i)),1) 
    end do
    do i=1,N-1
        do j=i+1,N
            if(POINT3(i,j).and.POINT4(i,j))ans=max(ans,(x(i)-x(j))**2+(y(i)-y(j))**2)
        end do
    end do
    print"(I0)",ans
contains
logical function In_area(a,b)
    integer::a,b
    In_area= a>0 .and. a<=5001 .and. b>0 .and. b<=5001
end function

integer function Pillar_ID(a,b)
    integer::a,b
    Pillar_ID=5001*(a-1)+b
end function

logical function POINT3(k,l)
    integer::k,l
    POINT3=.false.
    if(In_area(x(l)+y(k)-y(l),y(l)+x(l)-x(k)))POINT3=get(Pillar,Pillar_ID(x(l)+y(k)-y(l),y(l)+x(l)-x(k)))==1
end function
logical function POINT4(k,l)
    integer::k,l
    POINT4=.false.
    if(In_area(x(k)+y(k)-y(l),y(k)+x(l)-x(k)))POINT4=get(Pillar,Pillar_ID(x(k)+y(k)-y(l),y(k)+x(l)-x(k)))==1
end function
end program am

これで流石にうまくいくだろうと思ったのですがまたMLEが出てきてしまいました(Fig.2)。

Fig.2 MLE．先程のものよりはMLEの数が減っている

そこで原因究明のために

            if(POINT3(i,j).and.POINT4(i,j))ans=max(ans,(x(i)-x(j))**2+(y(i)-y(j))**2)

という部分を抜かして提出しました。 その結果メモリがオーバーしなかったのでgetの回数が多いとメモリを食ってしまう、と判断しました。

どうしたらgetの数を減らせるかを考えた結果、もし正方形ができていてもそれが今までみつけた一番大きい正方形より小さかったら答えの更新が行われないことに至りました。そこで、点二つを選んだ際にその点二つを一辺としてもつ正方形が今わかってる正方形より小さい時は正方形ができるか調べない、ということにしました。

    do i=1,N-1
        do j=i+1,N
            if(ans>=(x(i)-x(j))**2+(y(i)-y(j))**2)cycle
            if(POINT3(i,j).and.POINT4(i,j))ans=(x(i)-x(j))**2+(y(i)-y(j))**2
        end do
    end do

そうしてできたコードがこちらです。(ue1221さんの作成したmodule部分は削っています)

program am
    use mod_tree_map
    implicit none
    integer::N
    integer::x(3000),y(3000)
    type(t_tree_map)::Pillar
    integer::ans=0
 
    integer::i,j
 
    read*,N
    do i=1,N
        read*,x(i),y(i)
        x(i)=x(i)+1
        y(i)=y(i)+1
        call put(Pillar,Pillar_ID(x(i),y(i)),1) 
    end do
    do i=1,N-1
        do j=i+1,N
            if(ans>=(x(i)-x(j))**2+(y(i)-y(j))**2)cycle
            if(POINT3(i,j).and.POINT4(i,j))ans=(x(i)-x(j))**2+(y(i)-y(j))**2
        end do
    end do
    print"(I0)",ans
contains
logical function In_area(a,b)
    integer::a,b
    In_area= a>0 .and. a<=5001 .and. b>0 .and. b<=5001
end function
 
integer function Pillar_ID(a,b)
    integer::a,b
    Pillar_ID=5001*(a-1)+b
end function
 
logical function POINT3(k,l)
    integer::k,l
    POINT3=.false.
    if(In_area(x(l)+y(k)-y(l),y(l)+x(l)-x(k)))POINT3=get(Pillar,Pillar_ID(x(l)+y(k)-y(l),y(l)+x(l)-x(k)))==1
end function
logical function POINT4(k,l)
    integer::k,l
    POINT4=.false.
    if(In_area(x(k)+y(k)-y(l),y(k)+x(l)-x(k)))POINT4=get(Pillar,Pillar_ID(x(k)+y(k)-y(l),y(k)+x(l)-x(k)))==1
end function
end program am

このコードはMLEにならずに正解することができました。 おしまい。