ABC-068 C Cat Snuke and a Voyage を解いてみた

今回の問題もデータ構造に関する問題でした。基本的に問題の解き方はグラフを作りダイクストラあたりで解くか、1 ~ Nまでの経路が存在するかのデータ構造を構築するあたりが妥当でした． ハッシュ的に解く想定はできたのですがTLEとWAで，なかなかACできず苦労しました． では以下問題文

問題

Cat Snuke and a Voyage

高橋キングダムには、高橋諸島という、N 個の島からなる諸島があります。 便宜上、これらの島を島 1、島2、 ...、島 N と呼ぶことにします。

これらの諸島の間では、船の定期便が M 種類運行されています。 定期便はそれぞれ 2 つの島の間を行き来しており i 種類目の定期便を使うと、 島 aiと島 bi の間を行き来する事ができます。

すぬけくんは今島 1 にいて、島 N に行きたいと思っています。 しかし、島 1 から島 N への定期便は存在しないことがわかりました。 なので、定期便を 2 つ使うことで、島 N に行けるか調べたいと思っています。

これを代わりに調べてあげてください。

制約

• 3≦N≦200,000
• 1≦M≦200,000
• 1≦ai<bi≦N
• (ai,bi)≠(1,N)i≠j ならば (ai,bi)≠(aj,bj)

---

とこんな感じ

考えたこと

出発点と目的地が決まっていれば、計算する部分は1 ~ i と i ~ Nということがわかります。つまり全探索前に全探索ができるようにデータ構造をつくれるかどうかが鍵になってくるなと考えました。

入力を受け取りながら出発地が1の時に目的地の場所をハッシュで保持し、その要素を真にします。その次にNが目的地の時に出発地の場所にハッシュで保持し、その要素を真にする。

この操作はO(M)の操作で終わります 次に全探索を行いNまでの経路があるかを洗い出します。

フロー

• 入力の受け取りN,M
• 2つの配列を宣言し配列の中身を初期化
• 制約外なら終了
• 定期便の入力を受け取りながら以下の処理をする
  • 出発地と目的地の受け取り
  • もし出発地が1の時に片方の配列の目的地の要素を真にする
  • もし目的地がNの時に片方の配列の出発地の要素を真にする
• 各島(N)に対して以下の処理を行う
  • もしその島が目的地かつNへの出発地ならばPOSSIBLEと出力
  • 終了
• IMPOSSIBLEと出力
• 終了

みたいな感じになりました 全探索の際は定期便の中心となるNがループの主体になります。

プログラム

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

int main(void){
    int N , M;
    cin >> N >> M;
    vector<bool> a(200000);
    vector<bool> b(200000);
    for (int i = 0;i < 200000; i++){
        a[i] = 0;
        b[i] = 0;
    }
    if (N < 3 && N > 200000 && 1 > M && M > 200000){
        return 0;
    }
    for (int i = 0;i < M; i++){
        long long from,to;
        cin >> from >> to;
        if(from == 1){
            a[to] = true;
        }
        if(to == N){
            b[from] = true;
        }
    }
    for (int i = 0;i < N; i++){
        if(a[i] && b[i]){
            cout << "POSSIBLE" << endl;
            return 0;
        }
    }
    cout << "IMPOSSIBLE" << endl;

    return 0;
}

これでAC取れました

ABC-066 C pushpush を解いてみた

ABC-C 066を解いたのですが、今回の問題はデータ構造を知っているか知らないかの問題で解けたのですが、最初、提出した際に TLE でできなかったのでなんでかなとおもったら使っていた STL のメソッドが悪かったようでした。 今回はデータ構造について学ぶことが多く良問でした。

では、以下問題

問題 C - pushpush

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

配点 : 300 点

問題文

長さ n の数列 ai ,..., an が与えられます。 空の数列 b に対して、以下の操作を n 回行うことを考えます。 i 回目には数列の i 番目の要素 ai を b の末尾に追加する。b を逆向きに並び替える。この操作をしてできる数列 b を求めて下さい。

制約

• 1 ≤ n ≤ 2 × 10⁵
• 0 ≤ ai ≤ 10⁹
• n,ai は整数である。

---

とこんな感じ 見た感じ結構複雑な操作をしていますが、実はそうでもないものです。おそらく面食らうのは逆向きにならべかえるという部分ですが、実際にはこの作業は不要になります。並び変えをすると特定条件で最速でもO(N) 最悪の場合 O(N²) で制約からすると最大のNは 10⁵ なのでこの操作は避けたいっといったところです。

考えたこと

