ABC061 D Score Attack と ベルマンフォード法

久しぶりの投稿です。。 だいぶC問題の正答率が安定した(新ABCになってCの難易度が下がった気もしない。。)ので、D問題の使用しているアルゴリズムと考え方をまとめていこうかなと思います。

ABC061

Score Attack

問題は以下から

atcoder.jp

枝に重みのついたグラフが与えられて1 ~ N までの頂点に行く際の最大スコアを算出するという問題ですね。

この時 1 ~ N までの経路は非連結でないことは保証されているようです。

最初考えたこと

DFSで閉路を探索
閉路の場合 -> inf
閉路でない場合 -> DFSの経路を全探索して最大を見つける

残念なことにこれではできなかったです。。

  • 与えられる重みは 整数なので負の閉路を見つけた場合にinfにはならない
  • DFS での全探索は頂点の累乗で計算量が増えるので、間に合わない

となったので、解説に頼りました。

読んでみると、ベルマンフォード法を使えばいいようですね。

ダイクストラ法やワーシャル・フロイド法などと同じで聞いたことあるけど実装したことないやつだったのでいい経験になりそうです。

ベルマンフォードの適用問題がわからないので、調べました。

最短経路問題を解くためのアルゴリズムの1種で問題の条件によってはダイクストラなどの方法が早い場合があるそうです。

ベルマンフォード法の特徴は以下のようです。

  • 最短経路問題を解くためのアルゴリズム
  • 負数を含む場合も問題を解くことができる(ダイクストラは解けない)
  • 負経路を含む場合(閉路が存在するときにその閉路の枝の重みの総和が 負数になる)正しい計算はできないが、検出は可能

今回の問題にぴったりな感じがしますね。

アルゴリズムのコアな部分

  • 最短経路の保管するデータ構造を初期化
  • 各頂点に対して以下の処理を繰り返す
    • 全ての枝に対して以下の処理を繰り返す
      • 枝がない場合、スキップ
      • 移動後のコストよりも低くなる場合は更新 その時の 枝を 負数の枝にする。
      • 枝の元が訪問済みならば 枝の先も負数の枝にする

今回の問題のコツ

  • 重みを反転をすれば負経路が正経路と考えることができるので、それでinfの検出を行えば良さげな気がします。
  • 重みの計算の値を頂点ごとに保管するデータ構造を作りそこの値を再利用する。
  • 判定した重みを答えで反転すれば正しい答えを求めることができる。

プログラムのフローは以下のような感じです。

  • 値の受け取り 重みは 正負反転
  • ベルマンフォード法を使って最短経路の算出
  • 負経路(正経路)の検出
  • 負経路がある場合
    • inf
  • そうでない場合
    • 最短経路

プログラム

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <tuple>
#include <math.h>
#include <deque>
#include <stack>
 
using namespace std;
 
typedef long long ll;
 
 
int solve() {
  ll n, m;
  const ll INF = 1145141919810;
  cin >> n >> m;
  vector<ll> a(m),b(m),c(m);
  for(ll i = 0;i < m;i++){
    cin >> a[i] >> b[i] >> c[i];
    c[i] = -c[i];
  }
  vector<ll> dist(n,INF);
  dist[0] = 0;
  // Bellman–Ford
  for(ll i = 0;i < n - 1; i++){
    for(ll j = 0;j < m;j++){
      // 最短経路値の計算
      if(dist[a[j] - 1] == INF){
        continue;
      }
      if(dist[b[j] - 1] > dist[a[j] - 1] + c[j]){
        dist[b[j] - 1] = dist[a[j] - 1] + c[j];
      }
    }
  }
  ll ans = dist[n - 1];
  vector<bool> negative(n, false);
  // 閉路の検索
  for(ll i = 0;i < n; i++) {
    for(ll j = 0;j < m; j++){
      if(dist[a[j] - 1] == INF){
        continue;
      }
 
      if(dist[b[j] - 1] > dist[a[j] - 1] + c[j]){
        negative[b[j] - 1] = true;
      }
 
      if(negative[a[j] - 1] == true){
        negative[b[j] - 1] = true;
      }
    }
  }
  if(negative[n - 1]){
    cout << "inf" << endl;
  }else{
    cout << -ans << endl;
  }
  return 0;
}
 
