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

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

atcoder.jp

ここ数回のABCコンテストでは5完達成が続き、レートの方もいい感じで上がってきております。目標としていた水色にもだいぶ近づいてきました。

今回のコンテストは、とりあえず水パフォを目指し、さらに水色コーダーに近づこうという気持ちで臨むこととしました。

今回の結果

前回に続いて、5完を確保することに成功しました!

ABC267結果
ABC267結果

パフォーマンスは、水色の真ん中ぐらいまで出て、レートは大幅に上昇。水色コーダーに、さらに一歩近づくことができました!

振り返り

E問題をなんとか解き切ることができました。

ABC267提出結果
ABC267提出結果

A問題

A - Saturday

IF文を5通り書くだけの問題。

問題文からのコピペが面倒だが、やるだけの実装をして提出。問題なくACが取れました。

1分41秒で1完。まあまあの時間という印象。

提出コード

https://atcoder.jp/contests/abc267/submissions/34531429

B問題

B - Split?

だいぶ実装がめんどくさそうな問題。なんらかの法則性を見つけて簡潔に実装できるかとおもったが思いつかずだったので、ゴリ押しの実装で挑むことにしました。

まず、問題文の通り、ピンが立っているかどうかを保持する配列を作成する。

つぎに、この配列を左から見て、ピンが立っている→ピンが立っていない→ピンが立っているというパターンが存在するかを判定すればOK。

実装時間がやたらとかかってしまい、判定部分にバグが無いか大分心配でしたが、なんとか一度の提出でACが取れました。

11分52秒で2完。少し手こずった感があるタイム。

提出コード

https://atcoder.jp/contests/abc267/submissions/34540034

C問題

C - Index × A(Continuous ver.)

一読して、累積和を使えば解けるかという問題。

まず、A_1からA_Mまでの連続部分列について、答えを計算する。

つぎに、連続部分列を、右に一つずらして答えを計算する時に、前の答えから、A_1からA_Mまでの累積和を引いて、M \times A_{M + 1}を足すという工夫をすることで、計算量を減らすことができる。

あとは、連続部分列が右端に到達するまで同様の要領で計算していけば良い。

ということで、あとは実装して、なんとか1回の提出でACを取り切ることができました。

24分30秒で3完。ここまでは、まあまあの内容です。

提出コード

https://atcoder.jp/contests/abc267/submissions/34547219

D問題

D - Index × A(Not Continuous ver.)

C問題とは違い、今度は連続で無くても良いパターンの問題。制約などをみると、これはDPするやつだと直感でわかった。

  • dp\lbrack i \rbrack \lbrack j \rbrack := Ai個目まで見て、Bj個採用した時の最大値。

  • 遷移は、dp\lbrack i \rbrack \lbrack j \rbrack = max(dp\lbrack i - 1 \rbrack \lbrack j - 1 \rbrack + (j \times A\lbrack i \rbrack ), dp\lbrack i - 1 \rbrack \lbrack j \rbrack)

当初、初期値の設定に不具合があり、サンプルがなかなか通らなかったのですが、なんとか実装を完了し、1回の提出でACを取り切ることが出来ました。

42分27秒で4完。とりあえず、5完は行けそうなペースです。

提出コード

https://atcoder.jp/contests/abc267/submissions/34556310

E問題

E - Erasing Vertices 2

現在可能な操作のうち、一番コストが低い操作を貪欲に実行し続け、最終的に一番高かったコストが何だったかを答える問題かというところかと。

ということで、まずは、各頂点とそれを削除するためにかかるコストを前もって計算しておき、コストの昇順で管理する優先度付きキューに突っ込んで、先頭から処理していけばよい。

ということで、現状可能な操作のうち、一番コストの低い順から削除し、さらに、削除する操作を行なった頂点に隣接する頂点が既に削除されている場合は、そのコストも計算に入れてコストの最大値を計算するという感じで組んでみる。

