JOI2011 春合宿4-4 Orienteering

表題の問題を解きました。

問題はこちらから。

＜さらっと概要＞

有向グラフがあり、そこを2人で1からNまで行く。

途中に少なくともどちらか一方が通らなければ行けない場所があり、それらを全て通ったときの2人の移動経路の合計の最短は？

・まず、ここの文に注目します。

JOI 高校は，混乱を避けるため，オリエンテーリングの間，それぞれの道を，高度が低い方の地点から 高度が高い方の地点への一方通行とする．高度が等しい 2 つの地点は存在しない．スタートである地点 1 は最も高度の低い地点であり，ゴールである地点 N は最も高度の高い地点であるが，地点の番号は必ずしも高度の低い地点から順につけられているわけではないことに注意せよ．

ここから、高度が低い方から見ていけば答えに近づきそう。

「番号は高度が低い方から振られているとは限らない」→もう一度高度が低い方からつけ直せば良いです。

これをするためのアルゴリズムがトポロジカルソートです。閉路のない有向グラフに適用することができます。

トポロジカルソートされたあとの順序はトポロジカル順序と呼ばれ、トポロジカル順序がそれ以下の頂点には移動できなくなります。つまり、iからjへ移動できるできることはi<jであることの同値十分条件となります。

トポロジカルソートとDPは非常に相性が良いです。なぜなら、トポロジカル順序に沿ってたどっていけばその地点における更新に必要な情報をすでに計算してあるからです。

今回も最小値を求める訳なのでDPをすることを思いつきます。ここで、DPの更新に必要な要素は2人のそれまでの移動距離とそのとき相方がどこにいるか、です。

二人の人をA,Bとします。ただし、区別をつけるため最初のチェックポイントにいった方をAとします。

dp[i][j][k]:k(0:A、1:B)がトポロジカル順序でのi番目の頂点にいて、相方がj(最初に与えられたインデックスのままでいいです)にいるときの2人の移動距離の最小値

と言う風になります。

N<=1000と制約が緩いので更新にある程度の時間を割くことができます。ここでは、i番目のチェックポイントにAがいく時の更新を考えます。Bのときも同じようにできます。

i→jの最小コストをf(i,j)とします。

・i-1番目もAが訪問しているときからの更新

Bは動かないので、Bが最後に訪れた場所は変わりません。

iはトポロジカル順序でi番目という意味なので、それに当たる頂点の番号をpとします。(これ以降この前提で話をします。)また、トポロジカル順序でi-1番目に当たる頂点をtとします。

よって、jが1からnまでの場合を考えて、dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][0]+f(t,p))とすればいいです。

・i-1番目をBが訪問しているときからの更新

この場合は、Aが最後に訪れた場所の候補が1～nまで考えられます。また、相方が最後に訪問した場所はトポロジカル順序でi-1番目の場所(=t)です。

すると、jが1からnまでの場合を考えて、dp[i][t][0]=min(dp[i][t][0],dp[i-1][j][1]+f(j,p))となります。

これで全体でO(N^2)で解けるようになりました。と言いたいところですがf(i,j)の更新を考えていませんでしたね。

グラフ上の最短経路なのでdijkstra法でpから各頂点までの最短経路をO(NlogM)で求めることができるので全体の計算量はO(N^2 log M)です。N<=1000,M<=10000なのでこれで問題ありません。

ただし、グラフにそのままdijkstra法を適用してしまうと、pよりトポロジカル順序が後の頂点までの最短経路までしか出せません。(トポロジカル順序の定義より、トポロジカル順序が前の頂点へ移動する辺がないので)

実際には更新に使う頂点はトポロジカル順序が前のものだけなので、逆辺でdijkstra法を適用するとうまくいきます。

自分の提出を貼っておきます。汚いコードですが良かったらどうぞ。

atcoder.jp

ありがとうございました。

JOI2011本選5 微生物実験

冬休みももう終わりですね。

ここを放置気味でしたが、こういう場所を作ったからにはちゃんと何か書いていこうと思ったので。

表題の問題を解きました。3日くらいかけてやっと解きました。

＜問題概要＞

n個の微生物がいる。それぞれが変な物質を出している。