int main(void){
  solve();
  return 0;
}

まだ理解が曖昧な部分がある場合があるので、指摘していただけるとありがたいです。。

ABC071-C Together を解いてみた

今回のC問題はデータ構造を作ることができれば一瞬で解ける問題でした。

以下問題

問題

Together

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

長さ N の整数列 a1,a2,...,aN が与えられます。

各 1≤i≤Nに対し、ai に 1 足すか、1引くか、なにもしないかの三つの操作からどれか一つを選んで行います。

この操作の後、ある整数 Xを選んで、ai=X となる i の個数を数えます。

うまく操作を行い、Xを選ぶことで、この個数を最大化してください。

考えたこと

一つ一つ足して引いてのシミュレーションを行っていると O(N3) になってくるのでTLEになってしまいます。

視点を変えるとO(N)で問題が解けるようになります。

該当要素の+1 - 1を + 1 して配列としてデータをもって置けばO(N)で計算が終了します。

この時配列に作るデータの注意点は +1 -1 が配列の要素外にならないようにする点です。

フロー

  • 入力の受け取り
  • 数列を受け取りながら以下の処理を行う
    • 数列の要素の値を受け取る
    • 要素 - 1 と 要素 + 1の変数を作る
    • -1 要素が0以上 かつ +1 要素が 109 以内ならば以下の処理
      • 3つの要素の該当部分を+1
    • -1要素が範囲外の場合
      • 該当要素と+1要素を+1
    • +1要素が範囲外の場合
      • 該当要素と-1要素を+1
    • 作った配列を線形的に探索
      • そのなかでの最大値をとる
  • 最大値を出力

プログラム

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

int main(void){
  long long N;
  long long MAX = 100000;
  vector<long long> a(MAX);

  for(long long i = 0; i < MAX; i++){
    a[i] = 0;
  }
  
  cin >> N;

  for(long long i = 0;i < N; i++){
    long long tmp,dec,inc;
    cin >>  tmp;
    dec = tmp - 1;
    inc = tmp + 1;
    if(dec >= 0 && inc < MAX){
      a[dec]++;
      a[tmp]++;
      a[inc]++;
    }else if(dec < 0){
      a[tmp]++;
      a[inc]++;
    }else if(inc >= MAX){
      a[tmp]++;
      a[dec]++;
    }
  }
  long long mx = 0;
  for(long long i = 0; i < MAX; i++){
    mx = max(mx,a[i]);
  }
  cout << mx << endl;
  return 0;
}

こんな感じでACをとれることができました。

ABC071-C Make a Rectangle を解いてみた

今回の問題初歩的な部分や制約あたりで躓いてREを出して迷走していましたが、アルゴリズムを見直せば問題なく解くことができました。

では、以下問題

問題

C - Make a Rectangle

問題文

太さが無視できる棒が N 本あります. i 番目の棒の長さは Ai です.

すぬけ君は,これらの棒から 4本の異なる棒を選び,それらの棒を辺として長方形(正方形を含む)を作りたいです. 作ることができる最大の長方形の面積を求めてください.

制約

* 4≤N≤105
* 1≤Ai≤109
* Ai は整数

とこんな感じ、

考えたこと

最初考えたのはハッシュ的にデータを保持できれば解けるかなと思いましたが、ハッシュを使う場合に 配列の要素を 109 分の領域を確保しないといけないので、REになってしまいます。

vector + pair でデータの領域を 105 に抑えられるのですが、pairの部分で該当要素を取得するまでに O(N2) を費やしてしまうので、この方法も却下になります。

ここで考えなおします。