で、なんとかサンプルが通る実装ができたものの、提出したらWAを大量に食らってしまう。。。

なにがダメなのかよくわからなかったが、とりあえず頂点を削除したときに、隣接する頂点を削除するコストを新たに計算し直してからキューに突っ込むような実装にしてみる。

すると、多少実行時間がかかったものの、なんとかACを取り切ることが出来ましたとさ。

83分46秒2ペナで5完。ちなみに、公式解説では二分探索が想定だったようですが、その筋は全く考えられておりませんでした。

提出コード

https://atcoder.jp/contests/abc264/submissions/34019512

F問題

F - Exactly K Steps

一応、15分以上残り時間がありましたので、問題は読んでみたものの何もわからず。

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

G問題

G - Increasing K Times

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

Ex問題

Ex - Odd Sum

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

これまでの実績

念願の水色コーダーに、あと少しで手が届くというところまで伸びてきました。

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

総括

ここ数回は、非常に調子が良く、レートの方も上昇傾向が続いています。

念願の水色まであと少し。とりあえず、日曜はARCがあるので、ここで入水できるように頑張るだけです。

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

AtCoder Beginner Contest 266 参加記

2022/8/27に開催されたAtCoder Beginner Contest 266に参加しました。

atcoder.jp

前回のABCでは、青パフォが出るという上々の結果でレートを大幅に上げることに成功しました。

今回のABCでは、前回の勢いを落とさない様に、まずはレート以上のパフォーマンスを出そうという気持ちで臨むこととしました。

今回の結果

前回に続いて、5完を達成しました!

ABC266結果
ABC266結果

水パフォを叩き出すことに成功し、前回に続いてレートはHighestを更新!さらに水色コーダーに近づくことが出来ました!!

振り返り

C問題で大きく手こずったことが反省点です。

ABC266提出結果
ABC266提出結果

A問題

A - Middle Letter

文字列Sの長さをTとした時、0-indexedで、 \lfloor \frac{T}{2} \rfloor文字目を出せば良い。

ということで、実装して1回の提出で問題なくACが取れました。

1分47秒で1完。

提出コード

https://atcoder.jp/contests/abc266/submissions/34369403

B問題

B - Modulo Number

普通に、N mod 998244353を計算すれば良いというのであれば簡単だが、そうはいかないと思われる。

とりあえず、上記の要領で計算してみると、やはりNがマイナスの時に計算が合わない。

ということで、マイナスの場合は、998244353を足してみることで帳尻を合わせる実装をすることに。

これでなんか嫌なケースがあったら困るなあという気持ちで提出しましたが、なんとか無事ACを取ることができました。

9分2秒で2完。

提出コード

https://atcoder.jp/contests/abc266/submissions/34376842

C問題

C - Convex Quadrilateral

苦手意識のある、二次元上の角度を求めるような問題。

解法を検討してみるものの、角度計算の方法をさっぱり忘れており、時間を溶かしてしまう。。

とりあえず10分ほど経ったところで、いったんこの問題からは撤退。D問題以降に着手することにしました。

ーーー

で、D、Eと解いたところで戻ってきたC問題。とりあえず、平面上の3点間の角度を計算する方法をググればなんとかなるかというところで、調査を開始。

すると、外積を計算すればよいとかなんとか説明している、いい感じの計算できるコードを見つけたので、とりあえずコピペで自分のコードに実装。

あとは、A→B→C、B→C→D、C→D→A、D→A→Bのそれぞれ4パターンで3点間の角度を計算し、判定することでなんとかACを取り切ることが出来ました。

88分58秒で5完。自身の知識不足のせいで、やたらと時間がかかったのですが、なんとか5完を確保することができました!

提出コード

https://atcoder.jp/contests/abc266/submissions/34401948

D問題

D - Snuke Panic (1D)