各個体の物質の放出量と許容量が与えられる。

複数の微生物を同じ箱に閉じ込めたとき、1体の微生物が摂取する物質は全体の放出量の平均値

最も条件良く微生物たちを選んだとき、最大何匹を同じ箱に入れられるか？

 ＜解法＞

・とりあえず平均値を固定して、許容量がそれ以上の物の中で小さい物からGreedyすることを考えた

・座圧を使って各個体毎の許容量の値のみで考えるとO(N^2)程度-＞部分点30点を得られる。

・上の考えにおいて、ある平均値についてO(N)で判定を行うのは少し計算量的にキツいかも･･･

・各個体の放出量の合計値が、(考えている許容量×個体数)より大きくなるようにしたから定めていく-＞累積和が使えそう

・累積和をO(log N)くらいで計算するには-＞BIT(Binary Indexed Tree)

・ただし、小さい方から取りたいので昇順ソート

・問題文のサンプルデータでやるとこういう木になる([7],[8]は不要)

・許容量を段階的に考えていくとき、許容量がそれ以下の微生物の値については0に変えていく

・あとはここで二分探索をする

・50点を取る方法

O(N log^2 N)で50点が返ってくる。この問題の部分点としては設定されていないが、個人的にはこれを小課題2にしてもいいのでは？と思った。

・例えば、許容量4の時を考える(赤字はその区間に含まれる個数)

N(この場合は6)までで二分探索すると、

・3->1～3の累積和:13、1～3の個数:3->4*3=合計12まで放出してok->NG

・1->1～1の累積和:2、1～1の個数:1->4*1=4まで放出してok->OK

・2->1～2の累積和:7、1～2の個数:2->4*2=8まで放出してok->OK

という風な感じで、2体までならokになる。

許容量7の時も考えてみる。

今度は、一番左の微生物の許容量が4のため、これを虚無に置き換える。

個数に注意しながら探索すると

・3->1～3の累積和:11、1～3の個数:2->7*2=合計14まで放出してok->OK

・4->1～4の累積和:21、1～4の個数:3->7*3=21まで放出してok->OK

・5->1～5の累積和:33、1～5の個数:4->7*4=28まで放出してok->NG

という風にして4に定まりますが、1～4に実際にいる微生物はこの段階では3体なので、3を更新値にします。

・毎回BITのsumクエリを呼び出していると、許容量を試すのにO(N)、二分探索にO(log N)、BITのクエリの呼び出しにO(log N)かかるため、合計でO(N log^2 N)になります。

・BITは木構造の一種なので、実はO(log^2 N)をO(log N)にまとめることができます。

・BIT上二分探索という手法。

再登場。

今まで意味を持たなかった[8]がここで意味を持つようになります。

・まず全体をカバーしている[8]を見る。5体いるので7*5=合計35まで放出可能だが、35<46より答えは左側

・つぎに[4]を見る。3体いるので7*3＝21。放出量も21なので右側に行ける。

・[6]のノードへ移る。現在、これより左では放出21・許容21より、限界まで受け止めていることになる。よって、余裕は0。

2体なので7*2=14、これより左の余力が0なので受容可能なのは14だが、25出してくるのでできない

という風に、見ているノードの幅がだんだん1/2になっているのがわかると思います。

二分探索は「次に左と右のどちらのノードに行くか」といったところでしょうか。

この解法は、一つの区間に対する和の取得がO(1)でできるので、全体でO(N log N)です。

自分の提出を貼っておきます。

atcoder.jp

JOI2018-2019予選 解法メモ・参加記

A-ソーシャルゲーム(Social Game)
・問題概要

JOI君はソシャゲを始める。
ログインボーナスがA(1<=A<=1000)コイン、7日連続でログインするとB(1<=B<=1000)コインもらえる。
C(1<=C<=10^6)枚のコインが欲しいとき何日ログインすべきか

・解法
　・累計のコインがC以上になるまで愚直に探索

・実装
　こんな感じ

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
using namespace std;
typedef long long Int;

int main(){
  int a,b,c;
  cin>>a>>b>>c;
  int cnt=0;
  while(c>0){
    c-=a;
    cnt++;
    if(cnt%7==0) c-=b;
  }
  cout<<cnt<<endl;
}

