2022-03-13

AtCoder Beginner Contest 243 参加記

AtCoder 競プロ ABC

2022/3/12に開催されたAtCoder Beginner Contest 243に参加しました。

直近のRatedコンテスト成績は絶賛6連敗中。ジリジリとレートが削られていく状況が続いており、競プロに対するモチベーションも下がりがちのため、そろそろこの悪い流れを断ち切りたいところ。

まずは、今回で連敗を阻止するぞという気持ちで臨むこととしました。

Rated参加します！7連敗を阻止するため、頑張ります✊✊
AtCoder Beginner Contest 243 - AtCoder https://t.co/fI1V91smgR
— devgenjin77 (@devgenjin77) 2022年3月12日

今回の結果

で、、、いままで3完続きだったABCでなんとか4完を確保することができましたとさ。

で、なんと今回は4完でも水色パフォーマンスが出てくれまして、なんとか連敗を阻止することに成功！レートの方も4桁に戻すことができましたとさ。

4完水パフォで、やっと連敗を阻止しました😂😂😂
来週も頑張ります✊
devgenjin77さんのAtCoder Beginner Contest 243での成績：1418位
パフォーマンス：1298相当
レーティング：992→1027 (+35) :)#AtCoder #ABC243 https://t.co/BiL9Uh1OGm
— devgenjin77 (@devgenjin77) 2022年3月12日

振り返り

D問題まではまずます好調でしたが、E以降がさっぱりでした。

A問題

A - Shampoo

もう少しうまいやり方もあるかと思いつつ、下手に効率化すると逆にドツボにハマりそうという懸念もあり、単純な解法で解くこととした。

$V$ から、 $A,B,C,A,B,C,...$ と引いていき、最終的に、答えがマイナスになった時の変数で場合分けして結果を出力すればよい。

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

4分27秒で1完。少しコーディングに時間がかかってしまっている印象です。

提出コード

https://atcoder.jp/contests/abc243/submissions/30029232

B問題

B - Hit and Blow

とりあえず、配列 $A$ の中身をすべてHashSetに突っ込んでみる。

その後、配列 $B$ の値を先頭から見ていき、

$A_i = B_i$ の場合、答え1に1追加
$A_i \ne B_i$ 且つ、 $B_i$ の値が、配列 $A$ の値を入れたHashSetの中に含まれている場合は答え2に1追加

以上の要領で実装し、問題なくACが取れましたとさ。

8分35秒で2完。ここまでは、まあまあのタイムという印象。

提出コード

https://atcoder.jp/contests/abc243/submissions/30034335

C問題

C - Collision 2

少しややこしめだが、解法を考えるのにはそんなに苦労しないという印象の問題。

入力に対して、平面上の位置、 $X,Y$ と歩く向きの方向(LかR)を持つオブジェクトを定義する。

その後、 $Y$ 座標の位置が同じ且つ、向きがRのオブジェクトの $X$ 座標が、向きがLのオブジェクトの $X$ 座標より小さいものが存在するかを判定する。

実装時、バグがありサンプルが通らずで苦戦するも、なんとか解決してACを取ることができました。

30分22秒で3完。もう少し早く通せたらなーという印象。

提出コード

https://atcoder.jp/contests/abc243/submissions/30049551

D問題

D - Moves on Binary Tree

この問題に関しては、早めに解法が浮かんだので助かった。

現在位置 $X$ に対して、二分木上の移動後の位置は以下の式で計算できる。

Uの場合、 $\lfloor X \div 2 \rfloor$
Lの場合、 $X \times 2$
Rの場合、 $(X \times 2) + 1$

で、これをまともに計算するとlong型の最大値を普通に超えてしまうので、2進数に変換した値を文字列として扱い、上記の計算を行うようにする。

すなわち、現在位置 $X$ を2進数の文字列表現に変換した $S$ に対して、

