AtCoder Regular Contest 149 参加記

2022/10/2に開催されたAtCoder Regular Contest 149に参加しました。

atcoder.jp

昨日のABCでは、緑パフォで冷えという残念な結果でした。

今回のARCでは、気持ちを切り替えて、最近停滞気味のレートを一気に上げようということで、目標は高く3完を目指そうという気持ちで臨むこととしました。

今回の結果

早いうちに2完を達成できましたが、3完を達成することはできませんでした。

ARC149結果
ARC149結果

しかしながら、パフォーマンスは水色の中盤あたりまで出てくれまして、最近停滞気味のレートも大きく上昇させることが出来ました。

振り返り

C問題を解き切ることが出来ませんでした。

ARC149提出結果
ARC149提出結果

A問題

A - Repdigit Number

検討したところ、dpっぽくやれば解けるかもということで、以下のdpを考えてみる。

  • dp\lbrack i \rbrack \lbrack j \rbrack :=10進数でji個並べた数字をMで割った時の余り

  • 遷移は、 dp\lbrack i \rbrack \lbrack j \rbrack = ( ( 10 \times dp\lbrack i - 1 \rbrack \lbrack j \rbrack ) + j ) \% M

  • i, jの大きい順から見ていき、dp\lbrack i \rbrack \lbrack j \rbrack = 0となるi, jがあれば、ji個並べた値が答え。なければ-1

あとは実装して、一回でACを取る事ができました。

16分54秒で1完。この時点でAのACが900以上ぐらいだったので、少し出遅れた感あり。

提出コード

https://atcoder.jp/contests/arc149/submissions/35348563

B問題

B - Two LIS Sum

一読して、問題の意味は分かるものの、解法自体はすぐには思いつかず。。

とりあえず、考えた感じ、並び替えは何回でもできるので、数列A, BのどちらかのLISはNとして最大化できるはず。

ということは、A全体をソートした時のBのLIS + Nか、B全体をソートした時のAのLIS + Nの大きい方が答えになるような気がする。

思いつける解法がこれぐらいしかないという感じだったが、この解法で実装してみたところサンプルまでは通ったので提出。なんとか一発でACを取り切ることができました。

38分18秒で2完。エスパー解法が大当たりで助かりました(笑)

因みに、公式解説によれば、A全体をソートした時のBのLIS + Nだけでよかったようです。

提出コード

https://atcoder.jp/contests/arc149/submissions/35351153

C問題

C - Avoid Prime Sum

奇数+奇数や偶数+偶数の組は絶対に素数でないことから、この特性を上手く利用するのかなあと思ったが、上手い使い方が全く思いつかず。

とりあえず、全く解法が思いつかないので、苦し紛れの実装でなんとかならないか試してみる。

1N^2の数字をランダムソートしてキューに突っ込み。左上のマスから順番に値を決めてみて、隣接するマスの値との和が素数なら、キューから取り直してみるという、いわば運試しのような実装。

が、、N = 1000のケースを走らせてみると、てんで通らないので、適当に決めたらどうもダメみたいという知見だけを得て終了。

その後も、色々試行錯誤しましたが、結局解き切ることはできずで、時間切れとなりました。

コンテスト終了後、解説を見たところ、やはり冒頭の特性を使うのが正解だったようだが、使い方が全く思いつかなかったものでした。結局考察力が足りなかったということですな。

D問題

D - Simultaneous Sugoroku

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

E問題

E - Sliding Window Sort

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

F問題

F - Rational Number System

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

これまでの実績

大きくレートは上昇。水色への道を着々と進んでおります。

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

総括

今回は、エスパー解法が当たってくれたおかげで、大きなレート上昇を勝ち取りました。

しかし、これで満足していては、次回のARCで大負けをしかねないですな。

10月はARCが連続であるようなので、ここで大きくレートを上げられるように準備していきたいと思います。

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

京セラプログラミングコンテスト2022(AtCoder Beginner Contest 271)参加記

2022/10/1に開催された、京セラプログラミングコンテスト2022(AtCoder Beginner Contest 271)に参加しました。

atcoder.jp