並び替えが発生するのを避けたいので、並び替えをしなくてもいい方法を見つけました。ここで注目するのは最初の入力のNとループを回す変数になります。 ループを回している変数が偶数の場合は反転×反転なので追加する場所は変わらないので、最初に要素が挿入されます。逆に奇数の場合は1回の反転なので最後に要素が挿入されます。 こうすると途中の並び替えの操作が不要になります。 Nが偶数の場合はもとの状態なので反転させる必要があるため、末尾要素から出力していき、Nが奇数の場合はすでに反転しているので最初から出力していくというものになります。

フロー

• 入力受け取り
• キューを定義
• Nに対して線形ループを行う
  • もしループの変数が偶数ならば以下の処理
    • キューの最初に追加をする
  • それ以外ならば
    • キューの最後に定義
• もしNが偶数ならば
  • キューの末尾からループを行う
    • キューの出力
• それ以外ならば
  • キューの最初からループを行う
    • キューの出力

みたいな感じです。 ここでなぜキューを使っているかというとVector配列だと 最初の要素に入れる関数がinsertになってしまい。これはメモリを線形探索して最初の要素を探すということをしているらしいのでinsertを使うと実質 N² のオーダになってしまうということになります。

プログラム

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

int main(void){
    int N;
    cin >> N;
    vector<long long> a(N);
    deque<long long> b;

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

    for(int i = 0;i < N;i++){
        if(i % 2 == 0){
            b.push_front(a[i]);
        }else{
            b.push_back(a[i]);
        }
    }
    if (N % 2 == 0){
        for(int i = b.size() - 1;i >= 0;i--){
            cout << b[i] << " ";
        }
    }else {
        for(int i = 0; i < b.size(); i++){
            cout << b[i] << " ";
        }
    }

    return 0;
}

これでACとれました

ABC-065 C Reconciled? を解いてみた

今回の問題はデータの情報落ちとの戦いでした。。 アルゴリズム自体はすぐにでてきて簡単に実装はできたのですが、longlong で素直に計算してもあれれ？これなぜ負の数がでてくるの？みたいな感じになってしまって結構大変でした。

では以下問題

問題

問題文

すぬけ君は、犬を N 匹と猿を M 匹飼っています。すぬけ君は、この N+M 匹を一列に並べようと思っています。

文字通り犬猿の仲の犬たちと猿たちを仲直りさせたいすぬけ君は、犬同士、または猿同士が隣り合うところができないように並べようと思っています。

このような並べ方は何通りあるでしょうか。犬と猿は 10⁹+7 以上の数を理解できないので、並べ方の個数を 10⁹+7 で割ったあまりを求めてください。 ただし、犬同士、また猿同士は互いに区別します。また、左右が反転しただけの列も異なる列とみなします。

制約

* 1≦N,M≦10^5

---

と言うもの

愚直に配列用意してそこに犬いれて猿いれて。。なんてしていたら計算のオーダはN,Mが大きくなるにつれて階乗並みに増えていくので現実的ではない。。

考えたこと

犬と猿の交互の列が何個作れるかの問題なので、まず N と Mについての関係を紐解く 交互にするためには、 絶対値|N - M| は 1以下であることが必須条件になってくる。|N-M|=1の時はスワップを利用し考え、N - M = 0の時と分けて考えれば良いと言うことです。 では次に列の種類の算出ですが、次のように考えましょう

文字列	1	2	3	4	5
累積配列	犬a	猿a	犬b	猿b	犬c

のような列ができるとします。これは一例なのでもっと抽象化しましょう

文字列	1	2	3	4	5
累積配列	犬	猿	犬	猿	犬

こうすれば数式が見えてくると思います。

• 1に入るのは a,b,c のどれか -> 組み合わせは 3×2×1 = 6

• 2に入るのは a,b のどれか -> 組み合わせは 2×1 = 2

• 3に入るのは1に入った以外の二つ -> 組み合わせは2×1 = 2

• 4に入るのは残った猿 -> 組み合わせは 1

• 5に入るのは残った犬 -> 組み合わせは1

これらは排反なので 加算で列の種類数が算出できます。

フロー

• 入力の受け取り
• もし N = Mである時
  • Mの値を変数に格納する
  • 答えを1とする
  • N から 1 までループを回しながら
    • ループの変数とMの値の変数と答えを乗算し 10⁹ + 7の剰余をとる
    • Mの値の変数をデクリメント
  • 答えを2倍する
  • 答えに対して 10⁹ + 7の剰余をとる
  • 答えの出力
