AGC013 B問題 Hamiltonish Path

問題

agc013.contest.atcoder.jp

解説

まず適当に頂点uを選択します。頂点uから移動可能な頂点vを探して頂点vから今まで訪れた頂点でない頂点xを選択し頂点xから移動可能な今まで訪れた頂点でない頂点yを選択し、、、
このような操作を繰り返していくと移動できなくなる頂点にたどり着くことができ、その頂点は片方の端点になります。そして再び頂点uから移動可能な今まで訪れた頂点でない頂点zを選択し、、、のように繰り返すと、別の片方の端点にたどり着くことができます。したがって移動可能な頂点を探していく過程で頂点を順番通り保持していけば解を求めることができます。

コード

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
 
#define ALL(x) x.begin(), x.end()
using namespace std;
 
typedef vector<vector<int> > G;
const int inf = 1e9;
 
int n, m;
G graph;
vector<int> ans;
 
int visited[100100];
 
void dfs(int u){
 
    ans.push_back(u);
    visited[u] = 1;
 
    for(int i=0; i<graph[u].size(); i++){
        int v = graph[u][i];
        if( !( visited[v] ) ){
            return dfs(v);
        }
    }
    return;
}
 
int main(void){
    cin >> n >> m;
    graph = G(n+100);
    for(int i=0; i<m; i++){
 
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
 
    }
    
    dfs(1);
    reverse(ans.begin(), ans.end());
    ans.pop_back();
    dfs(1);
 
    cout << ans.size() << endl;
 
    for(int i=0; i<ans.size(); i++){
        cout << ans[i] << " ";
    }
 
    cout << endl;
    return 0;
}

ARC083 D問題 Restoring Road Network

問題

AtCoder Regular Contest 083 - AtCoder

解説

入力例のケースで考えてみます。

3
0 1 3
1 0 1
3 1 0

この場合三角形の頂点に３つの街があると仮定し、辺の付近に都市間の距離を書いた、図は

     3
  ①ーー③
1｜　 ／ 
  ②／ 1

となります。

しかし都市間の距離を長さだと考えると、このような三角形は作ることはできません。 それは 辺の長さをa, b, cとすると、a + b < c からです。 よってこのようなケースが存在すれば入力例のような道路の構造はありえないので出力は-1となります。

では道路の構造が存在する場合について考えてみます。与えられるのは全都市間を結んだケースです。 以下のケースで考えてみます。

3
0 1 3
1 0 2
3 2 0

図に表すと

     3
  ①ーー③
1｜　 ／ 
  ②／ 2

このようになります。
ここで総距離が最小で全ての都市が繋がっていればいいので都市1と3を結ぶ道路はいらないことがわかります。 つまり a + b = c　の場合の道路は入りません。
では a + b > cとなる道路はどうでしょうか？答えは必要です。 a + bでは他の都市を経由して行く場合の総距離が直接結んだ場合の距離より多くなってしまう場合には２都市間を結ぶ必要があります。

したがってまとめると
a + b < c となる場合が存在すれば -1
a + b = cとなる辺cは必要なし
a + b > cとなる辺cは必要あり

コード

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

int d[303][303];
bool d_n[303][303];

int main(void){
  int n;
  cin >> n;

  long long ans = 0;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      cin >> d[i][j];
    }
  }
  for(int k=0; k<n; k++){
    for(int i=0; i<n; i++){
      for(int j=0; j<n; j++){

        if(d[i][j] > d[i][k] + d[k][j]){
          cout << "-1" << endl;
          return 0;
        }

        if(d[i][j] == d[i][k] + d[k][j] && d[i][k] > 0 && d[k][j] > 0){
          d_n[i][j] = true;
        }

      }
    }
  }

  for(int i=0; i<n; i++){
    for(int j=0; j<=i; j++){

      if(d_n[i][j] == false){
        ans += d[i][j];
      }

    }
  }
  cout << ans << endl;
  return 0;
}

AGC002 C問題 Knot Puzzle

問題

agc002.contest.atcoder.jp

解説

この問題は結び目に注目して考察すれば解くことができます。 最後にほどくのは必ず左右のロープの長さの和がL以上の結び目でなければなりません。したがってそのような結び目が存在しなければほどくことはできません。 しかし、存在すれば必ずほどくことができます。それは長さL以上のロープが常に存在することになるからです。