ここ最近のコンテストでは、地味な結果が続いており、レートの方も停滞モードが続いております。

今回のコンテストでは、ここいらで大きくパフォーマンスを上げようということで、水パフォを目標として臨むこととしました。

今回の結果

3完で終了しました。。。

ABC271結果
ABC271結果

パフォーマンスは、4桁にすら到達せず。今回は完敗という結果になりましたとさ。

振り返り

C問題でハマってしまい、だいぶ時間をロスしました。

ABC271提出結果
ABC271提出結果

A問題

A - 484558

入力されたNを、丁度2桁の16進数で表示せよという問題。

出力フォーマットを使えれば簡単そうだったが、すぐには使い方が思い出せなかったので、とりあえず16進数の文字列で変換後、1桁だったら0を足すという実装をしました。

2分48秒で1完。

提出コード

https://atcoder.jp/contests/abc271/submissions/35272193

B問題

B - Maintain Multiple Sequences

あまりにもシンプルな問題だという印象だったが、公式解説によると二次元配列を使う練習問題であるとのこと。

とりあえず、N個のListオブジェクトを用意し、入力通りに値を追加。

クエリに対する答えでは、s番目のListオブジェクトのt番目を出力する実装をしました。

8分0秒で2完。

提出コード

https://atcoder.jp/contests/abc271/submissions/35277704

C問題

C - Manga

まず、入力されたaをソートして、キューに突っ込む。

次に、キューを前から参照した時に、1巻から順番にあるかどうかを見て、ない場合は配列の後ろにある2巻を売るという実装をしてみる。

が、提出したら、あえなくWA。。。。

どういうケースで上手く行かないかを考えるも、全く思いつかず。。

残り時間も半分以下になり、このままでは2完爆死しかねないので、仕方なくこの問題は撤退することにしました。

D問題

D - Stones

以下のDPを使って解いていく。

  • dp\lbrack i \rbrack \lbrack j \rbrack :=i番目のカードまでの裏表を決めた時に、合計がjになる時の配置方法の文字列

  • dp\lbrack i - 1 \rbrack \lbrack j \rbrack がNullでない場合、以下の遷移を行う

    • dp\lbrack i \rbrack \lbrack j + a_i \rbrack = dp\lbrack i - 1 \rbrack \lbrack j \rbrack + H (表向きの場合)

    • dp\lbrack i \rbrack \lbrack j + b_i \rbrack = dp\lbrack i - 1 \rbrack \lbrack j \rbrack + T (裏向きの場合)

  • dp\lbrack N \rbrack \lbrack S \rbrackがNullの場合はNo、そうでない場合はYes。

以上の実装でなんとかACを取り切りました。

71分45秒で3完。とりあえず、緑パフォぐらいは確保できそう。

提出コード

https://atcoder.jp/contests/abc271/submissions/35307731

E問題

E - Subsequence Path

cost\lbrack i \rbrack :=頂点1からiに到達する時の最小コストを管理する配列として定義。

あとは、配列Eを先頭から見て、E_i番目のパスを使った時に、上記の最小コストを更新できるかを計算していく。

と、ここまでの解法はなんとか思いつきましたが、いかんせん残り時間が少なくて、実装が終わる頃には、コンテスト終了ギリギリの時間。。

ローカルでサンプルが通れば提出するところでしたが、実装をバグらせてしまい、惜しいところで提出できず。結局時間切れ終了となりましたとさ。

F問題

F - XOR on Grid Path

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

G問題

G - Access Counter

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

Ex問題

Ex - General General

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

これまでの実績

停滞モード継続中です(笑)

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

総括

今回は、C問題で引っ掛かってしまい、あわや爆死するところでした。

課題としては、問題ではまってしまった時に次の問題に移る判断が遅かったところがあります。

また、Eの実装が間に合わなかったところも、少し入力部分の実装に時間がかかってしまったところが反省点。少し実装にかかるコーディング量を少なくするために、ライブラリを準備した方がいいかと。。

この点を反省して、また次に備えたいと思います。

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

トヨタ自動車プログラミングコンテスト2022(AtCoder Beginner Contest 270)参加記