要素は 105 以内に抑えて O(N) の計算量に抑えたいと考えます。 以下のようになります。

* 要素はN個に合わせる (入力データをそのまま保持)
* 線形探索で問題を解く

これから考えると貪欲法が一番しっくりくるかなと考えました。

入力を配列に格納し、その配列をソートすれば横同士で数値が被るようになります。

そこから要素の先読みをし、その値が連番になるようならばwidth heightを更新していくことを行えば最大の横縦が求まるので後は乗算を行うことで答えが求まり、計算量とメモリ領域も足りることになります。

フロー

* 入力の受け取り

* Aiを昇順にソート

* 後ろの要素から線形探索
    * その要素から3つ先が存在する場合
        * 3つさきまで同じ要素ならば以下の処理をする 
            * width と height を更新し、要素を 3 つ先にすすめる
    * その要素から1つ先が存在する場合
        * 1つさきまで同じ要素ならば以下の処理をする
            * width と height を更新し、要素を 1 つ先にすすめる
 * width * height の出力

プログラム

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

int main(void){
  long long N;
  long long width,height;
  width = 0;
  height = 0;
  
  cin >> N;
  vector<long long> a;

  for (long long i = 0;i < N; i++){
    long long tmp;
    cin >> tmp;
    a.push_back(tmp);
  }
  sort(a.begin(),a.end());
  for (long long i = N - 1;i >= 0; i--){
    if(i - 3 >= 0){
      if(a[i] == a[i - 1] && a[i - 1] == a[i - 2] && a[i - 2] == a[i - 3]){
        width = width < a[i] ? a[i] : width;
        height = height < a[i] ? a[i] : height;
        i = i - 3;
      }
    }
    if (i - 1 >= 0){
      if(a[i] == a[i - 1] && height >= width){
        width = width < a[i] ? a[i] : width;
        i = i - 1;
      }else if(a[i] == a[i - 1] && width >= height){
        height = height < a[i] ? a[i] : height;
        i = i - 1;
      }
    }
  }
  cout << width * height << endl;
  return 0;
}

これでAC取れました。

ABC070-C Multiple Clocks を解いてみた

70回のC問題は完全に数学でしたね.数学の知識を知っていれば解ける問題で,知らなければ解けないだろうなという感触でした. では,以下問題

問題

Multiple Clocks

問題文

N 台の時計があり、i(1≦i≦N) 番目の時計の針はちょうど Ti 秒で時計盤を 1 周します。 最初、全ての時計の針は真っ直ぐ上に向いており、止まっています。 イルカは、全ての時計の針を同時に動かし始めました。 再び、全ての時計の針が真っ直ぐ上に向くのは何秒後でしょうか?

制約

* 1 ≦ N ≦ 100

* 1 ≦ Ti ≦10^18

* 入力は全て整数である。

* 答えは 10^18秒以内である。

とこんな感じですね.

色々小難しいことを書いていますが,結論をいうと入力される値の最小公倍数を求めなさいという問題です. 最小公倍数を求める際に最大公約数を求める必要があります.それを求めるアルゴリズムとしてユークリッド互除法があるのでそれを使用します.

考えたこと

ユークリッド互除法を実装するには再帰関数を使えばすごく楽なのでそれを実装すればいいと考えました.

ユークリッド互除法

f(x,y) = x (y == 0) || f(x,x % y) (y != 0)

の関数式になります.

これを実装しますと以下のようになります.

long long dev(long long base,long long num){
    if (num == 0){
        return base;
    } else {
        return dev(num,base % num);
    }
    return base;
}

あとは入力を受け取り,i ~ Nまで繰り返し処理をしながら最小公倍数を探すということをすれば問題は解けます

フロー

  • 入力を受け取り
  • 答えを 1 に設定する
  • 受け取った要素に対して以下の処理を繰り返す
    • もしその要素の剰余が0の場合
      • 答えを答えとその要素の最大にする
    • それ以外の場合以下の処理をする
      • その要素と答えを比べて大小を決める
      • 答えに 大きいほう / 最大公約数 * 小さい方にする
  • 答えを出力