Uの場合、 $S$ の最後の文字を削除。
Lの場合、 $S$ に、0を追加。
Rの場合、 $S$ に、1を追加。

これを最後まで処理し、long型に戻した値を答えとすればOK。

なかなか早い時間でACを取ることができました。

38分59秒で4完。順位を確認すると、1200位前後ぐらいだったので、なんとか連敗は止まりそうというところで、少しほっとしました。

提出コード

https://atcoder.jp/contests/abc243/submissions/30054108

E問題

E - Edge Deletion

順位表のAC数から見て、やたらと難しそうな印象という問題。。

とりあえず、見覚えのありそうな解法から試してみる。

まず各辺より、コストの低い順に優先的に採用し、グラフを連結にするために必要な辺の数をすべての辺の数から引いた値が答えとする。が、、これはサンプルでWA。

それならばと、コストの高い方を優先にしてみたら、、と実装を変えてみるも通るわけなく、サンプルでWA。。

で、落ち着いて制約を見てみると、なんかワーシャルフロイド法を使えと言っている感じがするので、とりあえずワーシャルフロイド法を書いてみる。

その後、入力された各辺のコストより、最短経路のコストが小さいケースの数を答えとするという実装をしてみる。が、、これもサンプルが通らず。。。

で、いろいろ試行錯誤してみたものの、サンプルが通らずで結局時間切れということになりましたとさ。。

で、解説を見てみると、ワーシャルフロイド法を使うところまではあっていた模様。辺のコストが同一の回り道がある場合の考慮が必要だったようですなー。。

F問題

F - Lottery

コンテスト中、チラ見はしてみたものの何もわからず。

G問題

G - Sqrt

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

Ex問題

Ex - Builder Takahashi (Enhanced version)

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

これまでの実績

とりあえず、連敗を6で止めることができました。

総括

今回、パフォーマンス的には大分Eの難易度に救われた感じがします。

最近の負けパターンとしては、緑上位、もしくは水色下位当たりの問題が解けずで結局パフォーマンスが緑下位でとどまってしまうというのが多かったのですが、今回はDまでが少し早めに解けてくれて、水色パフォを維持したまま逃げ切りというような感じですね。

ということで、連敗は止まったものの、まだまだ楽観はできません。今できることは水色にふさわしい実力をつけるべく精進を重ねていくしかないというところでしょう。

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

2022-03-06

AtCoder Beginner Contest 242 参加記

AtCoder 競プロ ABC

2022/3/5に開催されたAtCoder Beginner Contest 242に参加しました。

atcoder.jp

ここ最近のRatedコンテストの成績は惨憺たるもので、現在5連敗中。レートの方も3桁落ち目前というところまで落ちてしまいました。。

ということで、なんとか今回こそ連敗を阻止するぞ、という気持ちで臨むこととしました。

Rated参加します。連敗を止めることと、3桁レート落ち回避のために、頑張ります✊

AtCoder Beginner Contest 242 - AtCoder https://t.co/ds3b0VxnpU
— devgenjin77 (@devgenjin77) 2022年3月5日

今回の結果

で、、、そんな思いも虚しく、今回も3完という結果となりました。。。

パフォーマンスは、またまた緑の下というところで、今回も下げ。結局、レートは3桁落ちになりましたとさ。