2022/9/24に開催された、トヨタ自動車プログラミングコンテスト2022(AtCoder Beginner Contest 270)に参加しました。

atcoder.jp

前回のABCでは、なんとか連敗を止めることができたものの、増加幅は1桁程度という体たらく。ここ最近は大きくレートを上げることができておりません。

というわけで、今回はなんとか水パフォを突破して、レートを大きく上げていこうという気持ちで臨むこととしました。

今回の結果

で、今回はなんとか4完を確保するのが精一杯でした。。

ABC270結果
ABC270結果

パフォーマンスは、なんとかギリギリ水色に到達。レートは上がりましたが、上昇幅は1桁程度ということで、今回もパッとしない結果になりましたとさ。

まあ、負けるよりはだいぶマシですが。

振り返り

Dで方針を誤ってしまい、だいぶ時間をロスしました。

ABC270提出結果
ABC270提出結果

A問題

A - 1-2-4 Test

問題文の言っていることが、すぐには理解できなかったが、配点のパターンを見る限り2進数のビットを表現したもののように見える。

おそらく答えは、A,Bをなんらかのビット演算したものと推定。サンプルを試すと、OR演算で行ける模様。

あとは実装して、一発でACを取ることができましたとさ。

2分2秒で1完。

提出コード

https://atcoder.jp/contests/abc270/submissions/35092599

B問題

B - Hammer

数直線上の位置関係で分岐させる問題。工夫すれば、シンプルに実装する方法もありそうだが、とりあえず普通に分岐を実装してく方法とってみる。

Xが正の場合と負の場合、ハンマーが取れる場合と取れない場合、ハンマーが、ゴールと反対方向にある場合とそうでない場合という感じで愚直に実装。だいぶ時間が掛かりましたが、なんとか一度の提出でACが取れました。

10分30秒で2完。ちょっと遅めのタイムという印象。

提出コード

https://atcoder.jp/contests/abc270/submissions/35098743

C問題

C - Simple path

根付き木を、頂点XからDFSし、途中で通った頂点を記録していくと、頂点Yにたどり着いた時に、取っていた記録がそのまま答えとなる。

実装に少し手間取りながらも、一度の提出でACを取り切りました。

27分14秒で3完。

提出コード

https://atcoder.jp/contests/abc270/submissions/35109722

D問題

D - Stones

問題の見た目上、現時点で一番取れる最大の数を取り続ける戦略をとればいいような気がするが、制約の見た目上、そうでもないような気もする。。

とりあえず、最大を取り続ける方針で実装してみる。が、、これはあえなくWA。。。

最大を取り続ける戦略がダメということと、制約から、計算量がO(NK)になるDPをすれば良いのかと思ったが、DPの方針が思いつかず。

とりあえず、残り40分を切ったあたりで、この問題は一旦諦めました。

E問題

E - Apple Baskets on Circle

10分以上解法が思いつかずでしたが、あれこれ試行錯誤しているうちに、なんとか解法が降りて来てくれました。

K個食べるまでに、かごを何周できるかを二分探索で求め、最後に残った1周分に満たない余りを愚直に計算していけば解けそう。

ということで、あとは実装。当初、二分探索の下限を間違えてしまい、1週未満でK個食べ切ってしまうケースでWAを食らってしまいましたが、終了間際でなんとか修正。時間内にACを取り切ることができました。

97分46秒2ペナで4完。3完止まりだと爆死するところでしたが、なんとかギリギリ持ち堪えました(笑)

提出コード

https://atcoder.jp/contests/abc270/submissions/35135836

F問題

F - Transportation

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

G問題

G - Sequence in mod P

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

Ex問題

Ex - add 1

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

これまでの実績

前回に続いて、レートは微増。着実に水色への道を進んでおります(笑)

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

総括

今回は、あわや爆死という場面もありましたが、なんとか持ち堪えることができました。

特に、今回のE問題は水Diffだったようですが、本番でこのぐらいのDiffの問題を通せているのも、最近の地道な精進の成果がでているというところでしょうか。

