ABC388個人的備忘録

早解きの波を泳ぎ切った男の備忘録です

### コンテスト概要
HHKBプログラミングコンテスト2025(AtCoder Beginner Contest 388)

https://atcoder.jp/contests/abc388

開催日:2025年1月11日 21:00-22:40

## [A - ?UPC](https://atcoder.jp/contests/abc388/tasks/abc388_a)
#### 考察
ここ最近わかりやすいA問題が続いていてありがたい。
先頭が大文字であることが確定しているので、先頭だけ拝借しそのあとに"UPC"の文字をつなげるだけ。

#### 提出
``` c++:A.cpp
#include <bits/stdc++.h>
using namespace std;

int main(){
    char x;
    cin >> x;

    cout << x << "UPC" << endl;
}
```

## [B - Heavy Snake](https://atcoder.jp/contests/abc388/tasks/abc388_b)
#### 考察
制約が100しかないので二重ループでも問題なし。長さを増やした時の蛇の重さをすべての個体に対して調べ、最強の蛇の重さが答え。
コンテスト中は気にして無かったが「ヘビーなヘビ」を探す問題だったのか。

#### 提出
``` c++:B.cpp
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,d;
    cin >> n >> d;

    vector<int>T (n),L (n);
    for(int i=0;i<n;i++) cin >> T[i] >> L [i];

    for(int i=1;i<=d;i++){
        int ans = 0;
        for(int j=0;j<n;j++){
            ans = max(ans,T[j] * (L[j]+i));
            //j番目までに最も重い蛇の重さをansに格納
        }
        cout << ans << endl;
    }
    
}
```

## [C-Various Kagamimochi](https://atcoder.jp/contests/abc388/tasks/abc388_c)
#### 考察
すでに昇順に並んでくれてる。やさしいね。
要するに各餅について二倍以上の大きさの餠がいくつあるのかを調べる必要がある。
この手のものは二分探査を使えば瞬殺。

```c++:C.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    vector<int>num (n);
    for(int i=0;i<n;i++) cin >> num[i];

    ll ans = 0;
    for(auto x:num){
        ll c = num.end() - lower_bound(num.begin(),num.end(),x*2);
        //これで2*x以上の要素の数が一発ででる。
        ans += c;
    }

    cout << ans << endl;
    
}
```

## [D-Coming of Age Celebration](https://atcoder.jp/contests/abc388/tasks/abc388_d)
#### 考察
(成人を岩で祝う星人...?聞き覚えがあるような?)
成人した宇宙人はこの後石を配るしかないので成人するタイミングで前もって配ってしまう。
成人したら配れるだけ後輩に石を配り余った分が自分の取り分になる。
貰う石はそれを管理する配列を作っておき、まじめに配るとTLEするのでimos法を使いさぼりながら配っていく。

#### 提出
``` c++:D.cpp
#include <bits/stdc++.h>
using namespace std;

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

    vector<int>num (n);
    for(int i=0;i<n;i++) cin >> num[i];

    vector<int>stn (n,0);
    for(int i=0;i<n;i++){
        if(i != 0) stn[i] += stn[i-1];
        //これまでに貰った石の数を算出
        num[i] += stn[i];
        //手持ちに加える

        if(i == n-1) break;

        int k = min(n-i-1,num[i]);
        num[i] -= k;
        //手持ちに残る石の数を出す
        stn[i+1]++;
        if(k < n-i-1) stn[i+k+1]--;  
        //imos法でみんなに配っていく
    }

    for(auto x:num) cout << x << endl;    
}
```

## [E - Simultaneous Kagamimochi](https://atcoder.jp/contests/abc388/tasks/abc388_3)
#### 考察
すでに昇順に並んでくれてる。やさしいね。
「n個の鏡餅を作ることはできるか？」という問題に言い換え二分探査で答えを探る。
n個の鏡餅については土台を大きいものにして損はないので大きい順にn個並べておく。あとはこの上に餠を乗せることができるかをチェック。

```c++:E.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    vector<ll>num (n);
    for(int i=0;i<n;i++) cin >> num[i];

    int h = 0,t = n+1;
    //作れない最小の個数を調べる
    while(h != t){
        int c = (h+t)/2;
        //鏡餅はC個作れるか？

        int k = n-c;
        //使える小さい餠の数
        for(int i=0;i<n-c;i++){
            if(k == n) break;
            if(num[i]*2LL <= num[k])k++;
        }

        if(k == n) h = c + 1;
        //土台の餠がすべて埋まってるならC個は作れる
        else t = c;
        //そうでなければC個は作れない
    }

    cout << h - 1 << endl;
    //h個は作れないのでその1つ下が上限値
}
```

## 結果
結果　ABCDE　5完 35:52

順位　892位
パフォーマンス 1626

## 感想
年末年始と燻っていたが、それを吹き飛ばす大勝。というか青パフォ自体が初めてという自己最高成績。
早解きは苦手だが今回は得意の二分探査が多かったので事なきを得た。

この調子が続けば入水も手の届く位置に！しっかりと兜の緒を締めていこう。