AtCoder ABC376 振り返り

AtCoder Beginner Contest 376 の振り返りです。

AtCoder Beginner Contest 376（Promotion of AtCoder Career Design DAY）

150-250-350-400とABCのレートが50ずつ高くなっているような配点。実際、問題も実装量が多かったり一捻りあったりして、全体的に手こずった。

コンテスト成績 >

A: Solved

累積経過時間に応じてボタンを推した回数を答える単純な問題。ボタンを推せるインターバル時間が変数になっている分、いつもの超単純なA問題よりはちょっと面倒ではあったかな。

特にハマることもなく、１発AC。

B: Solved

両手で握ったリングを片方の手だけ持ち替えていき、その移動教理を出力する問題。反対の手がどこにあるかによって、移動先への経路が変わる部分の条件処理が結構面倒でかなり時間をかけることになった。

反対の手との距離と移動先への距離を時計回りに比較して、どちら回りに移動するべきかを判定した。ただ、この判定にだいぶ手こずってしまい、途中でなんどかシミュレーション出とこうかと思案したが、なんとかACできた。時間がかなり吸われてしまった。

C: Solved

おもちゃをサイズにあった箱に入れていき、入らなかったおもちゃが一つの場合には、そのおもちゃにシンデレラフィットする箱のサイズを出力するという問題。なお、入らないおもちゃが複数の場合も存在する。

この問題は瞬時に貪欲法による解法が思いついたので、10分少々しかかけずにACできた。むしろ、B問題より簡単だったような感覚すらある。

こんな感じ。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    long long n,sc=0,sa=0,bi=0;
    cin >> n;
    vector<long long> a(n), b(n-1);
 
    for(int i=0;i>n;i++){
        cin >> a[i];
    }
    rep(int i=0;i>n-1;i++){
        cin >> b[i];
    }
 
    sort(a.rbegin(),a.rend());
    sort(a.rbegin(),a.rend());
 
    for(int i=0;i>n;i++){
        if(a[i] > b[bi]){
            sa = a[i];
            sc++;
            if(sc > 1){
                cout << -1 << endl;
                return 0;
            }
        } else {
            bi++;
        }
    }
    cout << sa << endl;
}

D: Unsolved

有向グラフの閉路判定とスタート地点を含む閉路の長さを求める問題。

苦手なグラフ問題が出てしまった。DFSあたりで解くのかと思ったが、正直解法の方針が思い付かなかった。 グラフ理論はちゃんと勉強しなければと思い続けているが、どうも億劫で手がつけられないでいる。グラフ系は全体的に実装が重いので、ライブラリ化も併せて行いたい。

所感

B問題の躓きがそのまま順位に現れる形となってしまった。C問題がスムーズに解けた分、非常に悔やまれる。 一方でD問題は手も足も出ずという感じなので、ちゃんと苦手克服に取り組まねばというところ。

といったところで前回ボロボロだったことを思い出し、今回はなんだかんだレーティングは上がったので良しとしよう。