逆に、D問題の貪欲にみせかけた引っかけにつまづいたのが反省点。もうすこしDPの過去問を解いていくことをしないとなあというところです。

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

UNICORNプログラミングコンテスト2022(AtCoder Beginner Contest 269)参加記

2022/9/17に開催された、UNICORNプログラミングコンテスト2022(AtCoder Beginner Contest 269)に参加しました。

atcoder.jp

参加前時点で、Ratedコンテスト3連敗中という状況でした。今回のコンテストは、この悪い流れを断ち切るべく、まずは連敗を止めようという気持ちで臨むこととしました。

今回の結果

今回は、なんとか5完という結果を残すことができましたとさ。

ABC269結果
ABC269結果

パフォーマンスは、水色にギリ届かずというところでしたが、なんとか現レートを上回りました。なんとか連敗脱出に成功です。

振り返り

Eに時間が掛かりすぎだった感があります。

ABC269提出結果
ABC269提出結果

A問題

A - Anyway Takahashi

簡単な計算問題と、固定文字列出力を行うだけのシンプルな問題。

やるだけの実装をして提出。問題なくACが取れました。

1分26秒で1完。

提出コード

https://atcoder.jp/contests/abc269/submissions/34919787

B問題

B - Rectangle Detection

グリッド上の四角形の四隅を求める問題。なんか、PaizaのCかBぐらいに出てきそうな感じ。

解法としては、グリッド上を2重ループで走査し、以下の要領で計算すればよい。

  • Aは#が出てくる行の最小値

  • Bは#が出てくる行の最大値

  • Cは#が出てくる列の最小値

  • Dは#が出てくる列の最大値

あとは、実装して、一度の提出でACが取れました。

8分7秒で2完。ここまでは、まあまあのタイムです。

提出コード

https://atcoder.jp/contests/abc269/submissions/34925918

C問題

C - Submask

Nを2進数で表した時、1となる位は15個以下との制約があるので、1となる位をbit全探索して、xを構築していけば良い。

あとは、実装して提出。問題なく一発でACが取れました。

20分13秒で3完。

提出コード

https://atcoder.jp/contests/abc269/submissions/34932002

D問題

D - Do use hexagon grid

連結成分の数を答えるということで、Union-Findを使う系の問題であることはわかった。

あとは、この大戦略のマップのような六角形のマップの連結を、どうやって判定するかで少々悩んでしまう。

しかし、よくよく考えると、四角形のグリッドを移動するときに使う4通りの移動方法をdx,dyの配列で実装するのと同じ要領で、6通りの移動方法を決めればよいということに気づく。

あとは、実装して提出。問題なくACが取れました。

32分48秒で4完。

提出コード

https://atcoder.jp/contests/abc269/submissions/34936553

E問題

E - Last Rook

忘れた頃にやってくる、インタラクティブ問題。

今回は、二次元グリッド上に配置されている、どのルークにもぶつからないようにルークを置ける点を見つけるという問題。

当初考えた解法は、二分探索の要領で解く方法。

まず、グリッドを縦に半分に切った領域の左側にあるコマの配置数を求め、半分に切ったどちらにルークが置ける余地があるかを求める。

次に、その領域を横に半分に切って、縦の場合と同じ要領で、半分に切ったどちらにルークが置ける余地があるかを求める。

が、これで実装して、自作のテストケースで色々試してみたが、どうしても正解に辿り着けていない。。

ここで大きな勘違いをしていたことに気づく。要は、シンプルに、縦に半分に切っていく二分探索を行うことで、新たに配置できるルークのjの位置を求め、次に横に半分に切っていく二分探索で、iの位置を求めるのが正解だった模様。

結局、最初の考察が大間違いだったが仇となり、大幅に時間をロスしたものの、最後はなんとか実装してACを取り切ることができました。

81分59秒で5完。この時点で、順位表を見ると、多分今回は負けはないかな?という位置でした。

提出コード

https://atcoder.jp/contests/abc269/submissions/34948569

F問題

F - Numbered Checker

残りが20分弱あるので、なんとか解けるかと問題を見ましたが、解法にたどり着けず。