• もし N - 1 = M または M - 1 = N の時
  • もし M - 1 = N の時
    • NとMをスワップ
  • Nの値を変数に格納する
  • 答えを1とする
  • M から 1 までループを回しながら
    • ループの変数とNの値の変数を乗算し10⁹ + 7の剰余と 10⁹ + 7の剰余 を乗算し その結果から 10⁹ + 7の剰余をとる
    • Nの値の変数をデクリメント
  • 答えの出力
• それ以外の時
  • 0を出力する

とこんな感じ

プログラム

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

int main(void){
    long long N,M;
    cin >> N >> M;
    if (N == M){
        unsigned long long ans = 1;
        unsigned long long tmp = M;
        for(long long i = N;i > 0;i--){
            ans = (i * tmp * ans) % (1000000000 + 7);
            tmp--;
        }
        ans *= 2;
        ans = ans % (1000000000 + 7);
        cout << ans << endl;
    }else if(N - 1 == M || M - 1 == N){
        if(M - 1 == N){
            swap(N,M);
        }
        long long ans = 1;
        long long tmp = N;
        for(long long i = M;i > 0;i--){
            ans = ((i * tmp)% (1000000000 + 7) * (ans % (1000000000 + 7)) % (1000000000 + 7));
            tmp--;
        }
        cout << ans % (1000000000 + 7) << endl;
    }else{
        cout << 0 << endl;
    }
    return 0;
}

ABC-064 C Colorful Leaderboard を解いてみた

昨日記事をあげたかったのですが、疲れ切っててあげることができませんでした。。 今回の問題は学ぶことがAC取った後にあったので、今後気をつけていこうかなと思います。。

では、以下問題

Colorful Leaderboard

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

配点 : 300 点

問題文 AtCoderでは、コンテストに参加すると「色」が付き、これはレートによって次のように変化します：

レート 1-399：灰色 レート 400-799：茶色 レート 800-1199：緑色 レート 1200-1599：水色 レート 1600-1999：青色 レート 2000-2399：黄色 レート 2400-2799：橙色 レート 2800-3199：赤色 また、レートが 3200 以上になると色を自由に変えることができます。 現在 N 人の人がAtCoderのコンテストに参加したことがあり、i 人目の人のレートは ai です。 そのとき、色の種類数の最小値と最大値を求めなさい。

制約 1≤N≤100 1≤ai≤4800 ai は整数である。

---

とこんな感じ

考えたこと

色の数が必要なのでその色にいる人をカウントするデータ構造を作って3200以上の人は個別にカウントする

フロー

• 入力の受け取り
• 色が存在するデータ構造の初期化
• 入力の回数以下の処理を繰り返す
  • 入力を受け取り
  • レートの場所にたいしてデータを格納する
• 色の数分処理を繰り返し
  • 3200 以上の人以外は1をmin,maxに足す
• max には 3200人以上の人の数分足す
• minには0の場合1を代入する
• 出力というフロー

コード

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

int main(void){
    int N,min,max;
    cin >> N;
    vector<int> color(9);
    for(int i = 0;i < 9;i++){
        color[i] = 0;
    }
    min = 0;
    max = 0;
    for(int i = 0;i < N;i++){
        int tmp;
        cin >> tmp;
        if(tmp >= 1 && tmp < 400){
            color[0]++;
        }else if(tmp >= 400 && tmp < 800){
            color[1]++;
        }else if(tmp >= 800 && tmp < 1200){
            color[2]++;
        }else if(tmp >= 1200 && tmp < 1600){
            color[3]++;
        }else if(tmp >= 1600 && tmp < 2000){
            color[4]++;
        }else if(tmp >= 2000 && tmp < 2400){
            color[5]++;
        }else if(tmp >= 2400 && tmp < 2800){
            color[6]++;
        }else if(tmp >= 2800 && tmp < 3200){
            color[7]++;
        }else if(tmp >= 3200 && tmp <= 4800){
            color[8]++;
        }
    }
    for(int i = 0;i < 9;i++){
        max = color[i] != 0 && i != 8 ? max + 1 : max;
        min = color[i] != 0 && i != 8 ? min + 1 : min;
    }
    max = color[8] + max;
    min = min != 0 ? min : 1;
    cout << min << " " << max << endl;
    return 0;
}

ですが、ここで気づきます。真ん中の邪魔臭いって ここの真ん中のifは実際には400の倍数飛ばしになっているので2重ループを回しながら(N * color)をしながらデータ構造を作ればもっとスマートになります。 問題解釈と把握能力ですかね。。

ABC-124 C Coloring Colorfully を解いてみた

昨日諸々打合せがあって、ABC途中参加でCまで時間内に解けたので上出来な気がしました。DまでACしたかった...