3完緑パフォで6連敗😭
レートも3桁落ち😭
また来週がんばります😭
devgenjin77さんのAtCoder Beginner Contest 242での成績：3009位
パフォーマンス：897相当
レーティング：1002→992 (-10) :(#AtCoder #ABC242 https://t.co/M7FITeARDo
— devgenjin77 (@devgenjin77) 2022年3月5日

振り返り

今回は、ジャッジのトラブルやこちら凡ミスもあり、なんかグダグダになってしまいました。

A問題

A - T-shirt

$X \le A$ の場合は必ずもらえるので、確率は1。

$X \gt B$ の場合はもらえないので、確率は0。

あとは上記以外の場合をどうするかというところですが、とりあえずそれっぽい計算をしてから提出。

で、、結果を確認しようとしたら、WJ...のまま一向に判定される気配がない。

明らかになにかおかしいと思いつつも、ツイッターとかみても何もアナウンスはなさそうなので、とりあえずB問題に進みました。

・・・・・

で、C問題を出そうとしたぐらいで、Aの提出がWAになってることに気づく。というか、そもそも出力すらしていないという凡ミス。。。

で、とりあえず標準出力に答えを出すようにして提出したら、これもWA。。。というか、確率の計算がめちゃくちゃだった。。。

で、確率計算を $\frac{C}{B - A}$ という形でちゃんと実装したらやっとこさACが取れましたとさ。

24分9秒の2ペナで3完。大分グダグダになってしまいました。。。

提出コード

https://atcoder.jp/contests/abc242/submissions/29881116

B問題

B - Minimize Ordering

文字列 $S$ 中の文字を昇順ソートして出力するだけの問題。

とりあえず実装して、サンプルまで通ったので提出。が、、待てど暮せど、ジャッジ待ちのまま。。。

とりあえず、結果はそっちのけでC問題に進みましたが、後で確認するとACでした。

8分4秒で1完だったようです。

提出コード

https://atcoder.jp/contests/abc242/submissions/29871536

C問題

C - 1111gal password

なんかDPを使う系の問題のような気がする。最近のABCのC問題はDPを出してくるのか。。

とりあえず、DP配列を作る。 $dp \lbrack i \rbrack \lbrack j \rbrack :=$ $i$ 桁目が $j$ であり問題の条件を満たす数のパターン数とする。

あとは、漸化式を適切に立てて計算するだけ。実装して提出みたら、あっさりとACが取れてくれましたとさ。

あとで解説で復習したら、だいたい同じことをやっていたので、妙に安心しました。

22分15秒で2完。で、ここでまだA問題が通ってないということに気づいてしまいました。。

提出コード

https://atcoder.jp/contests/abc242/submissions/29880123

D問題

D - ABC Transform

超絶ややこしそうな問題という印象のD問題。

解法を立ててみるまで、サンプルの文字列の遷移をメモ帳に起こしたりして法則性がないかをみるなどし、だいぶ長考しました。

で、思いついた内容としては以下の通り。

$t = 0$ の場合、答えは $S_k$ となる。
$k = 1$ の場合、答えは $S_1$ から $t$ 文字分進めた文字になる。
$k$ が偶数の場合、答えは $S^{t}$ の $k - 1$ 文字目から1文字分進めた文字になる。
$k$ が奇数の場合、 $S^{ (t - 1) }$ の $\lceil \frac{k}{2} \rceil$ 文字目から1文字分進めた文字になる。
$t$ と $k$ の制約がやたらと大きいが、 $S^{ (t - 1) }$ の状態を見る時に、 $k$ を2で割る計算が行われるため、最大でも60回程度の状態遷移を行えば答えに辿り着きそう。

ということで、なんとか実装に漕ぎつけようとしましたが、サンプルすら通せずで時間切れという結果になりましたとさ。。

で、悔しかったので、コンテスト終了後もなんとか解説を見ずに粘って実装したところ、なんとかコンテスト後だけどACがとれました。

https://atcoder.jp/contests/abc242/submissions/29905495

結局ノーヒントで解くことはできたけど、コンテスト時間内で解くのはまだまだ厳しいなーというところです。

E問題

E - (∀x∀)

問題をチラ見してみて、なんとか解けそうな見た目をしているという印象だったが、まずはD問題を解こうと思ったので今回は諦め。

また、自力で解いてみることにします。

F問題

F - Black and White Rooks

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

G問題

G - Range Pairing Query

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

Ex問題

Ex - Random Painting

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

これまでの実績

現状、6連敗中。。。レートも3桁に落ち、水色がどうとか言える状態ではなくなりつつあります。

総括

ここ最近は、難易度の高い問題を中心に精進を続けているのですが、コンテストでの結果が全く出ずという状態です。

普通なら、このへんで心が折れるというところかもしれませんが、あまり悲観的になっても仕方がありません。淡々と精進とコンテスト参加を継続していこうと思います。

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

2022-02-28

MC Digital プログラミングコンテスト2022 (AtCoder Heuristic Contest 008) 参加記

AtCoder 競プロ AHC 企業主催コンテスト

2022/2/12-2022/2/26に開催されたMC Digital プログラミングコンテスト2022 (AtCoder Heuristic Contest 008)に参加しました。

atcoder.jp

ヒューリスティック系のコンテストは、AHC001以降全く参加をしておらずだったのですが、最近ヒューリスティックのレーティング機能もちゃんと整備されたということらしいので、今回久々に参加をしてみることにしました。

まあ、とりあえず悪い成績でも落ちないレーティング制度らしいということと、なんか出しておけば一応プラスにはなるかなーという甘い気持ちで臨んでおります。

今回の結果

で、今回の結果ですが、「とりあえずは参加はしました」という結果しか残せませんでした。

パフォーマンスは、一応茶色上位ぐらい。元が灰色コーダーという状況だったので、レーティング的には一応大幅なプラスになりましたとさ。

devgenjin77さんのMC Digital プログラミングコンテスト2022（AtCoder Heuristic Contest 008）での成績：625位
パフォーマンス：781相当
レーティング：217→369 (+152) :)#AtCoder #MCDigitalプログラミングコンテスト2022（AtCoderHeuristicContest008） https://t.co/4hTE39TS6k
— devgenjin77 (@devgenjin77) 2022年2月27日