プログラム

#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
using namespace std;


long long dev(long long base,long long num){
    if (num == 0){
        return base;
    } else {
        return dev(num,base % num);
    }
    return base;
}

int main(void){
    int N;
    cin >> N;
    vector<unsigned long long> T(N);

    for(int i = 0;i < N;i++){
        cin >> T[i];
    }
    unsigned long long ans = 1;
    for(int i = 0;i < N;i++){
        if(ans % T[i] == 0 || T[i] % ans == 0){
            ans = max(ans, T[i]);
        } else {
            // 互除法
            long long hi,low;
            hi = max(ans,T[i]);
            low = min(ans,T[i]);
            ans = hi / dev(hi,low) * low;
        }
    }
    cout << ans << endl;
    return 0;
}

これでAC取れました

ARC080-C 4-adjacent を解いてみた

今回の問題も数え上げベースの問題でした。400点でしたが、そこまで苦労なく解くことができました。

では、以下問題

問題

C 4-adjacent

問題文

長さ N の数列 a=(a1,a2,...,aN) があります。 各 ai は正の整数です。

すぬけ君の目標は、a の要素を自由に並べ替え、次の条件が成り立つようにすることです。 各 1 ≤ i ≤ N − 1 について、ai と ai+1 の積は 4 の倍数である。 すぬけ君が目標を達成できるか判定してください。

制約

* 2 ≤ N ≤ 10^5
* ai は整数である。
* 1 ≤ ai ≤ 10^9

とこんな感じ 結果から考えると

4 1 1  ・ ・ ・(1)
1 1 4 1 ・ ・ ・(2)
2 2 2 ・ ・ ・ (3)

(1)みたいなのはOK、(2)みたいなのはNG、(3)みたいなのはOK

となります。

これから数列の要素が奇数の場合と偶数の場合での処理を分ける必要がありそうですね。

考えたこと

愚直に2重ループで4の倍数とそれ以外のペアを見つけるのはO(N2)かかりそうなのでTLEで問題が解けません。

4の倍数の個数と奇数の数と数列の要素数の関係みていけばペアが4の倍数になるかどうかについて考えることができそうなので、この方法を採用します。

上記の例(1)場合

* 4の倍数は1個 奇数は2個 数列の要素数は3個

上記の例(2)場合

* 4の倍数は1個 奇数は3個 数列の要素数は4個

上記の例(3)場合

* 2の倍数が3個

では、(2)の場合においてOKになる場合を考えてみると 4 1 4 1 は大丈夫でしょう。このとき 4の倍数は2個 奇数は2個 数列の要素数は4個になります。

以上のことから

1. 数列の要素数が奇数の場合 4の倍数の個数 - 奇数の個数 は -1以上であれば問題ない
2. 数列の要素数が偶数の場合 4の倍数の個数 - 奇数の個数 は 0以上であれば問題ない

の二つのルールが出来上がります。 じゃあ2の倍数の(3)はどうなるのとなりますが、この場合 上の二つのルールに該当するので問題ありません。(4の倍数の個数 : 0 奇数の個数 : 0 0 - 0 = 0)

フロー

  • 4の倍数の個数、2の倍数の個数、その他の倍数の個数を定義
  • 入力を受け取り
  • 数列の受け取りのループ
    • その入力が4の倍数の場合 4の倍数の個数 +1
    • その入力が2の倍数かつ4の倍数でない場合 2の倍数の個数+1
    • それ以外の場合 その他の倍数の個数+1
  • もし、要素数が2の倍数のとき
    • 2 のルールに該当するならば
      • Yesと出力し終了
  • それ以外の場合
    • 1 のルールに該当するならば
      • Yesと出力し終了
  • Noと出力し終了

プログラム

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
using namespace std;