多分、DPすればいい的な問題。ということで、以下のDPを構築してみる。

  • dp\lbrack i \rbrack \lbrack j \rbrack := 時刻iの時点で、地点jにいる時に得ることができる最大の得点。

  • 遷移は、dp\lbrack i \rbrack \lbrack j \rbrack = max(dp\lbrack i - 1 \rbrack \lbrack j - 1 \rbrack, dp\lbrack i - 1 \rbrack \lbrack j \rbrack, dp\lbrack i - 1\rbrack \lbrack j + 1 \rbrack) と計算し、その時点で、すぬけ君を捕まえることができるならば、得点をプラスする。

と、こんな感じで実装したら、サンプルの1部が合わず。。

調べてみると、時刻0の時点で地点0にいる前提を考慮しないとダメということみたい。

ということで、DPの初期値を、dp\lbrack 0 \rbrack \lbrack 0 \rbrack = 1と最初に1点とっていることとし、遷移の処理で、得点が0のケースを無視して、最後に1点引くという小細工をすることで対処してみる。

とこんな感じでサンプルが通る実装を作り、提出したら、なんとかACをとることができましたとさ。

39分31秒で3完。とりあえず、C問題を抜かしても大怪我はしなさそうな感じです。

提出コード

https://atcoder.jp/contests/abc266/submissions/34389206

E問題

E - Throwing the Die

数回前のABCにスゴロクのDPをするような問題があり、それを復習している時に、期待値の計算とかを勉強してたので、多少とっかかりやすかった問題。

とりあえず、立てた方針としては、この問題の答えをf(N)とした時、N回目に出た目がf(N - 1)より大きい場合、ゲームを終了させ、そうで無い場合は期待値f(N - 1)が取れるものとして計算することに。

で、結果サンプルが無事通る実装ができたので提出したら、一発でACを取ることが出来ましたとさ。

58分51秒で4完。これでなんとか緑パフォ上位は行けそうかという印象でした。

提出コード

https://atcoder.jp/contests/abc266/submissions/34394869

F問題

F - Well-defined Path Queries on a Namori

一応問題文を見て、検討したものの、いい感じの解法は思いつかず。

とりあえず、10分ほど程度経過したところで、この問題を諦め。

多少は順位が上がるだろうということで、C問題に取り組むことにしました。

G問題

G - Yet Another RGB Sequence

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

Ex問題

Ex - Snuke Panic (2D)

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

これまでの実績

前回につづいて、レートは大きく上昇。水色コーダーへ、また一歩近づくことが出来ました。

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

総括

今回は、C問題で苦戦したものの、なんとか優先順を決めて対応したことで、最低限の結果が確保できたのが良かったかと思います。

今後のABCでは、水色パフォ以上の結果を出し続けることを目標とし、青Diff以下の問題までは過去問の精進に取り組むという感じで進めていこうと思います。

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

AtCoder Beginner Contest 265 参加記

2022/8/21に開催されたAtCoder Beginner Contest 265に参加しました。

atcoder.jp

土曜のARCでは、思う様な結果が出ず、レートを減らしてしまうことに。

ということで、今回のABCでは、なんとか土曜の負けを取り戻せる様に、水パフォあたりは出してみようという気持ちで臨むこととしました。

今回の結果

で、今回は久々の5完達成という、嬉しい結果に!

ABC265結果
ABC265結果

そして、なんとABCでは自身初の3桁順位を達成!ギリギリ青パフォを達成するという出来過ぎの結果で、レートはHighestを大きく更新しました!!

振り返り

今回は、大きなミス無く終えることができて、良かったです。

ABC265提出結果
ABC265提出結果

A問題

A - Apple

N個のりんごを全部X円ずつで買ったときの金額と、Y円で3個を買えるだけ買って、残りを1個当たりX円で買った時の金額を比較する。

1回の提出で問題なくACが取れました。

2分45秒で1完。

提出コード