ここで
(x,y)=(左端から結び目までの長さ, 右端から結び目までの長さ)
左右のロープの長さの和がL以上の結び目をM, 長さをLm
とします
その他の結び目に関して、Mの左側に存在すれば(x, y+Lm), 右側に存在すれば(x+Lm, y) となり、 全ての結び目に関して左右の総和がLを超えることになります。したがってMの結び目が存在するロープと切り離される結び目を作らないように解いていきます。 つまり、Mの左側に存在する結び目に関しては左から順番に、右側に存在する結び目に関しては右から順番に、最後にMを解けば全ての結び目をほどくことができます。

コード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int ,int> P;
int main(void){
    int n, l, ans = 0;
    int a[100005], length[100005];
    vector<int> front, back;

    cin >> n >> l;

    for(int i=0; i<n; i++){
        cin >> a[i];
    }

    for(int i=0; i<n-1; i++){
        length[i] = a[i] + a[i+1];
        if(length[i] >= l && ans == 0){
            ans = i+1;
        }else{
            if(ans == 0){
                front.push_back(i);
            }else{
                back.push_back(i);
            }
        }
    }

    reverse(back.begin(), back.end());

    for(int i=0; i<back.size(); i++){
        front.push_back(back[i]);
    }

    if(ans == 0){
        cout << "Impossible" << endl;
        return 0;
    }else{
        cout << "Possible" << endl;
    }

    for(int i=0; i<front.size(); i++){
        cout << front[i]+1 << endl;
    }
    
    cout << ans << endl;

    return 0;
}

AGC001 B問題 Mysterious Light

問題

agc001.contest.atcoder.jp

解説

解法の方針はユークリッドの互除法です。 なぜこの問題を見てユークリッドの互除法が思いつくのかをまず解説していきます。

ユークリッドの互除法を幾何的に説明したサイトがあったので紹介します。 math-arithmetic.blogspot.jp

x, yの最大公約数をユークリッドの互除法で求める操作を図で表すとすると「縦の長さx, 横の長さyの長方形をできる限り大きな正方形で埋めていき全て埋まった時の最小の一辺の正方形の長さが最大公約数」になります。

ではなぜこの考えが問題に関係あるのかを次に説明していきます。 まず最初の光の航路(反射するまで)と底辺が対辺になる平行四辺形に注目してください(下図)

さらに下図を見てみてください

この問題は光の航路と三角形の辺で構成される平行四辺形を全ての辺が同じ長さのできる限り大きな平行四辺形で埋めていっているだけなのです。 また細かく見ると正三角形で埋められています。 以上の点からユークリッドの互除法の発想が浮かんでくるかと思います。
次に実際にユークリッドの互除法を用いてこの問題を解いていきます。

下図の赤い線に注目してください。

図の中に光の航路で囲まれている大きい正三角形１つと小さい正三角形２つがあります。この赤い線の長さはそれぞれの三角形の一辺の長さの和になります。 では長さはいくつになるでしょうか。ここで用いるのが先ほどの最大公約数です。図の中で最大公約数は正方形で埋めた時の最小の正方形の長さです。(ここでは平行四辺形の長さ)
下図の緑線に注目してください。
緑の線と赤の線の和は (N-x) + x になります。それは横にxだけ縦にN-xだけ移動しているからです。 そして緑の線の長さは前述した通りgcd(N-x, x)になるので赤い線の長さは N-gcd(N-x, x) になります。 よってこれは一辺の長さの総和なので求めるのは3倍した3*(N-gcd(N-x, x))

※解説ではgcd(N,x)ですがgcd(N-x, x)でも大丈夫です。

コード

#include <iostream>
#define ll long long
using namespace std;

ll gcd(ll a, ll b){
    if(a%b == 0){
        return b;
    }
    return gcd(b, a%b);
}

int main(void){
    ll n, x;
    cin >> n >> x;
    ll gc = gcd(n-x, x);
    cout << 3*(n-gc) << endl;
    return 0;
}

AOJ Range Minimum Query (RMQ)

問題

Range Minimum Query (RMQ) | Aizu Online Judge

解説

一般的なRMQの問題です。 セグメント木で実装すれば構いません。

コード

#include <iostream>
#define ll long long
using namespace std;