振り返り

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

A問題

A - Territory

今回の問題ですが、とりあえずプラスになる実装を行うというところから実装が重いという印象。とりあえず、考察らしきものをしてみるが、どうすればいいのか皆目見当が付きませんでした。

で、そんなこんなでコンテスト終盤まで差し掛かったものの、ほとんど何もできていない状態に。。

まあ、とりあえず何か提出を、ということで人間プレイヤーは300ターン何もしないという一番シンプルな出力を出すプログラムを出してみましたとさ。

で、順位表を見てると同点の人が結構沢山いるんですね(笑)

ということで、全ターン何もしないことで得られるスコアは、34322909点であるという事の知見を得ましたｗ

その後は、まともな実装がろくにできずに終了です。

最終提出コード

https://atcoder.jp/contests/ahc008/submissions/29634048

これまでの実績

レート的には結構な上昇。まあ今回は参加賞をいただいたようなものです。

総括

今回、ほぼ気まぐれで参加してみたヒューリスティックコンテストですが、ほぼ何もできずに終了という残念な結果に。

ただ、上位陣の実装などをみてると勉強になる部分も多々ありますので、また時間を見つけて一度この問題に取り組んでみたいと思います。また、次回以降のAHCはとりあえず参加はしていこうと思います。

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

2022-02-28

AtCoder Regular Contest 136 参加記

AtCoder 競プロ ARC

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

atcoder.jp

ここ最近レート上がってねーな。。とか思ってたら、いつの間にか直近のコンテストは4連敗という体たらく。

とりあえず今回は連敗を止めねばという気持ちで臨むこ事としました。

Rated参加します。とりあえず、なんとか連敗を止めたい😅

AtCoder Regular Contest 136 - AtCoder https://t.co/8qjcKZkc6s
— devgenjin77 (@devgenjin77) 2022年2月27日

今回の結果

で、今回も、なんと1完という体たらく。。競プロ難しすぎ。

パフォーマンスはギリギリ緑という所で、都合5連敗。4桁レートの維持も危うくなってきました。。