ここで、時間切れとなりましたとさ。

G問題

G - Reversible Cards 2

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

Ex問題

Ex - Antichain

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

これまでの実績

ほんの僅かではありますが、これまでの負け分を少し取り戻しました。

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

総括

なんとか連敗を止めることはできましたが、E問題で大分もたついたのが、今回の反省点。とくに、最初の考察時点で破綻していたのを実装まで進めたのは大きな痛手でした。

やはり、考察が雑なので、まぐれで当たれば良い結果がでるものの、当たらなければ今回のように大幅に時間ロスをするという事態を引き起こしているような気がします。

考察の精度を高めていくのが、今後の大きな課題ですな。

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

AtCoder Regular Contest 148 参加記

2022/9/4に開催されたAtCoder Regular Contest 148に参加しました。

atcoder.jp

一時は、入水目前までレートを上げたものの、ここ2回のRatedコンテストで大敗し、レートは暴落。入水までの道のりは遠いものとなりました。

今回は、なんとかこの連敗を止めて、とりあえず、この悪い流れを断ち切ろうという気持ちで臨むこととしました。

今回の結果

終盤まで苦戦し、あわや0完爆死かというところを、なんとか滑り込みで2完達成という、いいのか悪いのかよくわからん結果でした。

ARC148結果
ARC148結果

パフォーマンスは、なんとか緑上位まで持ってきたものの、すこし勝ちに及ばずという結果。残念ながら連敗を止めることはできませんでしたが、爆死は免れたのでヨシかと。

振り返り

A問題で、ドはまりしてしまいました。

ARC148提出結果
ARC148提出結果

A問題

A - mod M

M=2とすると、余りの種類数は必ず2以下になるので、この問題は、余りの種類数を1にできるかという問題だということは分かった。

あとは、試すべきMの候補をどのくらい絞れるかというところ。

まずは、Aのうち最小の要素を素因数分解して、その素因数をMの候補にしてみる。が、これはサンプルすら通らずでNG。

この辺で、解法のアイデアがまったく出てこず、30分ほど悩んで時間を溶かしてしまう。。

仕方がないので、サンプル3の答えがどうなるかを愚直に計算してみた時、実はAの隣同士の差分が関係するのではないかと推察。

ということで、Aをソートして、隣同士の差分をとり、その差分の最小値を素因数分解すればなんとかなるかというところで組んでみると、なんとかサンプルが通る実装が完成。

が、、提出してみたらWA。。。

結局、1時間程度掛かったところで、一旦この問題は撤退。順位表上、そこそこ解かれているB問題に取り掛かることとしました。

ーーー

とりあえず、なんとかB問題を解き切りました。終了まで残り10分を切っている状態ですが、なんとかAも解けないかと悪あがきしてみる。

で、前半時点で試してなかった、以下の2処理を入れてみることに。

  • M=2で操作したときに、種類数が1なら、そこで答えを1として終了

  • Aの隣同士の差分をソートした時の最大値を素因数分解する。その素因数全部をMの候補として試す。

で、これがなんとか当たってくれたようで、終了1分前というギリギリのところで、ACを取り切ることができました。

118分32秒5ペナという、ボロボロの内容でしたが、なんとか2完を確保しました。

ちなみに、公式解説では、GCDを計算するというのが解法だということでしたが、本番中は、全く思いつきませんでした。

提出コード

https://atcoder.jp/contests/arc148/submissions/34801402

B問題

B - dp

LRを適切に決めて、1回の操作で辞書順最小の文字列にしましょうという問題。

まず、LSのうち一番左にあるpの位置というのは直感でわかった。

あとは、Rをどうするかというところだが、まずはSの中でもっともpが連続している部分列の右端じゃないかと推察。

そのような候補が2つ以上ならどうするかという問題もあるが、まずは候補のうち、最も左側のものをRということにしてみる。

で、これで出してみたら、WA。。。

仕方がないので、そのような候補全てについて、操作を試し、できた文字列の最小を求めるという方向でやってみる。

これが、もしかしてTLEするかと思ったが、なんとかその懸念は不要だったもよう。とりあえず、ACを取ることができました。