const int INF = (1<<31)-1, MAX_N = 1<<17;

int N, dat[2*MAX_N -1];

void init( int n_ )
{
    N = 1;
    while( N < n_ )
        N <<= 1;
 
    for(int i=0; i < 2*N-1; i++)
        dat[i] = INF;
 
    return;
}
 

void update(int k, int a){
    k += N - 1;
    dat[k] = a;
    while(k > 0){
        k = ( k - 1 ) / 2;
        dat[k] = min(dat[ k * 2 + 1 ], dat[ k * 2 + 2 ]);
    }
    return;
}

int query(int a, int b, int k, int l, int r){
    if( r <= a || b <= l ){
        return INF;
    }
    if( a <= l && r <= b ){
        return dat[k];
    }else{
        int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
        int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return min(vl, vr);
    }
}

int main(void){
    int n, q;
    
    cin >> n >> q;
    init(n);
    
    for(int i=0; i<q; i++){
        ll com, x, y;
        cin >> com >> x >> y;
        
        if(com == 0){
            update(x, y);
        }else{
            cout << query(x, y+1, 0, 0, N) << endl;
        }
    }
    return 0;
}

ARC 074 D問題 3N Numbers

解説

この問題はどこで前半と後半の区切りになるのかを考えます。 例えば | が前後半の区切りだとすると

a, b, c d, e | f, g, h, i

この棒をずらしていくのですがn~2*nの間しか動くことができません。

• 先頭からN個数字をとる場合
  a, b, c, d, e, f | g, h, i

• 後ろからN個数字をとる場合
  a, b, c | d, e, f, g, h, i

このように極端な例を考えてみると | が動ける位置がわかるので その|の位置を一つづつずらして前半から大きい順にN個の和と後半から小さい順にN個の和を別々に計算し最後に最大になるa'の値を出力すれば正解です。

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;

int main(void){
    int n, a[300005];
    long long sum_front=0, sum_back=0;
    
    vector<ll> sf, sb;
    priority_queue<ll, vector<ll>, greater<ll> > que_front;
    priority_queue<ll> que_back;
    
    cin >> n;

    for( int i = 0; i< 3 * n; i++ ){
        cin >> a[i];
        if(i < n){
            sum_front += a[i];
            que_front.push(a[i]);
        }else if( 2*n <= i ){
            sum_back += a[i];
            que_back.push(a[i]);
        }
    }

    sf.push_back(sum_front);
    sb.push_back(sum_back);
    
    for( int i = 0; i < n ; i++ ){
        que_front.push(a[i+n]);
        sum_front += a[i+n];
        sum_front -= que_front.top();
        que_front.pop();
        sf.push_back(sum_front);

        que_back.push(a[2*n-1-i]);
        sum_back += a[2*n-1-i];
        sum_back -= que_back.top();
        que_back.pop();
        sb.push_back(sum_back);
    }
    reverse(sb.begin(), sb.end());
    long long ans = sf[0] - sb[0];
    for( int i = 1; i <= n; i++ ){
        ans = max(ans, sf[i] - sb[i]);
    }
    cout << ans << endl;
    return 0;
}

ARC 072 D問題 Alice&Brown

解説

まずこのようなゲーム系の問題は終了時から遡って考えていきます。 そこでゲームが終了する場面を考えてみると

(x, y) = (0, 0), (1, 0), (0, 1),(1, 1)

この4通りぐらいは自分で見つけることができるかと思います。
次にx, yが0~5の6x6の表を書いてみることにします。
そのマスには(x, y)の場面が回ってきた場合に負けならばL, 勝ちならばWとします。
するとあるマスからあるマスへはy=-2xかy=2x上のマスに遷移することはゲームのルールからわかります。 それでもし遷移できる箇所にLのマスがあれば勝つことができ、もしWしかならば負けということになります。(Wの先にはLがあるはずなので) したがってこの法則に従って表を埋めていくと

|x-y| <= 1 => Brown
|x-y| >= 2 => Alice

がわかるかと思います。

コード

#include <iostream>
using namespace std;

int main(void){
    long long x, y;
    cin >> x >> y;
    if(abs(x-y) <= 1){
        cout << "Brown" << endl;
    }else{
        cout << "Alice" << endl;
    }
    return 0;
}