AtCoder Regular Contest 143 参加記

2022/6/26に開催されたAtCoder Regular Contest 143に参加しました。

atcoder.jp

土曜のABCでは、体調が万全でなかったこともあってか、茶パフォを喰らい惨敗という結果に。

ということで日曜のARCでは、できるだけ昨日の負け分を取り戻そうという気持ちで臨むこととしました。

今回の結果

で、結果としては、1完を取るのがやっとでした。。

ARC143結果
ARC143結果

パフォーマンスは、緑の下位辺りということで、昨日に続いての連敗ということになりましたとさ。

振り返り

B問題は惜しいところまで行ってましたが、解き切ることができませんでした。

ARC143提出結果
ARC143提出結果

A問題

A - Three Integers

一読した時点では、よくわからなかったが、サンプルデータでの遷移を紙に書いてみるなどすると多少見通しが良くなった。

  • A = B = Cの場合は、計算不要。とりあえずAを答えとして良い。

  • A, B, Cを昇順にソートする。まず、CAに合わせるため、BCからC - A分を引く。

  • ここで、A = C \ge Bという関係になっている筈なので、A,CBに合わせるため、ACからA - B分を引く。

  • A = B = Cという関係になっている筈なので、最初に引いた数と、2回目に引いた数と、 Aを足した数が答えになる。

  • ただし計算途中で、A,B,Cいずれかがマイナスになる場合は、達成不可能とする。

あとは、実装とテストを入念に行い、なんとか一発でACを取る事ができました。

が、、順位表を見ると、15分程度で解いた割には、既に1000以上もACがでていたので、びっくり。大分簡単目の問題だったが少し時間を掛けすぎたのかもと思いました。

14分56秒で1完。

提出コード

https://atcoder.jp/contests/arc143/submissions/32773565

B問題

B - Counting Grids

これも、一読して何も思いつかず。まずは、問題の条件を満たす並べ方を考えてみるが、ある程度適当に並べても大体条件は満たしそう。。というか、どうすれば条件が満たせないかというところから考えてみることにする。

で、紙上に書いてみると、条件を満たさない並べ方としては、列で最も大きい数字がある行に、それ以上の数字を並べる方法という感じになり、問題の条件を満たせないマスは、高々1つしかなさそうという事が分かった。

ということで、条件を満たせないマスの数字がNからN^{2} - ( N - 1 )までのパターンが存在。

満たせないマスの数字をAとすると、同じ列に配置するAより小さい数字のパターン{}_{A - 1} P_{N - 1}と、同じ行に配置するAより大きい数のパターン{}_{N^{2} - A} P_{N - 1}を掛け合わせたパターン数に、マスをどの位置に配置するかというN^{2}のパターン数をかければ条件を満たさないパターン数が求まるはず。

あとは、全体のパターン数からさっき求めたパターン数を引けば答えになるかということで実装を進めてみたが、サンプル1は合うけど、他が全然合わない。

MODの計算が間違ってるかと色々試行錯誤してみるも分からずで詰み。

コンテスト後に、検討してみると、満たさないパターンについて、満たさないマスとその行と列のパターンは考慮していたが、それ以外のマスの配置パターンが全く漏れていたかと思われる。惜しいところまで考察できていたが、今回は残念ながら解き切ることが出来ませんでした。

C問題

C - Piles of Pebbles

少し考えてみたものの何もわからずで詰み。

D問題

D - Bridges

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

E問題

E - Reversi

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

F問題

F - Counting Subsets

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

これまでの実績

この土日でレートを大きく下げてしまう事になりましたとさ。

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

総括

今回のB問題は、考察の入り口までは来ていたものの、詰めが甘くて解き切れずでした。

上を目指すには、考察力も実装力も全然足りていない状態のようです。

とりあえず最近は、安直に解説ACを行わず、自力で考察することで、考察力をつけるように努力を重ねていこうという方針で過去問の勉強をしているのですが、まだまだ努力が足りない模様。来週に向けて今週の復習を進めていこうと思います。

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