https://atcoder.jp/contests/abc265/submissions/34201202

B問題

B - Explore

問題文のとおりシミュレーションするだけの問題。

残り時間と消費時間がイコールの場合、移動できないという条件に少し違和感を持ちましたが、ちゃんとサンプルを確認して間違いが無い様に実装し、提出1回でACが取れました。

12分50秒で2完。

提出コード

https://atcoder.jp/contests/abc265/submissions/34210566

C問題

C - Belt Conveyor

少し実装が面倒だが、グリッド上の移動をシミュレーションするだけ。

ループを考慮して、一度移動したマスを管理するようにする。

こちらも、問題なくACを取ることができました。

22分56秒で3完。

提出コード

https://atcoder.jp/contests/abc265/submissions/34217888

D問題

D - Iroha and Haiku (New ABC Edition)

まず、数列Aの累積和を求めておき、尺取り法の要領で、合計がP + Q + Rとなる区間があるかを求める。

次に、該当する区間が見つかったら、この区間の左端からの合計がP、およびP + Qになる区間があるかを、それぞれ二分探索で求める。

これらの条件が全て満たせたら、答えがYesとなる。

実装はやたらと手こずりましたが、なんとか提出一回でACを取ることができました。

45分45秒で4完。

提出コード

https://atcoder.jp/contests/abc265/submissions/34228845

E問題

E - Warp

残りが50分以上というところで、なんとか5完を達成したいところだが、最初に問題を読んだ限りでは上手い解法は思いつかず。

グラフ的な考え方が必要なのか、それとも包除原理的な解き方が必要なのかと色々検討したものの、イマイチぱっとしない。

で、時間をかけて思いついたのが、Nの最大が300というところで、計算量O( N^3 )ぐらいのDPは行けそうという考えから、

  • dp\lbrack n \rbrack \lbrack a \rbrack \lbrack b \rbrack := 合計n回ワープしたうち、1つ目のワープをa回、2つ目のワープをb回した時の通り数。

こんなDPができるのでは無いかと想定。

各ワープの回数が分かれば、どの座標に移動するかが高速に求まり、障害がある座標への移動であれば通り数をゼロとする。

そうでなければ、3種類のワープのうち、どれを増やしたかを考慮した遷移を実装すればよい。

で、これで本当に通るかが少し不安でしたが、なんとか頑張って実装を終え、サンプルまで通ったので提出。なんと1回でACを取り切ることが出来ました!

90分48秒で5完。これぐらいの難易度のDPを本番中に解き切ったのは初めてです!

提出コード

https://atcoder.jp/contests/abc265/submissions/34242845

F問題

F - Manhattan Cafe

残り時間が10分弱ありましたので、一応問題文を見てみましたが、何も思いつかず。

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

G問題

G - 012 Inversion

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

Ex問題

Ex - No-capture Lance Game

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

これまでの実績

青パフォゲットで、Highestを大きく更新。水色コーダーへ一歩近づくことが出来ました。

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

総括

今回のE問題が解けたのは素直に嬉しいです。

今回の結果が単なるまぐれ当たりで終わってしまわないように、今後も安定して水パフォ以上の結果をだせるように精進を重ねていこうと思います。

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

AtCoder Regular Contest 146 参加記

2022/8/20に開催されたAtCoder Regular Contest 146に参加しました。

atcoder.jp

今回のARCは、Aが300点、Bが500点ということで、見た目上は2完は厳しいかなという印象でしたが、逆に言えば2完取れればでかいということで、まずは2完を目標として臨むこととしました。

今回の結果

結局、1完で終了でした。まあ、0完よりはましかと。。

ARC146結果
ARC146結果

1完ということで、A問題の解答時間でパフォーマンスが大きく左右されるところでしたが、なんとか緑の真ん中ぐらいは取れたようで、なんとか小さい怪我で済みました。

振り返り

A問題は、少し時間かけ過ぎだったかもしれません。