昨日のC問題を忘れないうちにメモしようかなと思います。 では、以下問題

Coloring Colorfully

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

配点 : 300 点

問題文

左右一列に N 枚のタイルが並んでおり、各タイルの初めの色は長さ N の文字列 S で表されます。

左から i 番目のタイルは、S の i 番目の文字が 0 のとき黒色で、1 のとき白色で塗られています。 あなたは、いくつかのタイルを黒色または白色に塗り替えることで、どの隣り合う 2 枚のタイルも異なる色で塗られているようにしたいです。

最小で何枚のタイルを塗り替えることで条件を満たすようにできるでしょうか。

制約

1≤|S|≤10⁵ Si は 0 または 1 である。

---

とこんな感じ

O(N)で解けるのを想定したら結構簡単に解法がでてきたんでよかったです。

考えたこと

1箇所分かれば完成系の文字列がわかるので最初にそのデータ構造作ってしまって、そのあと線形的に照合をしていってカウントし、文字列の長さから引くと言う方法で行けるかなと思いました。 最後の出力は文字列の長さからカウントを引いたものとカウントを比較し、小さい方を出力すれば問題は解けました。

フロー

• 入力の受け取り
• 最初の文字が0の時は以下の処理をする
  • 文字の個数分繰り返しながら以下の処理をする
    • 偶数の時 0 奇数の時 1 を配列に格納する
• 0以外の時以下の処理をする
  • 文字の個数分繰り返しながら以下の処理をする
    • 偶数の時 1 奇数の時 0 を配列に格納する
• 文字列に1文字つつアクセスする
  • 作った配列と要素が違った場合カウントを1つ増やす
• 文字列の要素数からカウントを引いたものと カウントの比較をし小さい方を出力する

と考えました。最後の最初の算出は結局入れ違えの反転を考慮するものなので反転回数は |S|/2より以上にはならないのでここで比較を行います。

プログラム

このようになりました。

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

int main(void){
    string S;
    cin >> S;
    int N = S.size();
    vector<char> Trans(S.size());
    if (S[0] == '0'){
        for(int i = 0;i < S.size(); i++){
            Trans[i] = i % 2 == 0 ? '0' : '1';
        }
    }else{
        for(int i = 0;i < S.size(); i++){
            Trans[i] = i % 2 == 0 ? '1' : '0';
        }
    }
    int count = 0;
    for(int i = 0;i < S.size();i++){
        if(S[i] != Trans[i]){
            count++;
        }
    }
    cout << min(count,N-count) << endl;
    return 0;
}

これでAC取れました

ABC-063 C Bugged を解いてみた

今日もC問題を解いてみました。

区間内の最大値を組合せ計算の最大値を出力せよと言うもの

では問題を見ていきましょう 以下問題

Bugged

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

配点 : 300 点

問題文

あなたはコンピュータで試験を受けています。試験は N 問の問題からなり、i 問目の問題の配点は si です。それぞれの問題に対するあなたの解答は「正解」または「不正解」のいずれかとして判定され、正解した問題の配点の合計があなたの成績となります。あなたが解答を終えると、解答がその場で採点されて成績が表示される…はずでした。

ところが、試験システムに欠陥があり、成績が 10 の倍数の場合は、画面上で成績が 0と表示されてしまいます。それ以外の場合は、画面に正しい成績が表示されます。この状況で、成績として画面に表示されうる最大の値はいくつでしょうか？

自分の考えたこと

愚直に計算して最大値をだすとそれぞれの問題の成績から正解した問題と不正解の問題の点数のシミュレーションを行い、最大値を算出すると言う方法がありますが、計算のオーダは2の累乗になってしまいN=100で計算をしても2¹⁰⁰なので現実的でない。。

そこで、計算オーダを抑えるために考えた結果、最初に全て正解した際の計算を行いそこから10の倍数にならない成績の最小の点数を引けば最大値が求められます。

プログラムのフロー

• 入力を受け取りながら、最大値の計算を行う
• 成績に一つずつアクセスする
  • もし最大値が10の倍数ならばループを抜ける
  • 成績の配列に 最大値 - 成績 の値を格納する
• 最大値が 10の倍数の場合
  • 最大値を0とする
  • 最大値 - 成績 に 1つずつアクセスする
    • 最大値よりも最大値 - 成績 が大きい かつ 最大値 - 成績 が10の倍数でない場合 に 最大値 - 成績 で最大値を更新する
• 最大値が10の倍数の場合 最大値を0とする
• 最大値を出力する

とまあこんな感じに考えました。終わって考えてみると、10の倍数のあとreturn 0;しておけばそのあとの分岐いらないはずだったんですが。。まあAC取れたのでよしとしましょう.