108分15秒1ペナという、酷いタイムですが、なんとか1完を確保。

因みに、公式解説では、Rは全探索でも行けるということでした。うーん、ムダなWAを取ってしまったのが少し悔やまれる。

提出コード

https://atcoder.jp/contests/arc148/submissions/34799682

C問題

C - Lights Out on Tree

順位表から見ると、ある程度のAC数があったので、ワンチャンあるかと問題文を確認してみましたが、何もわからず。。

D問題

D - mod M Game

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

E問題

E - ≥ K

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

F問題

F - 998244353 → 1000000007

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

これまでの実績

Rated3連敗となりました。非常にもどかしい展開です。

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

総括

今回は、連敗を止めるどころか、0完爆死を喰らいかねない展開でしたが、なんとかギリギリ耐えたというところでした。

しかし、ここ最近のARCでは、いい結果が出てないですな。やはり、ABCの過去問精進に偏っているのが原因かもしれません。

また、今回の結果を振り返って、次回に向けて精進していきたいと思います。

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

ユニークビジョンプログラミングコンテスト2022 夏(AtCoder Beginner Contest 268)参加記

2022/9/10に開催された、ユニークビジョンプログラミングコンテスト2022 夏(AtCoder Beginner Contest 268)に参加しました。

atcoder.jp

先週土曜のABCでは大きくレートを上げて、もう少しで水色到達というところまで来ることができましたが、日曜のARCで惨敗してしまい、水色への道は遠いものとなりました。

今回のABCでは、とりあえず日曜のARCの負け分を少しでも取り返そうという気持ちで臨むこととしました。

今回の結果

で、今回は、なんと3完で終了という体たらく。。

ABC268結果
ABC268結果

パフォーマンスは、なんとか緑を超えたところということで、先週日曜に続いてレートは暴落ということになりましたとさ。

振り返り

AとBは簡単すぎでしたが、C以降が難しすぎでした。

ABC268提出結果
ABC268提出結果

A問題

A - Five Integers

入力のA \sim EをSetに突っ込んで、サイズを出すだけの問題。

やるだけの実装をして提出。問題なくACが取れました。

1分27秒で1完。比較的早い方のタイム。

提出コード

https://atcoder.jp/contests/abc268/submissions/34726041

B問題

B - Prefix?

A問題に出てきそうなぐらい簡単な問題。サービス問題か?

Javaだと、文字列の接頭辞判定は、startsWithメソッドを使えば良いので、あとは実装するだけ。

問題なく、一度の提出でACが取れました。

2分46秒で2完。これまでの2完目のタイムで一番早いかも。

提出コード

https://atcoder.jp/contests/abc268/submissions/34728623

C問題

C - Chinese Restaurant

一読して、解法が全く思いつかず。。。B問題まで順調にきたはずが、この問題でだいぶ時間を浪費してしまうことに。

C問題を飛ばしてD問題以降をみてみるかと思ったが、順位表から見ると、後の問題もだいぶヤバそうな感じがするので、とりあえずC問題を解き切ろうと頑張ってみる。

悩んでいても仕方がないので、サンプル3の移動パターンの10ケースを全部計算してみて、答えになるものにどのような傾向があるのかを観ることにする。

すると、(N + p_i - i) \% Nの値でグループ化した時に、連続する3要素分の要素数の合計の最大が答えになるのではないかという予想が出てきた。

ということで、上記のとおり実装してみて提出。通るか不安でしたが、なんとか1回の提出でACを取り切ることができました。

49分59秒で3完。2完爆死があるかと思いましたが、なんとか回避することができました。

提出コード

https://atcoder.jp/contests/abc268/submissions/34746130

D問題

D - Unique Username

最初、問題文を読み解くのが大変だったが、雰囲気的には順列全探索をするやつだとわかった。

しかし単語間の"_"の数を調整して文字列を構築するのが、めちゃくちゃ実装が重くて、限られた時間内ではだいぶ厳しそう。

とりあえず、順列全探索のパートと、"_"の数を最大2個ぐらいまでつなげることができる突貫工事のようなプログラムを作ってみて提出してみるが、これはケースに蹴られてWA。

