Euldernaの競技プログラミングメモ

主に気になった問題やライブラリの確認に使った問題を示します。

ICPC2017 国内予選 G問題(Go around the Labyrinth/迷宮を一周) 解説

前書き

ICPC2017年の国内予選G問題のネタバレ記事です。

ちなみに実際に本番では通せてないですが、あと10分あれば間違いなく通せてたという感じの人が書いています。

問題概要

二次元の迷路が与えられて、同じマスを二度行かないという制約の下、迷路の左上から左下・右下・右上を巡って左上に戻れるかという問題。

講評

実際には右手法で貪欲的に迷路を解いていくやり方で解いたチームが多かったようです。(講評の後半部分)

ここでは講評の前半で紹介されている最大流を用いた解法を扱います。

解法

探索書くのダルいと思います。そうするとうまくフローに逃げれないかと思います。経路の存在性は最大流アルゴリズムが典型なので、そこから考えます。(経路の存在=最小カットが1以上みたいな考察から始まります)

そうすると始点から各点までいく最大流(最小カット)が2であることが、少なくとも必要条件なのが分かります。

ここから反例になるようなものを考えると、必ずループのどこかで共有点が存在するので不可能です。

これで各点までの最大流が2であることが必要十分なことが分かります。(これは少し嘘)

このことは右手法で解が得られる根拠になっています。

この発想でプログラムするとサンプルの2が合わなくて悲しい気持ちになります。

ここで各マスに流入するのは必ず1であることに気がつけば、ノードの持ち方を工夫すれば解けますね。(本当は考察の段階で気がつきましょう)

つまり一つのノードを次のように持てばよいですね。

f:id:Eulderna:20171229204739p:plain

時間計算量はO(盤面のサイズ)で十分高速です。

コード

半年前の緑時代&&ICPCルールでのタイムアタック時のコードなので汚いです。参考までに。

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cstring>
 
 
#define REP(i,n) for(int i=0;i<(n);i++)
#define pb push_back
 
using namespace std;
 
const int INF = 1000000000;
 
#define MAX_V 5010
struct Edge{int to,cap,rev;};
typedef vector<Edge> Edges;
Edges G[MAX_V];
bool used[MAX_V];//for DFS
 
void add_Edge(int from,int to,int cap){
  G[from].pb((Edge){to,cap,G[to].size()});
  G[to].pb((Edge){from,0,G[from].size()-1});
}
 
int dfs(int v,int t,int f){
  if(v == t) return f;
  used[v] = true;
  REP(i,G[v].size()){
    Edge &e = G[v][i];
    if(!used[e.to] && e.cap > 0){
      int d = dfs(e.to,t,min(f,e.cap));
      if(d > 0){
        e.cap -= d;
        G[e.to][e.rev].cap += d;
        return d;
      }
    }
  }
  return 0;
}
 
int Ford_Fulkerson(int s,int t){
  int flow = 0;
  while(1){
    memset(used,0,sizeof(used));
    int f = dfs(s,t,INF);
    if(f == 0) return flow; //max flow
    flow += f;
  }
}
int main(){
  int n,m;
  while(cin >> n >> m,n){
    REP(i,5010)
      G[i].clear();
    vector<string> s(n);
    REP(i,n){
      cin >> s[i];
    }
    REP(i,n){
      REP(j,m){
        add_Edge(i*m+j,i*m+j+2501,1);
        if(s[i][j] == '.'){
          if(s[i][j+1] == '.'&& j != m-1){
            add_Edge(i*m+j+2501,i*m+j+1,1);
            add_Edge(i*m+j+1+2501,i*m+j,1);
 
          }
          if(i != n-1){
            if(s[i+1][j] == '.'){
              add_Edge(i*m+j+2501,(i+1)*m+j,1);
              add_Edge((i+1)*m+j+2501,i*m+j,1);
 
            }
          }
        }
      }
    }
    Edges tG[5010];
    REP(i,5010)
      tG[i] = G[i];
     
    string ans = "NO";
    if(Ford_Fulkerson(2501,m-1) == 2){
      REP(i,5010)
        G[i] = tG[i];
      if(Ford_Fulkerson(2501,n*m-1) == 2){
        REP(i,5010)
          G[i] = tG[i];
        if(Ford_Fulkerson(2501,n*m-m) == 2)
          ans = "YES";
      }
    }
    cout << ans << endl;
  }
  return 0;
}

