2023-12-11

estie プログラミングコンテスト2023(AtCoder Regular Contest 169)参加記

2023/12/9に開催された、estie プログラミングコンテスト2023(AtCoder Regular Contest 169)に参加しました。

今年は１年中ARCに苦しめられるという感じになっており、なんとか苦手意識を克服したいところ。

今回はA問題から400点ということで、０完爆死がチラつくところですが、まずは１完以上を目指して行きます。

Rated参加します。０完爆死しないことが目標です。

estie プログラミングコンテスト2023 （AtCoder Regular Contest 169） - AtCoder https://t.co/5TRRrUQfzg
— devgenjin77 (@devgenjin77) 2023年12月9日

今回の結果

なんとか１完を確保することができましたとさ。

水パフォ行けるかどうかは怪しいなあという印象でしたが、なんとか水パフォに届いてくれたようで、レートは回復。これで参加した甲斐があったというものです。

１完確保で、なんとか勝ちました😃
devgenjin77さんのestie プログラミングコンテスト2023 （AtCoder Regular Contest 169）での成績：1523位
パフォーマンス：1275相当
レーティング：1126→1142 (+16) :)#AtCoder #estieプログラミングコンテスト2023（ARC169） https://t.co/pIQAXGKVI2
— devgenjin77 (@devgenjin77) 2023年12月9日

振り返り

粘りに粘って、なんとかA問題を通し切ったという内容です。

A問題

A - Please Sign

当初は何もわからずだったので、とりあえず貪欲を書いて推移を眺めて見るもさらにわからず。。

とりあえずサンプルに対して処理をした時に、各項がどのように解に影響してくるかの推移を書いてみたら、処理中に全く更新されない項の正負が影響してくるような気がするという感じ。

どうも、配列 $P$ を $P \lbrack i \rbrack$ が $i$ の親となる根付き木として考えたときに、葉になる要素を見ていく感じか、、しかし葉が $0$ の場合とか、正負が混在するときにどう判断するかが悩ましい。

あれこれ悩んでる内に時間が無くなってきた。とりあえず確信は無いが、根付き木の深さが同じ要素を合算した時の正負が最終結果に影響するような気がするし、合算した結果が０の場合は一つ上の深さの要素を合算するという感じだろうということで実装。

すると、これが大当たりだったか、なんとか提出１発でACが取れました。変なコーナーケースなど無いかヒヤヒヤものでしたが、通ってくれて良かったです。94分0秒で1完。

提出コード

https://atcoder.jp/contests/arc169/submissions/48321147

B問題

B - Subsegments with Small Sums

それなりにAC数のある問題でしたが、何もわからず。ここで時間切れになりました。

C問題

C - Not So Consecutive

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

D問題

D - Add to Make a Permutation

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

E問題

E - Avoid Boring Matches

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

F問題

F - Large DP Table

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

これまでの実績

下落傾向が続いていたレートですが、なんとか少し持ち直しました。

総括

今年のARC結果を振り返ってみると、参加は17回に対して、結果は3勝13敗1分。レート増減を合算したら、 $-466$ ということで、今年はARCで大分痛い目に遭ってたようです。

とりあえずこの体たらくでは、来年も入青はおろか、緑落ちを繰り返す結果になりそうな感じ。来年は、ARCで平均２完ぐらいはできるようになりたいです。

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

2023-12-03

大和証券プログラミングコンテスト2023(AtCoder Beginner Contest 331)参加記

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

2023/12/2に開催された、大和証券プログラミングコンテスト2023(AtCoder Beginner Contest 331)に参加しました。

atcoder.jp

最近、精進不足がたたっているのか、ABCでも全く良い結果が出ずで、レートの方は、緑の上の方で停滞している状況です。

とりあえず、再入水は早く達成したいところ。今回も水パフォ目標で挑みます。

Rated参加します。
最近、不本意な結果が続いてますが、再入水に向けて今回も水パフォ目指します✊

