AtCoder Regular Contest 141 参加記

2022/5/29に開催されたAtCoder Regular Contest 141に参加しました。

atcoder.jp

今回のA問題は400点だそうなので、場合によっては0完で終わるリスクもあるかと思いましたが、いちいちUnratedで参加するとか面倒なことはやりたくないので、今回もRated参加。とりあえず、A問題は突破するぞという意気込みで臨みました。

今回の結果

当初の目標通り、なんとか1完を達成することに成功しました。

ARC141結果
ARC141結果

で、肝心のパフォーマンスは、1完でも水パフォが出てくれて、なんとHighestも更新。結果としては上々という形になりました。

振り返り

B問題を1時間半かけて解き切ることが出来ませんでした。

ARC141提出結果
ARC141提出結果

A問題

A - Periodic Number

とりあえず、Nより1桁小さい全桁9の数字が「周期的な数」の候補となる。

あとは、Nの桁数の約数ごとに考える。Nの先頭から、約数の数分取り出した数字をmの候補とし、構築した「周期的な数」をNと比較し、答えの候補になるかを判定する。ここでNより大きかった場合は、mの下一桁を1ずつ減らして再度「周期的な数」を構築することを繰り返す。

多少実装が重くなりましたが、これでなんとかACを取りきる事ができました。

22分47秒で1完。とりあえず、0完は回避しました。

提出コード

https://atcoder.jp/contests/arc141/submissions/32084542

B問題

B - Increasing Prefix XOR

考察を開始してから30分程度は、二項係数で求めるのかとかあれこれ悩んでいました。。

だが、サンプルを元に考えてみると、隣同士のXORが増加していくということは、A_{i+1}を二進数で見たときの桁数がA_iの桁数より明らかに大きい事が条件ではないかと推察。

で、ここまで考察できれば、あとはdp\lbrack i \rbrack \lbrack j \rbrack :=i個目の要素が二進数でj桁となる通り数となるDP配列を立てて遷移を考えれば解けるはず。

が、、実装を進めてみるも、どうしてもサンプル3が合わず。。1時間弱悪戦苦闘しましたが、結局時間切れ終了となりました。。

後ほど解説を確認すると、考察の方向性自体は間違っていなかった模様。問題は実装力の不足ということで、まだまだ精進が足りないと痛感させられる結果となりました。

C問題

C - Bracket and Permutation

ワンチャンあるかと、問題文を確認するも何もわからず。

D問題

D - Non-divisible Set

問題すら見れておりません。

E問題

E - Sliding Edge on Torus

問題すら見れておりません。

F問題

F - Well-defined Abbreviation

問題すら見れておりません。

これまでの実績

今週の土日の連勝で、少しながらもHighestを更新。ここのところ停滞モードが続いてましたが、嬉しい結果となりました。

コンテスト実績
コンテスト実績

総括

今回は0完が回避できたものの、B問題が解き切れなかったのが悔やまれるところ。考察スピードも問題あるかというところですが、実装力もつけないといけないというのが今後の課題となります。

最近は、ABCや典型の過去問に取り組んでいることが多いですが、ARCの過去問も精進のメニューに入れていかないといけないなーというところです。

ということで、また次回も頑張ります。