結論

フローは神。

TLにたまたまこの問題について流れてきたので書きました。

Maximumの人はwikiに上げてある部内向け解説の方が分かりやすいのでそっちを見て。

2017 ICPC国内予選 参加記(Team:Maximum-omake)

2017/11/18 あまりに雑な文章だったので全面的に書き直しました。というよりメンバーがtwitter始めてたのでそれに合わせて改訂

はじめに

埼玉大学とかいう大学で競技プログラミングをしている人です。

Maximum-omakeとして2017 ICPC国内予選参加して全体54位・学内1位で国内予選突破となりました。 国内予選通過組の中で最下位だったので選抜されてよかったと思います。

メンバー

僕はMaximumとかいう闇のサークルに所属しているので、自然とメンバーもそこから選出された。この時は僕がサークル内トップだったので好きな部員を2人選んでいい感じだった。

@qcw君は大学のプログラミングの授業が面白すぎて競技プログラミングを始めた異色の経歴を持つ。同学年ということもあり仲が良かったので彼はほぼ固定枠だった。

@qcw君がサークルの同級生たちとあまり馴染めていなさそうだったので、最後の一人は後輩の@seica君を選出した。

ICPC

僕とqcw君の実験レポートのせいでチーム練習は模擬国内予選のみ。その結果も3完とあまりいい雰囲気ではなかった。

これを受けて本番の方針としては4完早解きか、5完で行こうと話してた気がする。

そもそもうちは競プロ専門サークルなのに国内予選突破できるような人間がうちのチームにしか固まっていない。下の方でひっかかればいいだけなのでいけるやろとか考えていた。

ということで話し合ってD問題を全員で考えて瞬殺する方針にした。

ICPC

Aは印刷が終わるまでに僕がプログラム書いて提出。AC。

Bはチラ見したらただのパースぽかったので他の二人に任せてCを考えることに。今思うと何でBを二人がかりで解いてるんですかねぇ

Cのソースコードを紙に書き終わると、何やら二人ともB問題で苦戦していた。

『B解けないとかカスかwww』みたいな暴言を吐いて、B問題を通す。(後にこの発言を後悔する)

ただこの時に事件があってIDENTICALINDENTICALとして1WA食らった。これが響いたら確実に戦犯なので手が震えた。

Dを全員で考察する。あとから見直したら、G問題が最大流を写経したら、ただノードの持ち方を工夫するだけで解ける問題だったので、僕はGを解くべきだった。

D問題が全然わからなくて紙上でたくさん考察しても解法が浮かばない。

seica君が終了20分前くらいに正解にたどり着く。僕らの実装力じゃバグ埋め込んだら一瞬でアウトなので見送る。

今ある全探索コードから枝刈を進めていけば二分探索(two minutesの方)ができると考えて、強引に枝刈した二分探索(two minutesの方)で通した。

最終的に4完(20315)で54th.

ICPC

G問題を見て血涙を流す。 僕がG問題を一切見ていなかったのはやっぱりチーム戦略の失敗だなぁと思った。

ワンチャンあるのでは、と思っていたらOBから「君たちギリギリ通ってなくて受けるwww」みたいなメールを頂戴してほげえええっとなります。

何だかんだがあって†C選抜†で予選突破を果たします。

感想

G問題を見ずにいたのはよくなかった。A-Dを解くって決め打ちはよくないなと思った。(大学生並みの感想)

最下位での予選通過でした。精進します。

後日談

予選突破を果たしたこともあってチーム内やらサークル内でイキってたんですが、他のメンバーが†覚醒†を果たし、チーム内で最下位になりサークル内最強の座も奪われてしまいました。

『D解けないとかカスかwww』

今では僕がARCでこういう風に煽られています。

強くなった(ている)筆頭のqcw君とseica君は来年も国内予選突破を果たすでしょうが、僕にかなりのフラストレーションをためているはずなのでチームには入れてもらえそうにありません。

人間、謙虚に物事を運ばなければ必ず痛い目を見るという平成・埼玉の小話でした。