大和証券プログラミングコンテスト2023（AtCoder Beginner Contest 331） - AtCoder https://t.co/CQySnOie5h
— devgenjin77 (@devgenjin77) 2023年12月2日

今回の結果

なんと、今回は３完で終了という残念な結果になりました。。

結局、今回は緑パフォで、レートを上げることすらできずという結果で終了です。

３完緑パフォで冷え😭😭
devgenjin77さんの大和証券プログラミングコンテスト2023（AtCoder Beginner Contest 331）での成績：3231位
パフォーマンス：902相当
レーティング：1148→1126 (-22) :(#AtCoder #大和証券プログラミングコンテスト2023（ABC331） https://t.co/RedcoowMcY
— devgenjin77 (@devgenjin77) 2023年12月2日

振り返り

Dで、しこたまハマってしまい、Eにかける時間が無くなってしまいました。。

A問題

A - Tomorrow

なんか、IF文をこねくり回して解く問題という感じ。

実装後、サンプルで検証してたらバグらせているのに気づいてしまい、実装し直すなど、A問題にしてはやたらと時間がかかってしまいました。

なんとか実装をこなしてAC。5分22秒で1完です。

提出コード

https://atcoder.jp/contests/abc331/submissions/48102537

B問題

B - Buy One Carton of Milk

DPまでは要らんかなという感じでしたが、DPぐらいしか解法が浮かばず。

$dp \lbrack i \rbrack :=$ 卵を丁度 $i$ 個買う時の最小金額という形で定義し、あとは上限に余裕を持って、卵 $200$ 個ぐらいまでのケースを計算。

あとは $N$ 個以上買う時の最小金額を出すという感じの実装でACが取れましたとさ。

12分16秒で2完。

提出コード

https://atcoder.jp/contests/abc331/submissions/48110010

C問題

C - Sum of Numbers Greater Than Me

制約が $A_i \le 10^{6}$ とあることから、 $max(A_i)$ のサイズの配列が定義できるという感じである。

$Ans \lbrack i \rbrack :=$ $A$ の要素の内 $i$ 以上の値の和、という配列を累積和を用いて計算すれば、あとは $A$ の各要素について、配列を参照すれば答えが出せる筈。

ということで、上記の要領で実装して、なんとかACが取れましたとさ。20分50秒で3完。

提出コード

https://atcoder.jp/contests/abc331/submissions/48115887

D問題

D - Tile Pattern

めっちゃややこしそうな問題だが、 $(0, 0)$ を左上隅とし、任意の $(x, y)$ を右下隅とする長方形に含まれる黒マスの個数を $O(1)$ で求めることができれば、各クエリに対して答えを計算することができそうという感じ。

あとは、上記の計算をどうするかがキモなのだが、なんとか頑張って実装してみてサンプルまで通すことはできた。

が、、これを提出してみたら、WAという結果に。。。

WAの原因を考えてみるも、結局わからずじまいで、この問題は仕方なく諦めることにしました。

E問題

E - Set Meal

残り２０分程度の段階で臨んだこの問題。

問題を見てみると、禁止される組み合わせの個数が、最大 $10^{5}$ 程度であるということから、 $NM$ 個のペアのうち、金額の大きいもの $10^{5} + 1$ 個が列挙できれば、答えが出るかなという感じ。

しかしながら、着手が遅かったこともあり、実装が追いつかずで時間切れとなりました。。

F問題

F - Palindrome Query

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

G問題

G - Collect Them All

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

これまでの実績

連敗続きで、レート1100台の維持すら怪しくなってきました。。

総括

最近、BやC問題の難易度を上げてきてる傾向にあるように思えます。この影響で、少し調子が狂わされているかもしれません。

とはいえ、最近の低迷は、明らかに精進不足に因るものが大きいと思ってます。最近仕事が多忙なことで、なかなか精進時間が確保できないということもありますが、直近のコンテストの振り返りぐらいは毎週こなして、最低限、実力を維持できるように頑張っていこうと思います。

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

2023-11-26

トヨタシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 330)参加記

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