結局、実装が及ばずで、この時間で時間切れとなりました。

E問題

E - Chinese Restaurant (Three-Star Version)

問題はチラ見したものの、何もわからず。

F問題

F - Best Concatenation

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

G問題

G - Random Student ID

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

Ex問題

Ex - Taboo

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

これまでの実績

この2回の連敗で、だいぶレートを落としてしまいました。

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

総括

今回と前回のコンテストで、自分の実力不足を痛感することになりました。

とはいえ、これからやるべきことは、出来なかった部分を見直して、また次へと備えること。また、切り替えて次へ臨むこととします。

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

AtCoder Regular Contest 147 参加記

2022/9/4に開催されたAtCoder Regular Contest 147に参加しました。

atcoder.jp

土曜のABCでは水パフォを取って、レートの方は大幅に上昇。このARCで、高パフォーマンスが取れれば、一気に入水もあるかという位置に入ってきました。

とはいえ、前回のARCでは1完で冷えという結果でしたので、今回高パフォーマンスが取れるかどうかは微妙なところ。

とりあえず、今回はなんとかレートを上昇できるぐらいの結果が出ればという気持ちで臨むこととしました。

今回の結果

で、肝心の結果ですが、1完で終了という残念な結果に。。。

ARC147結果
ARC147結果

茶パフォを出すという結果になってしまい、レートは暴落。。目標としてた水色コーダーが、遠いものとなってしまいました。。。

振り返り

前回に続き、A問題で時間かけすぎだったかもしれません。

ARC147提出結果
ARC147提出結果

A問題

A - Max Mod Min

とりあえず、配列中で、最小の値と最大の値をとり続ければなんとかなるかという問題。

とはいえ、優先度付きキューを使うと、最大か最小しか取れないので、どうやって実装するかが難しいところ。

とりあえず、最大値の方を管理する優先度付きキューを使うことにし、最小値の方は一度だけ配列をソートしたのち取ってくることとする。

そして、配列の最大値を最小値で割った余りが0以外の場合は、余りの値を次に使う最小値とし、さきほど使った最小値の方は、キューに突っ込むこととする。

で、とりあえずサンプルまでは通ったので、出してみたら、WAがたくさん。。。

何がおかしいかよくわからんかったが、よくよく見ると、最初のソートが抜けていたというオチでした(笑)

ソートのステップを追加して提出すると、無事AC。今回のA問題もだいぶ苦戦してしまいました。

41分15秒2ペナで、やっと1完。

提出コード

https://atcoder.jp/contests/arc147/submissions/34610635

B問題

B - Swap to Sort

一つ跳びで入れ替える操作Bは何回でも使えるので、これは操作Bで転倒数をできるだけ減らしてから、操作Aを行うのがいいんじゃないかと考えてみた。

ということで、まずは、小さい数字から順に、操作Bを優先して揃えていき、どうしても操作Aが必要な場合になったら、そこで操作Aを使うという方針で行ってみることに。

で、出してみたら、これがまたWAだらけという結果。。

大きい順からソートしてみるとか、いろいろこねくり回してみたが、WAは一向に治らずで、ほとんどお手上げ状態。

最後の最後ぐらいに、実はこの問題、値の偶奇と位置の偶奇が結構関係するんじゃ無いか的な事が浮かんでは来たものの、あまりにもアイデアが出てくるのが遅すぎました。

結局、時間いっぱいまでもがいで解けず。

C問題

C - Min Diff Sum

順位表から見ると、ある程度のAC数があったので、ワンチャンあるかと問題文を確認してみましたが、何もわからず。。

D問題

D - Sets Scores

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

E問題

E - Examination

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

F問題

F - Again ABC String

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

これまでの実績

もう少しで水色というところまで来ていましたが、ここで痛いレート暴落。また地道に頑張らねば。。

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

総括

今回、水色直前というところで、大きなマイナスを喰らうこととなりましたが、これも自分の実力不足が原因かと。

また、今回の結果を振り返って、次回に向けて精進していきます。

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