ACL Beginner Contestに参加しました。ABCD4完1WA(31:24)で661位でした。パフォーマンスは1524でレートは1499→1501。

感想

 朝起きたらACL Contest2が消滅して代わりにABC級のACL Contestが生えていたので急遽参戦。レートはほとんど変わっていないが、収穫は大きかったので良し。

A - Repeat ACL

 流石にAからACLを使うということはないんだなと安心してAC。

B - Integer Preference

 またしても雑に提出してしまい1WA。以下のコード(WA)を見て察してください。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int main(){
    ll A,B,C,D;
    cin>>A>>B>>C>>D;
    if(B>=C){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
}

C -Connect Cities

 ようやくACLライブラリを使う場面が。といってもUnionFindは普段から定期的に出題されてますし、普段ならDで出すところをCで出すぐらいの違いでしょうか。自分のライブラリで問題なくAC。

D - Flat Subsequence

 ちょっとつまずきました。あれこれ考えながらDPだとどうだろうと思ったところで、区間操作が出てくることに気が付き、セグメント木の出番だ!となり、実装してAC。ちなみにこれも自分のライブラリでACしました・・・。

E - Replace Digits

 考察はDよりも簡単に感じましたが、実装がうまくできず解ききれませんでした。各桁が1~9だった場合のMODについて前処理を行い、LazySegmentTreeを用いた区間の更新と区間和(のMOD)を求めればいいことには早いことに気が付いたのですが、それをどのように実装できるのかが最後までわかりませんでした。これまでセグメント木を使う問題は、割と典型的な更新や値の取得であったため、出回っているライブラリを適用することで、解けましたが、いざ少し応用したパターンで出題されると、根本の理解を怠っていたために何もできなくなってしまいました。

F - Heights and Pairs

 問題見てないです。

反省

 Bの1ペナはもういい加減反省しろよといった感じですが、それはおいといてE問題が非常に教訓的でした。これまで解いてきた問題は、アルゴリズムやデータ構造の中身をちゃんと理解してなくても、使いどころとちょっとした使い方さえわかっていれば、解けてしまうことが多かったです。そのような中、いつか痛い目を見るだろうなと思いながら、一部のアルゴリズムについては不十分な理解のまま、とりあえず使えるという状態でこれまで取り組んできました。その痛い目というのがまさに今回で、きちんとその辺も理解しながら取り組んできた人とそうでなかった人との差が露骨に現れたかと思います。という点で、E問題はアルゴリズムコンテストらしい問題かつ教訓的であったため、良い問題だなと感じました。とりあえず中身の理解が不十分なアルゴリズムやデータ構造について、知識量を増やすことを意識しながら取り組もうと思います。