2023/11/25に開催された、トヨタシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 330)に参加しました。

atcoder.jp

ここのところ、土曜に予定が固まってしまい、２週連続で土曜のABCには参加できてなかったのですが、今週はなんとか９時ギリで帰宅できたので参加することにしました。

なんとか、早いとこ再入水を達成すべく、今回も水パフォ目標で挑みます。

３週ぶりのABCRated参加します。
年内に再入水させるため、水パフォ目標で頑張ります✊

トヨタシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 330) - AtCoder https://t.co/09vur0cc3m
— devgenjin77 (@devgenjin77) 2023年11月25日

今回の結果

なんとか５完確保したものの、時間かかり過ぎ＋ペナ喰らい過ぎの影響で、順位は伸びませんでした。

結局、今回は緑パフォで、レートを上げることすらできずという結果で終了です。

５完緑パフォでした😩😩
devgenjin77さんのトヨタシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 330)での成績：2306位
パフォーマンス：1064相当
レーティング：1157→1148 (-9) :(#AtCoder #トヨタシステムズプログラミングコンテスト2023(ABC330) https://t.co/qXeZSEruWI
— devgenjin77 (@devgenjin77) 2023年11月25日

振り返り

BとCで大分手間取ってしまい、ペナを喰らいまくるなど、非常に残念な内容でした。

A問題

A - Counting Passes

これは、見たまんまというか、配列 $A$ をfor文で回して、 $L$ 以上が何個あるかをカウントするだけ。

やるだけの実装でAC。0分54秒で1完です。

提出コード

https://atcoder.jp/contests/abc330/submissions/47889963

B問題

B - Minimize Abs 1

問題文を一読しても、要領がよくわからん問題でした。

とりあえず、紙に書いて整理してみたり、サンプルから推測するなりした結果、多分 $|L - A_i| \lt |R - A_i|$ なら $L$ が答えで、それ以外なら $R$ が答えかな？という感じで出してみたらWA。。

次に、サンプルに $L \lt A_i \lt R$ のケースが無い事に気づき、結局 $L \lt A_i \lt R$ なら $A_i$ が答えで、あとは $A_i \le L$ なら $L$ 、 $R \le A_i$ なら $R$ が答えかという感じで出したら、ACが取れましたとさ。

いつものB問題と雰囲気が違いので、やたら苦労しました。21分55秒1ペナで2完。

提出コード

https://atcoder.jp/contests/abc330/submissions/47910320

C問題

C - Minimize Abs 2

ここ最近のC問題に比べると難易度が高目というか、D問題で出てきてもおかしくないレベル感の問題という印象。

とりあえず、 $x$ を $\sqrt{D}$ ぐらいまで試して、 $y$ を二分探索で求める感じでいいだろうという感じで提出しましたが、何故か大量のWAが出てしまう。。。

色々いじってみても、WAが取りきれず。残り１時間を切ったぐらいで、とりあえず、この問題をスキップする事にしました。

E問題を終えたところで、解けそうな問題がCぐらいしか無く。。とりあえず、１から見直してみることに。

すると、当初何を勘違いしてたか、 $D$ の上限が実際は $2 \times 10^{12}$ だったところ、 $1 \times 10^{12}$ と誤解してた事で、2乗を前計算してたり、forの上限を決めてたところで色々おかしくなってた事に気づきました。。

また、挙げ句の果てに、非負整数は $0$ を含まないと勘違いしてたこともWAの原因に。。

結局、上記の勘違いを修正して実装したところ、なんとかACが取れましたとさ。

結局、C問題では5ペナも喰らってしまい、この時点では、87分37秒7ペナで5完となりました。

提出コード

https://atcoder.jp/contests/abc330/submissions/47937560

D問題

D - Counting Ls

2つのoが縦に並ぶラインと、横に並ぶラインの交点にあるoを基準に考えると、すんなりと解けるかという印象。

各列、各行に存在するoの数を前計算しておき、あとは、oである $(i,j)$ について、（行 $i$ のoの個数 $-1$ ） $\times$ （列 $j$ のoの個数 $-1$ ）の値を合計していけば解けるかと。

という事で、実装してみたら問題なくACが取れましたとさ。46分8秒1ペナで3完。

提出コード

https://atcoder.jp/contests/abc330/submissions/47922901

E問題

E - Mex and Update

Dを解いたあと、Cを少しいじったがWAが取れんので、E問題に進んでみる。

考察すると、求めるべきMexの上限は $N$ になるので、それ以上の数字については管理をしなくて良さそう。

という事で、TreeSetを使って、 $0$ 以上 $N$ 以下の数字のうち、 $A$ に存在しない整数を適切に管理できれば、TreeSetの最小値がMexになるはず。

で、一旦実装してみたら、管理する上限を間違えたか、１回WAを喰らったものの、修正してACが取れましたとさ。

この時点で、65分59秒2ペナで4完です。

提出コード

https://atcoder.jp/contests/abc330/submissions/47930405

F問題

F - Minimize Bounding Square

ワンチャン、これがACできれば大逆転で再入水まで持ってけるかというところだったが、解けず。。

問題の見た目上、正方形の一辺の長さで二分探索という感じでしたが、実装まで持ってくことはできませんでした。

G問題

G - Inversion Squared

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

これまでの実績

さらに入水が遠のく結果になりました。。

総括

今回は、BとCで大分調子を狂わされてしまいました。特にCは自分の不注意でペナを重ねているだけに反省しきりという感じです。

とりあえず、今年もあと一ヶ月と少しとなりましたが、現状１年前のHighestよりレートが下回っている状況。１年経って、進歩も無しというのは少し寂しい感じがするので、なんとか年内に再入水を果たしたいところです。次回のABCは、水パフォ以上取れるように、準備していこうと思います。

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

2023-11-21

ALGO ARTIS プログラミングコンテスト2023 秋(AtCoder Regular Contest 168)参加記

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

2023/11/19に開催された、ALGO ARTIS プログラミングコンテスト2023 秋(AtCoder Regular Contest 168)に参加しました。

atcoder.jp

所用で２週連続ABCを不参加にしておりましたが、直近コンテストでは緑落ちを喰らっている身分だけに、さっさと水色に戻しておきたいところ。

今年は１年通じてARCで苦い記憶しか無いところですが、なんとか再入水を狙えるところまで行ければという感じで挑んでみました。

Rated参加します。
２完以上で再入水行けるか、という感じだと思う。

ALGO ARTIS プログラミングコンテスト2023 秋（AtCoder Regular Contest 168） - AtCoder https://t.co/G7BX6tbAaq
— devgenjin77 (@devgenjin77) 2023年11月19日

今回の結果

目標の２完には届かずでした。

で、前回参加したABCに続いて茶パフォを喰らってしまい、レートは暴落。再入水がさらに遠のく結果になりましたとさ。

１完茶パフォでした😭😭😭
devgenjin77さんのALGO ARTIS プログラミングコンテスト2023 秋（AtCoder Regular Contest 168）での成績：1758位
パフォーマンス：702相当
レーティング：1198→1157 (-41) :(#AtCoder #ALGOARTISプログラミングコンテスト2023秋（ARC168） https://t.co/rk2VYOh6ly
— devgenjin77 (@devgenjin77) 2023年11月19日

振り返り

Aで余計なペナを喰らうわ、BではWAが取れないわで散々な内容でした。

A問題

A - <Inversion>

初回の考察では、 $x_1=N$ とし、 $S_i$ が<の場合、 $x_{i+1}=x_i+1$ 。

そうでない場合 $x_{i+1}=x_i-1$ として、 $x$ の転倒数を求めるのが良いかと思い実装してみたら、サンプル４が合わず。。

よくよく考えると、<で区切ったところで大きく差をつけることで、転倒数の最小化が図れるような気がする。ということは、結局>の連続を見て、それぞれの転倒数を計算して合計すれば良いのでは。。

で、結局この考察が当たりだったのですが、初回提出はオーバーフローでWAを喰らってしまい、余計な1ペナを喫してしまいました。

36分40秒1ペナで1完です。

提出コード

https://atcoder.jp/contests/arc168/submissions/47760433

B問題

B - Arbitrary Nim

grundy数かなあという問題。正直、grundy数は最近まともに勉強し始めたところなので、あまりよく理解できてない。。

とりあえず考察してみると、 $A$ の全てのxorが $0$ でない場合は、普通のNimのようにすれば先手が必勝のため $k$ の上限は無し。

$A$ の全てのxorが $0$ の場合どうするかだが、これが全然分からずで、サンプルを見ながら、 $A$ の最大値マイナス１とか、 $N$ の偶奇で判定してみたりとか色々考察してみてはとりあえず提出するなどしてみましたが、一向にWAが取れず。。

結局、時間いっぱい使って解き切れずでした。

C問題

C - Swap Characters

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

D問題

D - Maximize Update

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

E問題

E - Subsegments with Large Sums

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

F問題

F - Up-Down Queries

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

これまでの実績

さらに水色が遠のいてしまいました。また年内に再入水できるように頑張ります。

総括

一か月振りのARCでしたが、今回も結局惨敗となりました。やはり考察を積み重ねて解法を導くというところがまだまだ苦手なんだという印象です。

とはいえ、いつまでも実力不足を嘆いていても仕方なし。また次回に向けて、今回の復習をしていこうと思います。

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

2023-11-07

トヨタ自動車プログラミングコンテスト2023#6(AtCoder Heuristic Contest 026)参加記

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

2023/11/5に開催されたトヨタ自動車プログラミングコンテスト2023#6(AtCoder Heuristic Contest 026)に参加しました。

atcoder.jp

前回のAHCで青パフォをゲットし、ヒューリスティックのレートは、やっと入青というところまで来ました。

今後は、青パフォ以上を取っていかないと、まともにレートが上がっていかないという状況。今回は青パフォ目指して頑張っていきます。

参加します。
前回の短期AHCでは、良い結果が出なかったので、今回は青パフォ目標で頑張ります

トヨタ自動車プログラミングコンテスト2023#6（AtCoder Heuristic Contest 026） - AtCoder https://t.co/v76pvVdg99
— devgenjin77 (@devgenjin77) 2023年11月5日

今回の結果

なんと542位で終了。。全くスコアが伸びずで、散々な結果になりました。

パフォーマンスは、緑色の真ん中というところ。レートは結局１しか上がりませんでした。。

頑張ったつもりが、緑パフォで終了😩
devgenjin77さんのトヨタ自動車プログラミングコンテスト2023#6（AtCoder Heuristic Contest 026）での成績：542位
パフォーマンス：1043相当
レーティング：1618→1619 (+1) :)
Highestを更新しました！#AtCoder #AHC026 https://t.co/Vy7wO7H9LH
— devgenjin77 (@devgenjin77) 2023年11月5日

振り返り

最初の方針が悪かったみたいです。。

A問題

A - Stack of Boxes

方針の概要としては、以下のような感じでした。

#AHC026 お疲れ様でした。
得点は1,338,830点。最終結果542位でした。
取り除くべき箱の上に積んでいる箱を他の山に動かす際、移動先の山の転倒数の悪化具合が一番ましな山に動かす貪欲を思いついたのですが、全然スコアが伸びずでした😩 pic.twitter.com/TGX5vYDpac
— devgenjin77 (@devgenjin77) 2023年11月5日

今回は、10個の山に積まれた箱を番号順に取り出す時、どう動かせば効率良く全て取り出せるかという問題。

最大の操作回数が $5000$ 回ということで、箱の数 $200$ に対しては少し大きめかなあという印象。

ふつうにやれば、取り出すべき箱の上のをごっそり他にもってけば良いので、これだけ操作回数が多いのは、まとめて持っていくよりは分割して各山に散らす方針が良いのでは？という感じがしました。

次に、動かすべき箱のかたまりを上から下へ見た時に、単調増加でない箇所があれば、いずれ下にある箱を取り除く時に、上にあるかたまりを動かす必要がでてくるので、最初から分割して運んだらいいのでは？というアイデアが浮かびました。

さらに、動かす先は、できるだけ自分より小さい数が少ない場所が良いだろうということで、かたまりの移動先の山の転倒数を操作前後で比較し、増加具合が一番小さい山を遷移先とすることに。

これで、実装したら結構いい感じになるかと思ってましたが、実際に提出してみると、順位は400の中盤ぐらいという感じで全然大したことが無かったです。。

この後は、前半だけ、かたまりを丸ごと移動させて、後半は単調増加のかたまりに分割して移動するなどの工夫を入れてみましたが、気持ち程度の得点増加にしかならずでした。

最終提出コード

https://atcoder.jp/contests/ahc026/submissions/47306750

感想

最初に選んだ方針がダメすぎたのと、方針転換が全然できなかったのが反省点かと。実装にも結構手間取ったので、色々試す余裕は無かったです。
コンテスト後のTLを見てみると、今回は山毎にソートする方針が強かった模様。が、、理屈がよくわかってないです。

これまでの実績

$1$ 上がりました。

総括

今回の短期コンテストは、ハズレ方針を引いてしまったなあという感じです。

大変残念な回でしたが、めげてても仕方ないので、また次、勝てるように精進していこうと思います。

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

2023-11-06

HHKBプログラミングコンテスト2023(AtCoder Beginner Contest 327)参加記

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

2023/11/4に開催された、HHKBプログラミングコンテスト2023(AtCoder Beginner Contest 327)に参加しました。

atcoder.jp

参加前のレートは1242。直近のHighest手前まで戻してきたというところで、これから水色安全圏までレートを上げていきたいところです。

ということで、今回も水色パフォ目標で挑んでいきます。

Rated参加します。
今回も水パフォ以上とって、Highest更新目指します✊

HHKBプログラミングコンテスト2023(AtCoder Beginner Contest 327) - AtCoder https://t.co/JvHjaQ6gFa
— devgenjin77 (@devgenjin77) 2023年11月4日

今回の結果

D問題でどハマりを喰らってしまい、３完で終了という残念な結果となりました。

パフォーマンスの方は緑にすら届かず。。レートは暴落して、再度緑落ちを喰らってしまいましたとさ。

３完茶パフォと大事故を喰らって緑落ち😭😭
また次回頑張ります

devgenjin77さんのHHKBプログラミングコンテスト2023(AtCoder Beginner Contest 327)での成績：4534位
パフォーマンス：711相当
レーティング：1242→1198 (-44) :(#AtCoder #ABC327)https://t.co/unAAeI81yb
— devgenjin77 (@devgenjin77) 2023年11月4日

振り返り

A問題からペナを喰らってしまうなど、全体的に残念な内容でした。

A問題

A - ab

問題を見た瞬間、文字列 $S$ にabが含まれるかどうかを判定すれば良いかということでs.contains("ab")がtrueならYesという感じの実装で提出。

その後、結果を見ずにB問題に進みましたが、Bを提出した瞬間、WAになっていたということに気づきました。。

結局"ba"もチェックする必要があるということで、後で振り返ると、サンプルを確認していれば防げたミスでした。

AをACした時点では、6分54秒1ペナで2完。

提出コード

https://atcoder.jp/contests/abc327/submissions/47218764

B問題

B - A^A

見た目少し難しそうだが、制約から、 $A$ の取りうる範囲はそんなに大きく無いので、全探索が効くかという感じ。

とりあえず、 $A$ の探索範囲を $1$ から $100$ までとし、 $A^{A}$ がLongの最大を超える場合は探索打ち切りという感じで実装。これで問題なくACが取れました。

ちなみに、この時点でAの提出がWAだったことに気づいたので、6分24秒1ペナで1完です。

提出コード

https://atcoder.jp/contests/abc327/submissions/47217956

C問題

C - Number Place

与えられた $9 \times 9$ の盤面が、ナンプレの配置として正しいかを判定する問題。

やることとしては、各行、各列、そして各 $3 \times 3$ のブロックに対して、愚直に $1$ 〜 $9$ が１つずつ存在するかを判定するだけ。

実装に結構時間がかかりましたが、問題なくACが取れました。18分1秒1ペナで3完。

提出コード

https://atcoder.jp/contests/abc327/submissions/47012495

D問題

D - Good Tuple Problem

考察したところ、グラフに落として考えれば良くて、各連結成分毎にDFSを使って各頂点に0か1を設定していき、隣接する頂点が同じ値になったらNoという感じで良さそう。

ということで、上記の要領で実装して提出したものの、なぜかWAが取れず。。

不具合になりそうな所に当たりをつけていじってみても、同じWAの繰り返し。。とりあえず残り30分を切ったところで、一旦この問題を諦めることにしました。

因みに、コンテスト後に解説を見ても、本番中に行った考察とほぼ同じ感じだったので、なぜ通らないのかが未だにわからずです。

なお、この問題は単なる二部グラフ判定の典型だった模様。この程度の典型が解けなかったのは、非常に残念です。

E問題

E - Maximize Rating

考察してみると、コンテストを選ぶ回数を固定したときに、レーティングの計算式の分子の部分である、 $\sum_{i=1}^{k}(0.9)^{k-i}Q_i$ の最大をDPで求めることができれば解けそうな感じである。

あとは、 $dp\lbrack i \rbrack \lbrack j \rbrack :=$ $i$ 個目まで見た時に、 $j$ 個採用した時の前述の合計の最大値という感じでDPが組めれば、というところでしたが、どうにも実装がうまくいかずでサンプルすら通らない形に。

時間いっぱい頑張りましたが、結局ACを取り切ることはできませんでした。

F問題

F - Apples

Eに詰まりかけたところで、ワンちゃんあるかと問題をチラ見しましたが、結局わからずで撤退しました。

G問題

G - Many Good Tuple Problems

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

これまでの実績

再度の緑落ちを喰らいました。また、入水に向けて頑張ります。

総括

A問題のミスや、D問題のバグらせなどもあり反省点が多い回でしたが、E問題までは、考察はなんとかできている感じなので、そんなに悲観する内容では無いかというところです。

次回以降に向けては、もう少し実装力をつけていく必要があるかというところ。過去問を解く数などをいつも以上に上げていくように心がけて、準備していこうと思います。

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

2023-10-29

パナソニックグループプログラミングコンテスト2023(AtCoder Beginner Contest 326)参加記

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

2023/10/28に開催された、パナソニックグループプログラミングコンテスト2023(AtCoder Beginner Contest 326)に参加しました。

atcoder.jp

先週のABCで再度の入水を果たしたものの、現状ギリギリ水色コーダーという身分のため、なんとかレートを水色安全圏まで持っていきたいところ。

今回も水色パフォを取って、レートを上げていこうという感じで挑んでいきます。

Rated参加します。今回も水パフォ取って、水レート維持を目指します✊

パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 326） - AtCoder https://t.co/RZhB6z0gUl
— devgenjin77 (@devgenjin77) 2023年10月28日

今回の結果

終了３分前で、なんとかD問題を突破し、５完を確保することができました。

パフォーマンスの方は、水色の上の方まで出てくれて、なんとか直近のHighest付近までレートを戻すことができました。

５完水パフォ！
先週に続き、３桁順位を達成しました😂😂

devgenjin77さんのパナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 326）での成績：984位
パフォーマンス：1534相当
レーティング：1204→1242 (+38) :)#AtCoder #ABC326 https://t.co/hULv17onWk
— devgenjin77 (@devgenjin77) 2023年10月28日

振り返り

結構ミスが重なってしまい、反省点の多かった回でした。

A問題

A - 2UP3DOWN

シンプルに条件分岐を組めそうな感じもするが、ハマったりする可能性もあるので、 $X \lt Y$ の場合と、 $X \gt Y$ の場合とで愚直に場合分けすることにしました。

少し実装に時間がかかったものの、問題なくAC。2分51秒で1完。

提出コード

https://atcoder.jp/contests/abc326/submissions/46994139

B問題

B - 326-like Numbers

$N$ からスタートして、326-like numberが見つかるまで $1$ づつインクリメントしながら試していけば良い。

これは、やるだけの実装でACが取れました。5分6秒で2完。

提出コード

https://atcoder.jp/contests/abc326/submissions/46998662

C問題

C - Peak

実数 $x$ を、数列 $A$ のすべての値について試してみて、実際に獲得できたプレゼントが一番多かったものを採用する方針で良いはず。

で、ここで当初取れる範囲を、 $x + M - 1$ で二分探索して、同値のものが見つかった場合プラス $1$ 補正するという実装をしたので、初回提出ではWAを喰らってしまいました。。

じゃあ、同じ値が見つかるまでプラス方向に補正し続けるのはどうかと試してみたら、TLEを喰らってしまう始末。

結局、普通に半開区間として、 $x + M$ を二分探索すれば、実装もシンプルだったというオチでした。

17分57秒2ペナで3完。ややこしく考えてしまい、変なとこでつまづいてしまいました。

提出コード

https://atcoder.jp/contests/abc326/submissions/47012495

D問題

D - ABC Puzzle

問題を一読した感じ、どうも実装の重い全探索系の問題のような気がする。

C問題を通した時点で順位表を見たところ、少しばかりE問題の方がAC数が多いようで、D問題でハマるリスクを考えれば、先にE問題を見てみた方が良いかという感じがしました。

ということで、一旦D問題をスキップすることに。

で、E問題を通したので、D問題に取り組むことに。

とりあえず、全行について、順列全探索的なことができるかと実装してみましたが、これはTLE。。

ということは、ある程度枝刈りしていくとなんとか解ける感じになるかなということで、列で同じ文字が２回以上出るケースをスキップするようにしました。が、、なぜかこれはWA。。

多分、どこかバグってるんだろうと思いながら色々調べているうちに、時間切れ間際まで追い込まれてしまいましたが、なんとか文字の重複チェックでバグっている箇所を突き止めて終了３分前にACを取り切ることができましたとさ。

97分21秒5ペナで5完。内容はボロボロでしたが、なんとか５完確保できてよかったです。

提出コード

https://atcoder.jp/contests/abc326/submissions/47041680

E問題

E - Revenge of "The Salary of AtCoder Inc."

まさしく、期待値DPのような形をした問題という印象でした。

具体的には、 $dp \lbrack i \rbrack :=$ 変数 $x = i$ の時にダイスを振って追加でもらえる給料の期待値と定義し、 $i = N$ から始めて $i = 0$ に向かってデクリメントしながら計算していけば、最後 $dp \lbrack 0 \rbrack$ に答えが入るという感じになるかと。

$dp\lbrack i \rbrack$ の具体的な値は、 $j \gt i$ となる $A_j$ の合計と、 $dp \lbrack j \rbrack$ の合計を $N$ で割れば計算できるかなという感じで実装したら、一応サンプルが通ったので提出。なんと一発でACを取り切ることができましたとさ。