B-すごろくと駒(Sugoroku and Pieces)
・問題概要

　・すごろくがありスタートとゴールの間に1～2019の番号が振られている
　・1個先に駒がいないorゴールに着かないなら毎回指定された駒を1個右へ

・解法
　・実際にそれをプログラム上でやってみる
　・i番目の駒がどこにあるかの配列と、マスiに駒がいるかどうかのbool型配列を用意して実装

・実装
　こんな感じ

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
using namespace std;
typedef long long Int;
bool used[2020]={0};
int pos[2020]={0};
int main(){
  int n;
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>pos[i];
    used[pos[i]]=1;
  }
  int m;
  cin>>m;
  for(int i=0;i<m;i++){
    int a;
    cin>>a;
    if(used[pos[a]+1]==0&&pos[a]+1!=2020){
      used[pos[a]]=0;
      used[pos[a]+1]=1;
      pos[a]+=1;
    }
  }
  for(int i=1;i<=n;i++) cout<<pos[i]<<endl;
}

C-マルバツスタンプ
・問題概要

　・JOI君は○スタンプ、×スタンプ、○×スタンプをいくつか持っている
　・○×スタンプは○×と×○のどっちの押し方もできる
　・JOI君がスタンプを押した残骸をもらうので、JOI君が持っている○×の個数の最大は？

・解法
　・要素数分、はじめから見ていく
　・i番目!=i+1番目ならそこは○×を使って押せます
　・この場合i+1番目は見なくて良いのでi+2番目の探索に移ります

・実装
こんな感じ

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
using namespace std;
typedef long long Int;
bool used[2020]={0};
int pos[2020]={0};
int main(){
  int n;
  string s;
  cin>>n;
  cin>>s;
  int ans=0;
  for(int i=0;i<n-1;i++){
    if((s[i]=='O'&&s[i+1]=='X')||(s[i]=='X'&&s[i+1]=='O')){
      ans++;
      i++;
    }
  }
  cout<<ans<<endl;
}

ここまで10分で埋めました。例年の過去問だと20分くらい書けてるので速いほうですね、嬉しい

D-日本沈没(Japan Sinks)
・問題概要

　・日本をn個の区画に分ける。それぞれに高さA[i]がある。
　・海面上昇で相対的に日本が沈む。ばいばい。
　・だんだん高さが低い部分から海底になっていくが、そのとき連続していない一続きの陸地がc個あるとき島の数をcとする
　・日本が完全消滅するまでに島が一番たくさんできるのはいつ？

・解法
　・何も考えずに部分点1を見る。愚直にシュミレーションして間に合う。
　　・具体的には、日本の最高点に波が来るまで波の高さを1ｍずつ試す。
　　・毎回全体を見渡して島の数を数えていけばO(NAmax)<=4000000回の計算なので間に合う
　・部分点2は高さの制約がないも同然
　　・そこで座標圧縮という技を使う
　　・具体例をみた方がわかりやすいかも

　

　　・写真の場合、波の高さが2だろうが57だろうが99だろうが、区画1と3は浮いてて区画2は沈んでる
　　・→0、1、100、5000兆だけ見ればいい　こうすれば5000兆回試さなくて済む
　　・全部の高さをvectorに入れてソートする、またはpriority_queueを使うなどしてこれを実装すれば7+8＝15点

　・5，6の全探索を埋めて、満点解法が生えた

　　・この場合、5が沈むので島の数は増える
　　・しかし実際は1～3や7は5が沈んでも関係ない→その隣の状態だけを考えればいい
　　・海底:0,大陸の左端:1,大陸の右端:2,孤島:3,大陸内部:4とし、その状態がどのように変化するかを考えればO(N^2)くらいでできた
　　・これをACするのに2時間かけたが、これをACできたのは大きい

・実装
　満点解法だけ載せます。割とごちゃごちゃしているのでわかりにくいかも

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
using namespace std;
typedef unsigned long long Int;
typedef pair<Int,Int> P;
Int a[100005]={0};
vector<Int> v;
vector<P> island;