ARC146提出結果
ARC146提出結果

A問題

A - Three Cards

一読して、考察したところ、数列Aをソートして、大きい方からみていけばいいのかなあ、という気がしてくるが、なんだかワナがひそんでいるような気がする。

とりあえず、ソートして、値が大きい3つの桁数を見れば、作るべき数字の桁数が導けるので、あとはその桁数が作れるパターンを全探索かということも考えたが、それだと全部が同じ桁のときにTLEになりそうな気がする。。

と、あれこれ考察するうちに、結局、値が大きい3つの数字を使って、並び替えのパターンを全て試せばよいということに気づいたのが、大体開始から20分後ぐらいのこと。

とりあえず、実装して提出。なんとか、一回でACを取ることが出来ました。

22分31秒で1完。この時点でA問題のACが1000以上付いており、今回もA問題でやたらと時間を使いすぎたと気づきました。。

提出コード

https://atcoder.jp/contests/arc146/submissions/34168605

B問題

B - Plus and AND

一読して、何も分からず。

かなり、時間をかけて考察したところの印象としては、1増やす操作を繰り返すことで、上位の桁のビットを立てることができるかを計算し続けるのかなあという感じ。

が、考察としてはここまできたが、実装の方がまったくうまくいかずで頓挫してしまい、このまま時間切れとなりました。

あとで解説をみると、大体の方針は合っていたようですが、細部が詰めきれずでした。

C問題

C - Even XOR

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

D問題

D - >=<

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

E問題

E - Simple Speed

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

F問題

F - Simple Solitaire

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

これまでの実績

前回ABCではHighest更新もしましたが、今回は下げてしまいました。まだまだ停滞モードは続きます。

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

総括

今回は、B問題が解けなかったのも問題でしたが、A問題に時間かけ過ぎなのも問題かと。

ARCには少し苦手意識もあるので、慎重に対応した結果がこれなのですが、次回以降はある程度スピードも重視してみようかと思います。

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

RECRUIT 日本橋ハーフマラソン 2022夏(AtCoder Heuristic Contest 013)参加記

2022/8/9-2022/8/16に開催されたRECRUIT 日本橋ハーフマラソン 2022夏(AtCoder Heuristic Contest 013)に参加しました。

atcoder.jp

前回のAHC012は参加せずでしたが、今回はせっかくなので、提出ぐらいはしてみるかという気持ちで参加登録することにしました。

とりあえず、レートは下がることはないということで、まずは正の得点を取ることが目標でした。

今回の結果

「とりあえずは提出はしました」という結果しか残せておりません。

AHC013結果
AHC013結果

そして、今回は茶パフォという結果。まあ、出しただけというところなので致し方なし。それでもレーティングは上がっちゃいました。

振り返り

本当に、とりあえず出しただけという結果です。

AHC013提出結果
AHC013提出結果

A問題

A - Server Room

実は、今回の問題の検討と実装に着手したのは、コンテスト最終日の16日。。

それまでは、参加登録はしてましたが、ABCの過去問解きばかりやっていたので、完全に未着手。最終日になって、慌てて実装し出すという始末でした。

で、読んでみると、グリッド上にある、数種類のコンピュータを動かしながら、ケーブルで繋げていこうという問題とのこと。

とりあえず考えたのは、初期配置から繋げられるところを繋げてみて、ケーブルの近傍にあるコンピュータを1マス移動させることで連結できるなら繋げてみようという方針。

が、、残り少ない時間内で、そんな複雑な実装ができるわけもなく、結局やったのは、移動なしで、初期位置から繋げられるコンピュータをつなげてみるという実装。

こんな実装でも、やってみるとかなり難しく、結局3時間程度かかってしまいました。

最終提出コード

https://atcoder.jp/contests/ahc013/submissions/34095165

これまでの実績

今回は、レーティングを下回るパフォしか出ませんでしたが、参加賞として少しのレートをいただきました。

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

