2019-04-10

ABC-61 C big Array を解いてみた

昨日は60-Cを解いたので今日は61-Cを解いて行きました

60-Cよりも考えることが多く結構身になった感じがしました。

以下問題

問題文

空の配列が 1つあります。この配列に、整数を配列に挿入する操作を N 回行います。 i (1≦i≦N) 回目の操作では、配列に整数 aiを bi 個挿入します。 N 回の挿入操作後の配列の中で、K 番目に小さい数を求めてください。例えば、配列が {1,2,2,3,3,3} の時、4 番目に小さい数は 3となります。

制約

1≦N≦10⁵
1≦ai,bi≦10⁵
1≦K≦b1…+…bn
入力は全て整数である。

こんな感じ。

おそらくこの問題文のまま実装するとメモリエラー&時間が足りないと言うことになると思います。 (入力のたびにメモリを確保して配列を作り直すのは1024KBを超えてしまう & 作り直した配列をソートの仕方にもよるが、TLEになりかねない？)

考えたこと

まず、問題文のまま実装するとエラーになるので、ハッシュ法風に実装すれば良いのでは？と考えました。

index	0	1	2	3
factor	2	4	5	6

のように0は2個 1は4個....のようにindexはfactor個とデータ構造を構築すれば良いと思います。

次にフローになります

N,K入力を受け取りそのデータから初期化を行う
ai bi入力を受け取りながら上記のデータ構造を構築して行く
そのデータ構造にアクセスする
- indexのfactorが、Kよりも大きい場合にそれを答えとし、データを保持する
その答えを出力する

と言うもの

コードになります

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

int main(void){
    long long N,K,ans;
    cin >> N >> K;
    vector<long long> container(N);
    // init
    for (long long i = 0; i < 100000;i++){
        container[i] = 0;
    }
    ans = 0;

    for (long long i = 0; i < N; i++){
        long long ai,bi;
        cin >> ai >> bi;
        if (ai >= 1 && ai <= 100000 && bi >= 1 && bi <= 100000){
            container[ai] += bi;
        }
    }

    for (long long i = 0;i < 100000; i++){
        if(0 < K - container[i]){
            ans = i + 1;
        }
        K -= container[i];
    }
    cout << ans << endl;
    return 0;
}

今回つまづいた点

制約をあまり考慮せずコーディングしていたら RE 連発したので制約には厳しくありたい。。

2019-04-09

ABC-60 C 解いて見た

なかなかAtCoderのCDの完答率が安定しないのでCD問題を解いた時の考え方やそのほかをまとめていきます。

では以下問題

ABC-60 C

Sentou

問題文

とある銭湯には、スイッチを押すと $T$ 秒間お湯が出るシャワーがあります。

なお、お湯が出ているときにスイッチを押すと、そのタイミングから $T$ 秒間お湯が出つづけます。お湯の出る時間が $T$ 秒間延長されるわけではないことに注意してください。

このシャワーの前を、 $N$ 人の人がスイッチを押して通り過ぎていきます。 $i$ 人目の人は、 $1$ 人目の人がスイッチを押した $t_{i}$ 秒後にスイッチを押します。

お湯が出る時間の総和は何秒かを求めてください。

制約

$1 ≦ N ≦ 200, 000$
$1 ≦ T ≦ 10^{9}$
$0 = t_{1} < t_{2} < t_{3} <, . . ., < t_{N - 1} < t_{N} ≦ 10^{9}$
$T, t_{i}$ はすべて整数である

考えたこと

最初にシャワーが出ている時間にボタンが押されない場合の最大の時間を求めて、そのあとボタンが押されている時間に押された時間分の差分を算出し最大の時間との差分を取れば良い

フローは以下のように考えました

- 入力の受け取り

- その入力からシャワーが最大で出る時間を算出する(N × T)

- それぞれ ti にアクセスしながら以下の処理をする

- もし最後の要素ではなく今の時間(ti)と次の時間(ti + 1)の差分がT未満の時

- 最大の時間からシャワーの時間と時間(ti)と次の時間(ti + 1)の差分をとる

- 最大の時間を出力する

ソースコード

>|cpp|
#include <iostream>
#include <vector>
using namespace std;

int main(void){
    int N,T;
    int max;
    vector<unsigned long> ti(N);
    max = N * T;
    for(int i = 0; i < N; i++){
        cin >> ti[i];
    }
    for(int i = 0; i < N; i++){
        if (i != N - 1 && ti[i + 1] - ti[i] < T){
             max = max - (T - (ti[i + 1] - ti[i]));
        }
    }
    cout << max << endl;
}

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