int main(){
  Int n,maxa=0,zcnt=0;
  cin>>n;
  for(Int i=0;i<n;i++){
    cin>>a[i];
    maxa=max(maxa,a[i]);
    if(a[i]==0) zcnt++;
    v.push_back(a[i]);
    island.push_back(P(a[i],i));
  }
  v.push_back(0);
  sort(v.begin(),v.end());
  sort(island.begin(),island.end());
  Int p=zcnt;
  Int ans=0;
  int info[200005]={0};
  Int is=0;
  for(Int j=0;j<n;j++){
    if(a[j]<=0&&is>0){
      ans++;
      is=0;
      if(j>=1){
        if(info[j-1]==1) info[j-1]=3;
        else info[j-1]=2;
      }
    }
    else {
      if(is==0&&a[j]<=0) info[j]=0;
      else if(is==0) info[j]=1;
      else info[j]=4;
      is=a[j];
    }
  }
  if(a[n-1]<=0) info[n-1]=0;
  else if(a[n-2]<0&&a[n-1]>0) info[n-1]=3;
  else info[n-1]=2;
  if(is>0) ans++;

  Int ans2=ans;
  for(Int i=0;i<v.size();i++){
    Int np=0;
    np=(lower_bound(island.begin(),island.end(),P(v[i]+(Int)1,(Int)0))-island.begin());
    for(int j=p;j<np;j++){
      Int pos=island[j].second;
      if(info[pos]==4){
        ans++;
        if(info[pos-1]==1) info[pos-1]=3;
        else info[pos-1]=2;
        if(info[pos+1]==2) info[pos+1]=3;
        else info[pos+1]=1;
      }
      else if(info[pos]==2){
        if(info[pos-1]==1) info[pos-1]=3;
        else info[pos-1]=2;
      }
      else if(info[pos]==3){
        ans--;
        info[pos]=0;
      }
      else if(info[pos]==1){
        if(info[pos+1]==2) info[pos+1]=3;
        else info[pos+1]=1;
      }
      info[pos]=0;
    }
    if(ans2<ans) ans2=ans;
    p=np;
  }
  cout<<ans2<<endl;
}

E-イルミネーション(Illumination)
・問題概要

　・JOI氏は木をN本はやしている。電飾してEn-JOI-ableな冬を過ごしたい。
　・まぶしすぎるのは嫌なのでm個の区間[l,r]では1本の木にしか電飾しない
　・木ごとに美しさがあるのでそれを最大化したい

・解説(になっていない)
　・結論から言うと部分点1しかとれませんでした
　・全探索をします
　・具体的には･･･すべての場所で電飾のあるなしを試します。計算量はO(2^N)
　・10分でこれを書いた以外何も分かりませんでした。終わった後にDPするらしいと言われ納得したけど実装ができない

・実装
　bit全探索の書き方が知りたい人向けに一応･･･
　ちなみにi>>jはiのビットをjだけシフトさせたと言うことです。例えば57>>2は57＝111001(2)より、2つ右にずらすと001110になります。

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
using namespace std;
typedef long long Int;
typedef pair<Int,Int> P;
Int a[200005]={0};
vector<P> v;
int main(){
  Int n,m;
  cin>>n>>m;
  for(int i=1;i<=n;i++) cin>>a[i];
  for(int i=0;i<m;i++){
    Int l,r;
    cin>>l>>r;
    v.push_back(P(l,r));
  }
  Int ans=0;
  for(Int i=1;i<(1<<(n+1));i++){
    bool f2=true;
    for(Int j=0;j<m;j++){
      Int l=v[j].first,r=v[j].second;
      bool f=false;
      for(int k=l;k<=r;k++){
        if(((i>>k)&1)==1){
          if(!f) f=true;
          else{
            f2=false;
            break;
          }
        }
      }
    }
    Int kans=0;
    if(f2){
      for(int j=1;j<=n;j++) if(((i>>j)&1)==1) kans+=a[j];
      ans=max(kans,ans);
    }
  }
  cout<<ans<<endl;
}

F-座席(Seats)
・問題概要
　>>
・国がN個あり、i番目とi+1番目は隣国
　・IOIに各国からAi人が出る
　・1列に並べるが、不正対策のため隣国や同国の選手を隣にしないように並べたい
　・パターン数のmod10007を求めよ