総括

今回は、さすがにサボり過ぎだなあと反省。

今回のような、ほどほどの実装しかできない様では、入緑すら怪しいようなので、次回コンテストではまともな実装ができるようにヒューリスティック関係の精進にも力をいれていきたいと思います。

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

AtCoder Grand Contest 058 参加記

2022/8/14に開催されたAtCoder Grand Contest 058に参加しました。

atcoder.jp

5月のAGCは、Unrated参加で1完。この時に、次のAGCまでには入水してRatedで参加するぞという目標を立てていたのですが、レートの停滞が続き、結局今回のAGCも緑コーダーとして参加することに。

とりあえず、次回参加のための練習と捉えて、まずは1完を目標に臨むこととしました。

今回の結果

なんとか1完は達成することができました。

AGC058結果
AGC058結果

今回はUnratedなので、パフォは出ませんでしたが、大体水色の後半ぐらいは出ていた様です。

振り返り

A問題はなんとかクリアしましたが、そのあとはさっぱりでした。。

AGC058提出結果
AGC058提出結果

A問題

A - Make it Zigzag

順列Pを前から見ていって、条件が合わないなら交換するという方法で済めば話は早いが、そうはいかなさそう。

ということで、ノートに順列のパターンを色々書いてみて考察してみると、いいアイデアが思い浮かんだ。

  • 先ず、P_{2i} \gt  P_{2i+1}の条件を成立させるため、数列Pより、左記の条件に合わない場合Swap操作を行う。
  • 次に、P_{2i-1} \lt  P_{2i}の条件を成立させるため、数列Pより、左記の条件に合わない場合Swap操作を行う。

完全な証明はできてないながらも、なんとなくそれっぽい解法なので、とりあえず実装してみて提出。

これが一度WAを喰らうも、単なる実装ミスだったので、再度修正後提出。なんとか無事ACを取ることが出来ましたとさ。

35分37秒1ペナで1完。エスパー解法でも、なんとかACが取れてよかったです。

ただ、コンテスト後でも、なぜ前から見て単純にSwapしたらダメだったのかは、よくわかってません。後々研究しておこうかと思います。

提出コード

https://atcoder.jp/contests/agc058/submissions/34047069

B問題

B - Adjacent Chmax

一応、90分ほどかけて考察をしてみましたが、糸口が掴めずでした。

11時をはるか過ぎたところで、諦め。

C問題

C - Planar Tree

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

D問題

D - Yet Another ABC String

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

E問題

E - Nearer Permutation

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

F問題

F - Authentic Tree DP

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

これまでの実績

UnRatedなのでレート変化はありません。

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

総括

今回もUnratedでの参加となったAGCですが、なんとか1完確保ができたのはよかったかと。

次回のAGCはいつになるかわかりませんが、次こそはRated参加できるように、今後も精進に励んでまいります。

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

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

2022/8/13に開催された、freee プログラミングコンテスト2022(AtCoder Beginner Contest 264)に参加しました。

atcoder.jp

ここ最近のコンテストでは、なんとかレート以上のパフォーマンスが出せているものの、小ミスが多くてパフォーマンスを下げるという展開が続いています。

今回こそは、その辺りの反省を踏まえて、最低水パフォといういつもの目標で臨むこととしました。

今回の結果

で、今回はABDEの4完という、なんとも微妙な結果で終了しました。

ABC264結果
ABC264結果

それでも、パフォーマンスは、なんとか水色まで出てくれまして、なんとかレート上昇。一応Highest更新のおまけ付きでの勝ちという結果になりました。

振り返り

C問題での、しょうもないミスで大きく時間をロスしてしまいました。

ABC264提出結果
ABC264提出結果

A問題

A - "atcoder".substr()

簡単な文字列操作の問題。JavaではStringクラスのsubstringメソッドを使えば良い。