コード

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

int main(void){
    int N,max;
    cin >> N;
    vector<int> score(N);
    max = 0;
    for(int i = 0;i < N;i++){
        cin >> score[i];
        max += score[i];
    }
    for(int i = 0;i < N;i++){
        if(max % 10 != 0)
            break;
        score[i] = max - score[i];
    }

    if(max % 10 == 0){
        max = 0;
        for (int i = 0;i < N;i++){
            max = score[i] > max && score[i] % 10 != 0 ? score[i] : max;
        }
    }
    max = max % 10 == 0 ? 0 : max;
    cout << max << endl;
}

これでACとりました。

ABC-62 C Chocolate Bar を解いてみた

ABC-62 C は400点だったこともあり、理解まで時間を少し要しましたが、なんとか自力ACできました。 今回の問題の概要は配列を連想させるような問題ですが、本質は数学的な考えができるかの問題でした。

では、以下問題

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

配点 : 400点

問題

縦 Hブロック、横 W ブロックの板チョコがあります。 すぬけ君は、この板チョコをちょうど 3 つのピースに分割しようとしています。 ただし、各ピースはブロックの境目に沿った長方形でなければなりません。すぬけ君は、3 つのピースの面積 (ブロック数) をできるだけ均等にしようとしています。 具体的には、3 つのピースの面積の最大値を Smax、最小値を Smin としたとき、Smax−Smin を最小化しようとしています。 Smax−Smin の最小値を求めてください。

制約

2≤H,W≤10⁵

とまあこんな感じ

自分の考えてたこと

線の引き方を考えました。1つのものを他の線とクロスしないような引き方でいくと2本の線を引くことで三分割が実現します。 ここで3分割の方法でつまづいてなかなかACできませんでした。。

分割の方法

一つの面を3分割にするので分割の手順は4通りあります。

* 横×横
* 縦×縦
* 縦×横
* 横×縦

ですね ですが、この分割の見方を変えると2通りの分割を考えておけばいいという考えに辿りつきます。 縦からするか横からするかの問題で、縦と横をスワップして同じ操作を行えば解決します。

フローは以下のようになります。

• 入力の受け取り
• もし 縦が3で割り切れる または 横が3で割り切れる
  • 答えを0とする
• それ以外の場合
  • 答えを縦の長さと横の長さの短い方にする
• 縦の長さに対して線形的にアクセスする
  • その時点での面積をSaとし変数に格納する
  • 横の長さを二等分する (w1 = W / 2 , w2 = W - w1)
  • 求めた横の長さで面積Sb,Scを求める
  • 面積の最小最大を求める
  • 差が最小な値を答えとする
• 縦と横をスワップする
• 縦の長さに対して線形的にアクセスする
  • その時点での面積をSaとし変数に格納する
  • 横の長さを二等分する (w1 = W / 2 , w2 = W - w1)
  • 求めた横の長さで面積Sb,Scを求める
  • 面積の最小最大を求める
  • 差が最小な値を答えとする
• 答えを出力

見たいな考え方で行けます スワップ後は全く同じ処理なので関数に分けたらきれいになるかもですね

以下コードになります。

    #include <iostream>
    #include <vector>
    #include <cmath>
    #include <algorithm>
    using namespace std;
     
    int main(void){
        long long H,W;
        const int MAX = 100000;
        // input
        cin >> H >> W;
        // 制約
        if (H < 2 && H > MAX && W < 2 && W > MAX){
            return 0;
        }
        long long Sa,Sb,Sc,Smax,Smin;
        long long ans = 100000000000000;
        // 横横 縦縦
        if (H % 3 == 0 || W % 3 == 0){
            ans = 0;
        }else{
            ans = min(ans, min(H,W));
        }
        // 横 縦
        for (int i = 1;i < H;i++){
            Sa = i * W;
            long long w = W / 2;
            Sb = (H - i)*w;
            Sc = (H - i)*(W -w);
            Smax = max(Sa,max(Sc,Sb));
            Smin = min(Sa,min(Sc,Sb));
            ans = min(ans,Smax - Smin);
        }
        swap(H,W);
        // 縦 横
        for (int i = 1;i < H;i++){
            Sa = i * W;
            long long w = W / 2;
            Sb = (H - i)*w;
            Sc = (H - i)*(W -w);
            Smax = max(Sa,max(Sc,Sb));
            Smin = min(Sa,min(Sc,Sb));
            ans = min(ans,Smax - Smin);
        }
        cout << ans << endl;
     
        return 0;
    }

これでAC取れました。