1完緑パフォで5連敗。。。。。
3桁レート落ちが見えてきたー😱😱
devgenjin77さんのAtCoder Regular Contest 136での成績：2037位
パフォーマンス：815相当
レーティング：1021→1002 (-19) :(#AtCoder #ARC136 https://t.co/fKwVsYT0FY
— devgenjin77 (@devgenjin77) 2022年2月27日

振り返り

Bで悪戦苦闘したものの、結局見当外れのことをやってたようです。

A問題

A - A ↔ BB

文字列 $S$ を先頭から見ていき、以下の要領で、答え用の文字列 $S^{\prime}$ に文字を追加する。

Aは辞書順最低なのでそのまま $S^{\prime}$ に追加する。
Cは変換不可なのでそのまま $S^{\prime}$ に追加する。
BAはBBB→ABと変換すると辞書順が小さくなる。変換後、Aを $S^{\prime}$ に追加する。
BBはAに変換して $S^{\prime}$ に追加する。

この要領で実装し、サンプルが通ったので提出したところ、問題なくACが取れましたとさ。

15分19秒というまあまあのタイムで1完。

提出コード

https://atcoder.jp/contests/arc136/submissions/29743239

B問題

B - Triple Shift

とりあえず、数列 $A$ と $B$ に現れる数字の種類と出現数が一致しない場合Noというのはわかるが、その後がわからない。

ただ、数字の移動自体は結構自由にできそうだという印象である。

よって、数列 $A$ を数列 $B$ の後ろ3要素より前の要素まで並びを同一にしてから、数列 $A$ の残りの3要素の並びで数列 $B$ の後ろ3要素が構成できるかという判定にしてみる。

ただし、実際に並び替えをシミュレーションするのは処理が大変でTLEになりそうなので、数列 $A$ を後ろから見て、数列 $B$ の後ろ3要素と同じ数字を並びを変えずに取得。そこから、 $B$ の後ろ3要素と同じ並びに変更できるかという判定で実装してみた。

で、これがサンプルまで通ったものの、WAを喰らう。。。

では、数列 $A$ を前から見ていく方針に変えたらどうかということで実装するも、これもWA。。

結局、時間切れまでWAが取り切れずということで終了となりましたとさ。

で、コンテスト後に解説を見ると、転倒数の性質を使うとのこと。そんな発想は全く無かったなー。。

C問題

C - Circular Addition

ワンチャンあるかと少し目を通してみたものの、何もわからずで諦め。

D問題

D - Without Carry

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

E問題

E - Non-coprime DAG

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

F問題

F - Flip Cells

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

これまでの実績

水色どころか、緑をキープできるかという事が当面の問題になってきそうです。

総括

今回のB問題は水色Diffだったようですが、これぐらいの難易度の問題がBにくると、良いパフォーマンスが出ませんねー。

この水色Diff辺りが攻略できていないという事が、最近のコンテストでじり貧になっている要因と思いますので、本腰入れて水色Diffあたりの問題の復習にとりくんでいきます。

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

2022-02-27

AtCoder Beginner Contest 241 (Sponsored by Panasonic) 参加記

AtCoder 競プロ ABC

2022/2/26に開催されたAtCoder Beginner Contest 241 (Sponsored by Panasonic) に参加しました。

atcoder.jp

実はこの日は飲み会などがあり、直前まで参加するかどうか迷ってたのですが、コンテスト開始の10分前に帰宅できたので、この際参加してみることにしました。

とりあえず毎度のことですが、レートが上げられるように頑張ろうという感じです。

飲み会後ですが、ギリギリ間に合ったのでRated参加します。とりあえずレート上げできるようにがんばります✊

AtCoder Beginner Contest 241（Sponsored by Panasonic） - AtCoder https://t.co/ZPRzBHwjoO
— devgenjin77 (@devgenjin77) 2022年2月26日

今回の結果

で、、今回のABCはなんと3完という体たらく。。うーん、まあ比較的Dが難し目だったかなー。

今回も緑下位ぐらいのパフォーマンスということで、都合4連敗目を喰らう羽目になりましたとさ。

3完緑パフォで4連敗目を喰らいました😭😭😭😭
明日頑張ります✊
devgenjin77さんのAtCoder Beginner Contest 241（Sponsored by Panasonic）での成績：2577位
パフォーマンス：983相当
レーティング：1026→1021 (-5) :(#AtCoder #ABC241（SponsoredbyPanasonic） https://t.co/gIaYr5ZXut
— devgenjin77 (@devgenjin77) 2022年2月26日

振り返り

D問題で完全に判断を誤ってしまいました。

A問題

A - Digit Machine

$k = 0$ を初期値として、 $k = a_k$ という処理を3回行った時の $k$ が答えとなる。

実装して、問題なくACを取ることが出来ました。

4分3秒で1完。

提出コード

https://atcoder.jp/contests/abc241/submissions/29664853

B問題

B - Pasta

配列 $A,B$ 双方を昇順ソートしておき、マッチング処理を行う。

配列 $B$ の要素が全てマッチする場合はYesと表示、それ以外はNoとする。

ちょっと、実装でもたついてしまい、時間は少しかかりましたが、こちらも問題なくACを取れました。

19分48秒で2完。

提出コード

https://atcoder.jp/contests/abc241/submissions/29677674

C問題

C - Connect 6

問題を一読すると、なんか五目並べならぬ、六目並べという感じがするこの問題。

全てのマスについて、右方向、下方向、右上方向、右下方向の連続6マスをチェックし、6マスの内4マス以上が黒く塗られていれば、あとは高々2つを塗ることで黒6つ以上の連続は可能となる。

あとは、範囲外の参照に気をつけながら実装すればOK。

ということで、少し実装に苦労したものの、あっさりとACが取れてくれましたとさ。

41分7秒で3完。ここぐらいで、2000位以内には行っていたので、もしかすると好成績いけるかという感触はありました。

提出コード

https://atcoder.jp/contests/abc241/submissions/29687610

D問題

D - Sequence Query

クエリを処理していく系の問題。愚直に実装するとTLEになるやつなので、なんらかの工夫は必要という感じだが、すぐにはわからん感じ。

とりあえず、ソート処理を全体で1回に抑えようという方針にしてみる。

数列 $A$ を、ペアオブジェクト( $x$ , 何回目のクエリで追加されたか)として配列で管理し、全てのクエリを先読みして数列に値を追加して1度昇順ソートする。その後、2と3のクエリを処理する際、二分探索で配列を探索する位置を決定し、何回目のクエリで追加された数字かを考慮しながら順に探索するという実装を行なってみた。

で、なんとかサンプルは通ったので、一度提出をしたみたところ、TLE、WA、REのトリプルパンチを食らってしまう。。

とりあえず色々見直してみるが、解決の糸口すら見えずで、このまま時間切れとなりましたとさ。

E問題

E - Putting Candies

ワンチャンあるかとチラ見をしてみるが、すぐにわかりそうにないため諦め。

F問題

F - Skate

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

G問題

G - Round Robin

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

Ex問題

Ex - Card Deck Score

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

これまでの実績

これで都合4連敗。。。。うーむ。。

総括

ここ最近のコンテストでは、なかなか思うような結果が出ず、壁にぶち当たっているような印象がしますが、ここを乗り越えてこそ自分の成長があるものと考えております。

今後も淡々と精進を行い、諦めずにコンテストの参加を継続していきます。

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

2022-02-22

AtCoder Beginner Contest 240 参加記

AtCoder 競プロ ABC

2022/2/20に開催されたAtCoder Beginner Contest 240に参加しました。

atcoder.jp

ここ2回のコンテストでは思うようなパフォーマンスが出せず、共にレート下げという結果を食らっています。今回はなんとか連敗を止めようという思いで臨むこととしました。

Rated参加します。直近のコンテストで2連敗中のため、連敗を止めるべく頑張ります✊
AtCoder Beginner Contest 240 - AtCoder https://t.co/KjtgehZE6I
— devgenjin77 (@devgenjin77) 2022年2月20日

今回の結果

で、、今回のABCも結果は4完となりました。。。

パフォーマンスはぎりぎり緑というところで、今回も大きな下げを喰らうこととなりましたとさ。

4完のギリギリ緑パフォで下げとなりました😭😭
来週取り戻せるようになんとか頑張ります！
devgenjin77さんのAtCoder Beginner Contest 240での成績：2820位
パフォーマンス：844相当
レーティング：1044→1026 (-18) :(#AtCoder #ABC240 https://t.co/64oym18IdK
— devgenjin77 (@devgenjin77) 2022年2月20日

振り返り

Aでつまづき、Cで遅れをとり、Eはまったくわからずでした。

A問題

A - Edge Checker

$b - a = 1$ だけが条件というわけではなく、 $b$ が10、 $a$ が1の時も考えないといけないなーという感じの問題。

そこでmodをとれば1つのシンプルな式に収まるのでは？という思いがふとよぎった。ということで、

$\left| (a \% 10) - (b \% 10) \right| = 1$ が成立すればYesという感じで実装して提出。うむ、非常にシンプルに収まった！

が、、これがあえなく1WAを喰らって撃沈しました。。というか、 $a = 9, b = 10$ の時に対応できてない。。

ということで、 $b = 10$ のときに、 $a = 1 or a = 9$ ならYesという雑な判定文を追加したりしてなんとかACを取ることが出来ましたとさ。

6分22秒の1ペナで1完。先が思いやられます。。

提出コード

https://atcoder.jp/contests/abc240/submissions/29513354

B問題

B - Count Distinct Integers

配列 $a$ の各数値を全てSetに突っ込んでサイズを出力するだけの問題。こちらは問題なくACを取れました。

8分48秒の1ペナで2完。多少遅れを取り戻しました。

提出コード

https://atcoder.jp/contests/abc240/submissions/29515769

C問題

C - Jumping Takahashi

一読してわからず。。全探索すると、最悪 $2^{100}$ のパターンを計算しないとなので、これはTLE間違いなし。

かといって、全部試す以外に解く方法など思いつかずということで、完全に手詰まりとなり、途方に暮れてしまいました。。

10分以上考えて良い考えが浮かばすなので、一旦D問題を解いてみることに。。

・・・

で、、なんとかD問題を解いた後にこの問題の制約を見直してみると、これナップサックDP問題やんということがわかった！

ということで、DP配列は、 $dp\lbrack i \rbrack\lbrack j \rbrack := j$ 回目のジャンプで、座標 $i$ にいる場合 $1$ とする。

遷移は、 $dp\lbrack i \rbrack\lbrack j - 1 \rbrack = 1$ の場合、 $dp\lbrack i +a_i \rbrack\lbrack j \rbrack = 1$ および $dp\lbrack i + b_i \rbrack\lbrack j \rbrack = 1$ とする。

最後に、 $dp\lbrack X \rbrack\lbrack N \rbrack = 1$ の場合、Yesと出力すればよいかと。

ということで、実装してみたら、あっさりとACが取れてくれましたとさ。

64分42秒の1ペナで4完。なんとか爆死を免れたかと。。

提出コード

https://atcoder.jp/contests/abc240/submissions/29536964

D問題

D - Strange Balls

一読して、スタックを使えば実装できるかな？と思ったが、普通に配列のみを使用してもなんとかなるかと予想。

とりあえず、筒の状態を管理する2次元配列を以下の内容で定義する。

$dp\lbrack i \rbrack\lbrack 0 \rbrack :=$ 現在筒の中の下から $i$ 番目にあるボールの種類
$dp\lbrack i \rbrack\lbrack 1 \rbrack :=$ $i$ 番目のボールは、何個連続している状態か

また $r$ を現在筒の中にあるボールの個数として定義する。あとは以下の要領で実装。

$r = r + 1$ とし、 $dp\lbrack r \rbrack \lbrack 0 \rbrack$ に $a_i$ をセットする。
$dp\lbrack r - 1 \rbrack \lbrack 0 \rbrack = a_i$ の場合、 $dp\lbrack r \rbrack \lbrack 1 \rbrack = dp\lbrack r - 1 \rbrack \lbrack 1 \rbrack + 1$ とする。
$dp\lbrack r - 1 \rbrack \lbrack 0 \rbrack \ne a_i$ の場合、 $dp\lbrack r \rbrack \lbrack 1 \rbrack = 1$ とする。
$dp\lbrack r \rbrack \lbrack 0 \rbrack = dp\lbrack r \rbrack \lbrack 1 \rbrack$ の場合、ボールを消す処理を行う。 $r = r - a_i$ とする。

以上の要領で、配列 $a$ の全要素について処理を行い、最後に $r$ の値を出せば終了。

少し不安もありましたが、なんとか一発でACを取ることが出来ました。

35分56秒の1ペナで3完。この後解けてなかったC問題と解いたりなどしました。

提出コード

https://atcoder.jp/contests/abc240/submissions/29528456

E問題

E - Ranges on Tree

昨日に引き続き、苦手なグラフ問題がEに登場。。。

さらに問題文を見てみましたが、あまり見慣れない集合に関する記号がふんだんに使われており、これがイマイチ何を言いたいのかよくわからない。。。

とりあえず、AC数は多そうなのでなんとかなるかと検討に取り組んでみましたが、とりあえず解法への糸口が見えない。なんだろう。。木DPとやらをするんだろうか。。。

ということで、木に関するDPについて調べたりなどしましたが、結局なにもわからずのままで時間切れという結果となりましたとさ。

F問題

F - Sum Sum Max

ワンチャンあるかとチラ見をしてみるも、何もわからずで諦め。

G問題

G - Teleporting Takahashi

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

Ex問題

Ex - Sequence of Substrings

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

これまでの実績

水色に向けての道のりも、また一歩後退する形となりました。

総括

今回の土日連続ABCコンテストはともに4完で連敗。苦手分野がE辺りにくると大分厳しいという印象です。

ただ、こういう苦手を克服していかないと上の色は目指せないことは明白なので、苦手意識をなくす為にもコツコツと復習に臨むしかないというところです。

だた、AHC008は一応登録しているので終了までに最悪提出だけはしておこうかと思ってるのでこれの対応も必要。うーん、リアルの業務より忙しい。。

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

2022-02-20

デンソークリエイトプログラミングコンテスト2022(AtCoder Beginner Contest 239)参加記

AtCoder 競プロ ABC 企業主催コンテスト

2022/2/19に開催された、デンソークリエイトプログラミングコンテスト2022(AtCoder Beginner Contest 239)に参加しました。

atcoder.jp

本来は先週行われるはずだったこのコンテストが本日に延期になったので、今週は土日連続でABCコンテストが行われることに。

ということで、今週は土日での連勝が目標。まずは土曜のこのコンテストでレート上げを目指ざそうという気持ちで臨むことにしました。

Rated参加します。今週土日がABCなので、連勝できるように、まずは今日頑張ります。
デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239） - AtCoder https://t.co/lGmfG7obKe
— devgenjin77 (@devgenjin77) 2022年2月19日

今回の結果

しかしながら、今回はあえなく4完止まりとなってしまいました。。

パフォーマンスは、緑の下位ぐらいしか出ておらず、結局今回は大きな下げを喰らうことになってしまいました。。

明日頑張ります😭😭
devgenjin77さんのデンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239）での成績：2594位
パフォーマンス：921相当
レーティング：1057→1044 (-13) :(#AtCoder #デンソークリエイトプログラミングコンテスト2022（ABC239） https://t.co/Xw9KCVZDRC
— devgenjin77 (@devgenjin77) 2022年2月19日