ということで、あとはやるだけの実装をして提出。問題なくACが取れました。

1分19秒で1完。ここ数回のABCでは早い方のタイムでした。

提出コード

https://atcoder.jp/contests/abc264/submissions/33985009

B問題

B - Nice Grid

問題を見て、なんらかの法則性がないかを考えてみたが、すぐには思いつかず。。

仕方ないので、ゴリ押しでACを取るため、15 \times 15のグリッドの情報を文字列で直書きする方針で実装。

実装時間がやたらとかかってしまい、また直書き部分のところにミスが無いか大分心配でしたが、なんとか一度の提出でACが取れました。

9分5秒で2完。コンテスト後のTLを見てると、結構ゴリ押し実装でやった人が多かったようですね(笑)

提出コード

https://atcoder.jp/contests/abc264/submissions/33992390

C問題

C - Matrix Reducing

一読して、Cにしては、やたらと難しい問題かと思ったが、制約などを見て、削除する行と列のパターンを全探索するやつだという印象を持った。

ということで、bit全探索の要領で実装。なんとかサンプルまでは通すことが出来たので、提出したら、これがREとWAのダブルパンチ。。。

そこから、WAはともかくREの原因がさっぱり分からず。ローカルでいろんなパターンをテストしてみるものの、原因の手がかりすら掴めずで、時間がどんどん溶けていくばかり。。

都合2回目の提出でWAを喰らったところで、この問題は一度撤退して、後のD以降に賭けてみることにしました。

で、結局この問題は最後まで解けずでしたが、あとでよくよくソースを見てみると、ループのところで致命的なバグがあったことが判明!

また、つまらないミスでパフォーマンスを下げたというオチでした。うーん、ミスが治らないねえ。。

D問題

D - "redocta".swap(i,i+1)

これ、転倒数を求めるやつだと瞬時にわかった。

転倒数を求めるライブラリなどは、まだ用意していなかったが、要素数も少ないので、単純計算で求めることは可能。

ということで、あとは愚直に転倒数を求める実装をして提出。サクッとACが取れましたとさ。

Cで手こずったこともありましたが、B、C問題より軽く解けたので、少し拍子抜けしました。

55分47秒で3完。あとは、E問題に賭けてみるのみ。

提出コード

https://atcoder.jp/contests/abc264/submissions/34009948

E問題

E - Blackout 2

一読した印象として、Union-Findを使って連結判定するのと、クエリを逆から見ていき、電線を繋げたときに電気の通る街の増加数を数えれば良いかという感じ。

実装方針としては、各連結成分ごとの街の数と発電所の数を個別にカウントして、発電所と同じ連結成分に存在する街の数だけをカウントしていくというやり方で進めました。

で、30分ほどかけてサンプルが通る実装ができて、提出。一度WAを喰らってしまうものの、なんとかバグってるところを見つけて、終了3分前という危ういところで、なんとかACを取り切ることが出来ました。

96分16秒1ペナで4完。これが取れるのと取れないのとでは、パフォーマンス的に大分違ってた筈なので、なんとか助かりました。

ちなみに、今回の私の実装方針は、公式解説とほぼ同じ考え方でした。他の解説であった、全ての発電所を同じ頂点と見做すやり方のほうが実装は軽かったようですが。。

提出コード

https://atcoder.jp/contests/abc264/submissions/34019512

F問題

F - Monochromatic Path

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

G問題

G - String Fair

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

Ex問題

Ex - Perfect Binary Tree

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

これまでの実績

一応、Highestを更新することが出来ました。

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

総括

今回は、なんとか水パフォを確保できましたが、しょうもないミスをするクセ自体は全然治らずというところで、この辺を治すのが長期的な課題のように思えます。

ここ最近は、ABCの過去問を解き直すという練習を続けていますが、バーチャル参加などして、コンテスト本番の状況で練習を重ねるのも一案かもしれません。

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