int main(void){
    long long N;
    cin >> N;
    vector<long long>a(N);
    long long bai4 = 0;
    long long bai2 = 0;
    long long other = 0;
    for (long long i = 0;i < N;i++){
        cin >> a[i];
        if(a[i] % 2 == 0 && a[i] % 4 == 0){
            bai4++;
        }else if(a[i] % 2 == 0 && a[i] % 4 != 0){
            bai2++;
        }else{
            other++;
        }
    }
    if (N % 2 == 0){
        if (bai4 - other >= 0){
            cout << "Yes" << endl;
            return 0;
        }
    }else{
        if (bai4 - other >= -1){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

こんな感じでACとれました。

ABC-067 C Splitting Pile を解いてみた

今回の問題も数え上げみたいな問題でした。 なかなか慣れませんがいい勉強になりましたね。

以下問題

問題

C - Splitting Pile

問題文

すぬけくんとアライグマは N 枚のカードの山を作りました。カードの山の上から i 番目のカードには整数 ai が書かれています。 N 枚のカードを分け合うことにしました。 すぬけくんがカードの山の上から何枚かのカードを取ったあと、アライグマは残ったカード全てを取ります。 このとき、すぬけくんもアライグマも 1 枚以上のカードを取る必要があります。

すぬけくんとアライグマが持っているカードに書かれた数の総和をそれぞれ x,y として、|x−y| を最小化したいです。|x−y| としてありうる値の最小値を求めなさい。

制約

* 2 ≤ N ≤ 2 × 10^5

* -10^9 ≤ ai ≤10^9

* aiは整数

とこんな感じ 入力された合計を管理して、その値の時のアライグマとすぬけくんの差の絶対値と今までの差の最小を比べてどちらが小さいかを計算していけばいいと考えて和を管理するために累積和を使っていました。 そんなこんなで、累積和を使って解いていたのですが、これ累積和いらないってわかり、変数で解きました。

考えたこと

数列の合計値と i までの和がわかれば、すぬけくんとアライグマの両方のカードの数字が算出することが可能になります。 方程式の関係になり数式で考えるとわかりやすいです。

sum(合計値), sunuke(すぬけくんの数),arai(アライグマの数)
sum = sunuke - arai
arai = sum - sunuke
sunuke = sum - arai

と関係が成り立ちます。 これが成り立つので すぬけくんとアライグマの 減算は求められ、最小値の比較に対するものは一つ出来上がります。 あとは答えを設定し、それぞれの要素に置いて差を求め最小値を算出すればO(N)時間で終わるため、問題が解けることになります。

フロー

* 入力受け取り
* 数列の和の計算
* 答えを10^18で設定
* すぬけくんとアライグマの数を0で設定
* 数列の各要素に対してループ
     * すぬけくんの数に該当要素を足す
     * アライグマの値を `総和 - すぬけくんの和` とする
     * もし、その要素が最終要素でない時に以下の処理をする
         * 答えに 今の答えとすぬけくんとアライグマの差の絶対値を取ったものの小さい方を代入
* 答えを出力

とこんな感じ 答えを1018で設定しているのは初期に109以上の数が109個こないのが制約により保証されているからです

プログラム

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

int main(void){
    long long N;
    cin >> N;
    vector<long long> a(N);
    vector<long long> resi(N);
    long long sum = 0;
    for(long long i = 0;i < N;i++){
        resi[i] = 0;
    }
    for(long long i = 0;i < N;i++){
        cin >> a[i];
        sum += a[i];
    }
    long long ans = 1000000000000000000;
    long long sunuke = 0;
    long long arai = 0;
    for(long long i = 0;i < N; i++){
        sunuke += a[i];
        arai = sum - sunuke;
        if(i < N - 1){
            ans = min(ans,abs(sunuke - arai));
        }
    }
    cout << ans << endl;
    return 0;
}

こんな感じでAC取れました。 解答をみて気づいたのですが、最小値をとる時に abs(sum - 2 * sunuke) でも良さげですね 等式変形をしたら辻褄が合います。 でも、数弱にはデータ構造に落とし込んだ方がわかりやすい。。

Tenka1 Programmer Contest/Tenka1 Programmer Beginner のC問題を解いてみた

昨日の天下一コンテストお疲れ様でした。 色々と課題の残るコンテストで学ぶ部分も多いコンテストでした。

今回のCのような問題が一番苦手なのかもしれません。。結構自分はデータ構造系の問題が得意なのですが、複雑なアルゴリズムを考える部分が苦手なんでここを磨き上げていきたいです。

では、以下問題

Stones

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

N 個の石が一列に並んでおり、すべての石は白か黒で塗られています。 石の状態は長さ N の文字列 S で表され、S の i 文字目が . のとき左から i 個目の石が白であり、# のとき左から i 個目の石が黒であることを表します。 高橋君は、0 個以上の石の色を黒または白に変更し、黒い石のすぐ右に白い石があるような箇所がないようにしたいです。 色を変更する必要のある石の個数の最小値を求めてください。

制約

* 1 ≤ N ≤ 2 × 10^5
* S は ., # のみからなる長さ N の文字列である

とこんな感じですね 解いてた時、しゃくとり法で反転区間が最小になるものを算出するのかなと思っていたのですが、それだと 不連続な場合の問題が解けないため却下という感じです。 また愚直にシミュレーションを行い比較を行うとO(2N)となるのでとても現実的でないことがわかります。

考えたこと

先に結果の形から考えてみましょう結果のパターンとして3つのパターンが考えられます。

* "白 白 ... 黒 黒" この時 (白は連続し黒との境界以降白は出てこないものとする)
* "白 白 白 ... 白 白"
* "黒 黒 黒 ... 黒 黒"

となります。 そして今回の問題の肝は反転回数が最小の値を求めよとのことなので、上記の3パターンに帰着するための反転回数の最小を算出することになります。

ではどうすれば良いか 白の数を数え上げ、白の反転の個数と黒の反転の個数の和の最小を求めることで解決します。 黒の反転の個数を0とし白の反転の個数を白の数とします。 ではここでルールを決めます(例として".#..#"の文字列を使用します)

* 最初に数え上げた白の個数を右の値に入れます
* 無視できるのは右にある黒の個数と左にある白の個数
* 文字列を線形探索するとき
     * 今の要素が黒ならば、右にある黒を+1します。
     * それ以外ならば右にある白を左に移動させます。

1 回目

0 0

1 2

この時は 2

2回目

1 0

1 2

この時は 3

3回目

1 0

2 1

この時は 2

4回目

1 0

2 0

この時は 1

5回目

2 0

2 0

この時は 2

結局5回の中で最小は 1 つまり、"....#" という文字列になります このアルゴリズムで問題なく解けそうですね。

フロー

* 入力の受け取り
* 文字列に対してループ
    * その要素が"."ならば白の個数を+1
* 右にある白を白の個数に黒を0にし、答えを白の個数に定義
* 文字列に対してループ
    * その要素が"#"ならば 黒の個数 を+1
    * それ以外の場合 白の個数を - 1
    * 答えに答えと白と黒の個数の最小を代入
* 答えを出力

とこんな感じ 2回目の文字列ループの際に前述したルールが組み込まれています

プログラム

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

int main(void){
    long long N;
    string S;
    cin >> N >> S;
    long long w = 0;
    for(long long i = 0; i < N; i++){
        if(S[i] == '.'){
            w++;
        }
    }
    long long BL = 0;
    long long WR = w;
    long long ans = w;
    for(long long i = 0; i < N; i++){
        if(S[i] == '#'){
            BL++;
        }else{
            WR--;
        }
        ans = min(ans,BL + WR);
    }
    cout << ans << endl;
    return 0;
}

とこんな感じでAC取れました。 このようなアルゴリズムの問題にめっぽう弱いので慣れていきたいです。。