AtCoder ABC378 振り返り

November 3, 2024

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

スタートと同時にaccコマンドを叩いて、テンプレートとexampleをコピーしてこようとしたが、なぜか認証が切れていたらしく再ログインを求められてしまう。しかも、そこで入力をミスったらしく認証失敗して、その後何度叩いてもfetchに失敗するような状態になってしまい大変焦る。何か方法はないかと、試しにacc loginを叩いたらうまく行ったが、10分ほどの遅れをもってのスタートとなってしまった。

今日こそはD問題まで解きたいと思っていたが、結局C問題止まりで終わってしまった。
D問題が425の配点だったので、ちょっと難しかったとはいえ悔しい。３完は及第点かと思ったらレーティング−1された。

ABC378

コンテスト成績 >

A: Solved(1ペナ)

1~4のいずれかの数値を４つ受け取って、ペアになるものの数を答える問題。

前述の通り、スタートが遅れてしまったのもあってちょっと焦りながら解き始める。
１〜４が何回出現するかを数え上げて、それぞれの数値が２回出現しているかどうかを判定して終わり！と思ったら同じ数字が４回出現するパターンの考慮漏れ。
ケアレスミスにより、１ペナくらってしまった。

同じ数字４回ケースをケアしてAC。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int ans=0;
    vector<int> c(5,0);
    for(int i=0; i < 4; i++){
        int a;
        cin >> a;
        c[a]++;
    }
    for(int i=1; i < 5; i++){
        if(c[i] == 4){
            ans+=2;
        } else if(c[i] >= 2){
            ans++;
        }
    }
    cout << ans << endl;
}

B: Solved

与えられたゴミ出し日程に応じて、それぞれ出したゴミが何日目に回収されるかという問題。

問題文が非常にややこしく書いてあって、理解するのに小一時間かかる。ちゃんと読んで見れば何ということはなく、単なるあまりの計算をするだけの問題。あまり計算の場合わけが若干面倒ではあったが、特に問題なくACできた。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n,nq;
    cin >> n;
    
    vector<int> q(n),r(n);
    for(int i=1; i < n; i++){
        cin >> q[i] >> r[i];
    }
    
    cin >> nq;
    for(int i=1; i < nq; i++){
        int t,d;
        cin >> t >> d;
        
        if(d % q[t-1] > r[t-1]){
            cout << q[t-1] - ((d % q[t-1]) - r[t-1]) + d << endl;
        } else {
            cout << r[t-1] - (d % q[t-1]) + d << endl;
        }
    }
}

C: Solved

与えられた数列の各要素に対して同じ数列の直前に同じ数値があれば、そのインデックスで入れ替えて、なければ-1で入れ替えていくというような問題。

単純に各要素に対して、それ以前に同じ値が出現するかを調べられればいいのだけれど、愚直にやると計算量が問題になってしまう。そこでunordered_mapを使って探索時間を短縮した。 unordered_mapは使ったことがなかったので、ちょっと調べながらの実装だったが、使い方自体はmapをそんなに変わらないのでさほど詰まることもなくACできた。

多分、というか絶対にmapでもACできたと思うので、unordered_mapを使ったことでどれだけ計算時間が短縮されたのかはわからないが、とりあえず使ってみてよかった。たぶん。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    unordered_map<int, int> m;
    
    for(int i=1; i < n; i++){
        int a;
        cin >> a;
        if(i != 0){
            cout << " ";
        }
        if(m.find(a) != m.end()){
            cout << m.at(a);
            m.erase(a);
        } else {
            cout << -1;
        }
        m.insert(make_pair(a,i+1));
    }
    cout << endl;
}

D: Unsolved

与えられた盤面に対して、経路長がkとなる経路の数がいくつあるかを数える問題。
フィールドだからシミュレーションかと思ったが、よく考えたらグラフ問題だった。

小一時間考えたが、どうしても解法が思いつかずE問題にチャレンジすることにしてしまった。
グラフに苦手意識があるので、予習して臨んだ割にはグラフ問題であえなく撃沈してしまった...

E: Unsolved

数列の各要素の部分列の和に対してあまりを求めて、さらにその和を求める問題。(自分で書いててよくわからない。)

数学的な問題かと思い、あまり計算についてちょっと調べてみて、どうやらあまりの和の公式に基づいて、連続する部分列の和の総和の問題になることまでは辿り着けた。
しかし、肝心の「連続する部分列の和の総和」の求め方がどうしてもわからず、どうやら累積和を用いて解けそうというところで手詰まり。

正解は、そこからさらにフェニック木(Fenwick tree)を使って解くというものだったが、フェニック木については全く存じ上げない。
解答をみるとフェニック木はACLにもあるらしいので、今度勉強してみようと思う。

所感

初っ端からaccが動かないトラブルに見舞われて、だいぶあたふたしてしまい、そのまま１ペナくらう羽目になってしまった。
逆にBC問題はハマりどころもなく割とスムーズに解けたのでよかった。300点のC問題については、この頃はコンスタントに解けているので、そこは成長しているような気がしている。一方で、D問題については予習してきたものの、やはり今週も手が出ず仕舞いだった。

レーティングの方も-1と微妙に下がってしまった。おそらく、開始直後のトラブルとA問題の1ペナがなければプラスに転じていたのかもしれないと思うと悔やまれる。とはいえ、目指すはもっと上なの早くD問題解けるところを達成したい。

michihiko-yamamoto Blog