2024-01-31

AtCoder Beginner Contest 338参加記

AtCoder 競プロ ABC

2024/1/27に開催された、AtCoder Beginner Contest 338に参加しました。

先週、久々の５完を達成し、レートの方は、再入水寸前というところまで上げることができました。

この勢いで、まずは再入水を早く達成したいところ。今回も５完了目標で臨むことにします。

Rated参加します。
今回も５完達成して、再入水を決められるように頑張ります✊

AtCoder Beginner Contest 338 - AtCoder https://t.co/FJXzJSNgFg
— devgenjin77 (@devgenjin77) 2024年1月27日

今回の結果

蓋を開けてみると、４完達成がやっとという結果でした。。

パフォーマンスは、水色にも届かずという感じで、結局今回は負け。再入水はお預けになりましたとさ。

４完緑パフォで負け😢
再入水はお預けになりました
devgenjin77さんのAtCoder Beginner Contest 338での成績：2105位
パフォーマンス：1136相当
レーティング：1193→1188 (-5) :(#AtCoder #ABC338 https://t.co/Igvj5QYf6t
— devgenjin77 (@devgenjin77) 2024年1月27日

振り返り

変な勘違いで、問題を余計に難しく考えてしまったところがあり、時間を浪費してしまった回でした。

A問題

A - Capitalized?

isUpperCaseやisLowerCaseを使って、大文字小文字の判定をしていくだけの問題。

やるだけの実装をして提出。問題なくACが取れましたとさ。2分53秒で1完です。

もうちょっと簡単に実装するなら、正規表現を使ってみるとかですかね。

提出コード

https://atcoder.jp/contests/abc338/submissions/49694189

B問題

B - Frequency

サイズ26の配列を作成して、各文字の個数をカウントする。あとは、最大値を計算するだけ。

これも、ほとんどやるだけの実装。問題なくACが取れて、5分35秒で2完です。

提出コード

https://atcoder.jp/contests/abc338/submissions/49699070

C問題

C - Leftover Recipes

当初、 $N$ の最大を $10^{6}$ ぐらいかと誤解していたので、やたらと難しく考えてしまいましたが、よくよく確認してみると、 $N$ の最大が $10$ 程度ということで、結局、料理Aを作る個数を固定した全探索で解決できそうというオチでした。

方針だけ決まれば、あとは普通に実装してAC。25分28秒で3完です。

初手で難しく考えすぎていたところで、10分以上ロスしてしまいました。。

提出コード

https://atcoder.jp/contests/abc338/submissions/49713229

D問題

D - Island Tour

橋 $i$ を壊した場合に通る橋の数と、橋 $i$ を壊さない場合に通る橋の数は、ツアー中のぞれぞれの移動について独立に考えることができそうです。

$ans \lbrack i \rbrack :=$ 橋 $i$ を壊した場合、すべての橋が残っている状態から比較して、ツアーの旅程で通る橋の数がどれだけプラスされるか。

上記の値が計算できれば、あとは最小値を取って、すべての橋が残っている場合のツアー中に通る橋の数と足すことで答えになる。

例えば、島の数が $10$ 個で、島 $3$ から島 $6$ に移動する場合、橋 $3$ から $5$ のいずれかが破壊される場合は、破壊されない場合に比べて $4$ つ余計に橋を通る必要が出てくる。よって、橋 $3$ から $5$ それぞれに $4$ を足すという要領です。

しかし、これを普通に計算するとTLEになるので、区間加算かつ最小値取得を効率的にできれば良いという感じだが、やり方がなかなか思いつかない。。

で、結局、D問題で使うのは場違いかと思ったが遅延セグ木を使って、区間加算と最小取得を行うぐらいしか思いつきませんでした。

使い慣れないライブラリなので、実装に悪戦苦闘しながらも、なんとかサンプルが通る実装を作って提出。なんとかACを取り切ることができましたとさ。87分36秒で4完です。

あとで解説を確認すると、imos法で解けた問題だったとのこと。履修済みのアルゴリズムが咄嗟に出て来なかったのは反省材料ですが、なんとか通し切ることができたのは良かったかと。

提出コード

https://atcoder.jp/contests/abc338/submissions/49735426

E問題

E - Digit Sum Divisible

C、Dで大分時間を消費したので、ほぼ絶望的な状態で臨んだE問題。

一応、問題に目を通したのものの、何にも解法が浮かばずで時間切れ終了になりましたとさ。

F問題

F - Rotation Puzzle

問題文すら読んでいません。

G問題

G - 16 Integers

問題文すら読んでいません。

これまでの実績

今回、再入水はお預け。が、致命的な負けでは無いので、次回取り戻せればと。

総括

今回は、問題文を難しく考えたがために、余計な時間を喰ってしまうというミスがあった回でした。

結局、まだまだ緑Diffレベルの基礎も曖昧な状態になっているということでしょう。当面は、基礎の振り返りに全力を入れていきたいと思います。

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

2024-01-22

トヨタ自動車プログラミングコンテスト2024#1(AtCoder Beginner Contest 337)参加記

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

2024/1/20に開催された、トヨタ自動車プログラミングコンテスト2024#1(AtCoder Beginner Contest 337)に参加しました。

atcoder.jp

最近、５完以上取っての水パフォが全く取れていないので、レートの方も停滞気味です。

今回は、配点的にも５完が現実的な感じなので、なんとか５完以上取って、レートを上げていこうという感じで頑張っていきます。

Rated参加します。
今回５完目指してがんばります。

トヨタ自動車プログラミングコンテスト2024#1（AtCoder Beginner Contest 337） - AtCoder https://t.co/AAIgBKZIPa
— devgenjin77 (@devgenjin77) 2024年1月20日

今回の結果

なんとか５完を確保！参加したABCでは直近の５回が４完以下だったので、大分久しぶりの５完達成です。

結果として、水色の真ん中あたりのパフォーマンスが取れ、レートは大きく上昇。なんとか再入水が現実的になってきました。

なんとか５完達成😂
devgenjin77さんのトヨタ自動車プログラミングコンテスト2024#1（AtCoder Beginner Contest 337）での成績：1297位
パフォーマンス：1464相当
レーティング：1159→1193 (+34) :)#AtCoder #トヨタ自動車プログラミングコンテスト2024#1（ABC337） https://t.co/iNDwGqZNDw
— devgenjin77 (@devgenjin77) 2024年1月20日

振り返り

Dまでは、なんとかミスなしで順調に来ましたが、E問題で１ミスしたのは反省点です。

A問題

A - Scoreboard

$X_i$ の合計と $Y_i$ の合計を比較して、結果を返すだけ。

実装して、問題なくACが取れましたとさ。

一応、提出前の検証も実施してたので、若干遅めの2分34秒で1完です。

提出コード

https://atcoder.jp/contests/abc337/submissions/49436087

B問題

B - Extended ABC

とりあえず愚直で実装する方針で。

Aより前にBやCが存在するか、またはBより前にCが存在するならNo、それ以外はYesという感じで実装。

こちらも問題なくAC。7分30秒で2完です。

提出コード

https://atcoder.jp/contests/abc337/submissions/49445205

C問題

C - Lining Up 2

入力データより、先頭の人を起点にした、有向パスグラフを構築する。あとは、先頭から順にたどっていけば解けるかという印象。

ということで、こちらも実装してなんとかAC。17分24秒で3完です。

提出コード

https://atcoder.jp/contests/abc337/submissions/49457958

D問題

D - Cheating Gomoku Narabe

oを $K$ 個連続させられるかは、各行、各列ごとに独立に考えることが出来る。

ということで、各行、各列の並びについて、 $K$ 文字の部分文字列を尺取り法で全探索する。部分文字列にxが無ければ.を全てoにすることで $K$ 個連続になるので、.の個数が最小の操作回数となる。

こちらも、実装して問題なくAC。39分10秒で4完です。

提出コード

https://atcoder.jp/contests/abc337/submissions/49478063

E問題

E - Bad Juice

問題読んでて、なんか既視感あるかと思ったら、これって毒入りワインを囚人に分ける問題やんね。。

ということで、内容もうろ覚えだったので、まずは「毒入りワイン　囚人」でググってみて、内容を確認。あとは実装するだけです。

で、当初の実装は、

$M$ は $N$ を2進数表記にした時の文字列長
各ワイン $1,2,...,N$ について２進数表記した文字列の右から $i$ 桁目に1が立っていたら囚人 $i$ に飲ませる
文字列 $S$ を逆順にみた２進数で評価した値が腐ったジュースの番号

という感じで提出しましたが、これがWA。。。よくよく考えると、１本だれにもあげないジュースがあり、結果だれもお腹を壊さなければそれが当たりになるか。。

ということで、

$M$ は $N - 1$ を2進数表記にした時の文字列長
各ワイン $1,2,...,N - 1$ について２進数表記した文字列の右から $i$ 桁目に1が立っていたら囚人 $i$ に飲ませる
文字列 $S$ を逆順にみた２進数で評価した値が腐ったジュースの番号。但し、 $0$ だった場合、 $N$ を答えとする。

という実装で、なんとかACを取り切ることができましたとさ。67分36秒1ペナで5完。久々の５完は中々達成感があります。

蛇足ですが、よくよく考えると、ワインを0-indexedで考えておけば、もう少し実装が楽になったような。。

提出コード

https://atcoder.jp/contests/abc337/submissions/49494838

F問題

F - Usual Color Ball Problems

とりあえず、時間もあるので問題文に目を通してみたが、なにもわからず。。順位表的にも黄パフォはありそうな感じなので、早々に諦めです。

G問題

G - Tree Inversion

なんかF問題より解かれている感じなので、なんかあるかと勘ぐっては見ましたが、結局、問題すら見ておりません。

これまでの実績

とりあえず、再入水直前まで戻すことができました。

総括

今回、久々の５完達成でしたが、これはE問題がたまたま既視感あったからという運用素が強かったかもしれません。

再入水と水レート安定のためには、今後のABCでも安定して５完以上達成できるかというのが、大事かと思いますので、今回の結果に満足せず、精進を重ねていきたいと思います。

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

2024-01-19

AtCoder Beginner Contest 336参加記

AtCoder 競プロ ABC

2024/1/14に開催された、AtCoder Beginner Contest 336に参加しました。

atcoder.jp

先週のABCでは、辛くも勝ちを収めてレートを上げることに成功しました。この勢いで、早々に入水を伺うべく、今回も頑張っていきます。

振り返ってみると、最近５完出来ていない状況のようなので、今回は５完以上を目標にしてみます。

Rated参加します。最近５完以上できていないので、今回は５完目標で頑張ってみます。

AtCoder Beginner Contest 336 - AtCoder https://t.co/ARkBVPz0vm
— devgenjin77 (@devgenjin77) 2024年1月14日

今回の結果

と、意気込んで見たものの、結局４完で終了。E、F問題の難易度が高かったような。。。

途中のやらかしなどもあり、順位の方は大きく伸びず。今回は負けという結果になりました。

４完確保でギリ勝ち😅
Dの解答時間で大分上下しそうな感じだが、一部勘違いがあって時間ロスしたのが悔やまれる。。

devgenjin77さんのAtCoder Beginner Contest 332での成績：1556位
パフォーマンス：1229相当
レーティング：1142→1151 (+9) :)#AtCoder #ABC332 https://t.co/z6i48NUF4v
— devgenjin77 (@devgenjin77) 2023年12月10日

振り返り

単純ミスでWAを繰り返すなど、大きな反省点があった回でした。

A問題

A - Long Loong

所謂、やるだけの問題。実装後、提出して、問題なくAC。

1分31秒で1完です。

提出コード

https://atcoder.jp/contests/abc336/submissions/49278050

B問題

B - CTZ

これも、書かれていることをそのまま実装してAC。3分27秒で2完です。

あとでよくよく考えると、Javaだと、Integer.numberOfTrailingZerosが使えたなあ。。

提出コード

https://atcoder.jp/contests/abc336/submissions/49283166

C問題

C - Even Digits

$N$ を5進数に変換して、あとは01234を02468に変換する感じかと思い実装。

で、これでACかと思いきや、 $N = 0$ のケースで出力できてないという単純ミスで、WAという結果に。。。

修正してなんとかAC。9分5秒1ペナで3完です。

提出コード

https://atcoder.jp/contests/abc336/submissions/49289727

D問題

D - Pyramid

$dpl \lbrack i \rbrack :=$ 左から見た時に、 $i$ 番目で作成できるピラミッドの頂点の最大の高さ。
$dpr \lbrack i \rbrack :=$ 右から見た時に、 $i$ 番目で作成できるピラミッドの頂点の最大の高さ。

この２つを求めると、あとは、左から見た時に $i$ 番目で作成できるピラミッド数列の最大サイズが求められるはず。

ということで、方針は決まったが、これが実装がなかなかうまくいかない。

さらにサンプルのテストケースが弱かったこともあり、サンプルが通った実装を出してみても余裕でWAを喰らう始末。。いや、サンプルの所為にするわけではないが。。

そんなこんなで、さらに実装誤りで都合２WAを喰らってから、やっとのことでACを取ることができましたとさ。68分7秒3ペナで4完です。

提出コード

https://atcoder.jp/contests/abc336/submissions/49308830

E問題

E - Digit Sum Divisible

目標も５完達成のために、なんとか通したい問題だったが、問題を読んでもよくわからん。

多分見た目の雰囲気的に桁DPかなというのが見えてきたが、結局桁DPを理解できてないので、解けるわけもなくという感じ。

結局、早々にこの問題は諦め。

F問題

F - Rotation Puzzle

これも、問題に目を通したものの、結局なにもわからず。ここで時間切れになりましたとさ。

G問題

G - 16 Integers

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

これまでの実績

今回ちょい負けで、入水が少し遠くなりました。

総括

５完出来なかったことは、知識不足なので、精進すればよいということだが、凡ミスが続いているのは良くない傾向だなあ。。

これも、まだまだ基本的な行動が出来ていない証拠。今年は一旦初心に帰って、典型問題や鉄則本などの履修に努めてみようと思います。

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

2024-01-08

AtCoder Beginner Contest 335(Sponsored by Mynavi)参加記

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

2024/1/6に開催された、AtCoder Beginner Contest 335（Sponsored by Mynavi）に参加しました。

atcoder.jp

2024年最初のRatedコンテスト。昨年は入水を果たしたものの、現状緑落ちという状態なので、今年は早めの再入水を決めて水色をキープし、入青を伺えるようになることを目標に頑張っていこうと思います。

ということで、今回は再入水に向けて、勝ちを収められるようにがんばります。

Rated参加します。
２０２４年最初のコンテスト。とりあえず勝ちで始められるように頑張ります✊
AtCoder Beginner Contest 335（Sponsored by Mynavi） - AtCoder https://t.co/y6rnbpbeS6
— devgenjin77 (@devgenjin77) 2024年1月6日

今回の結果

気合いを入れてはみたものの、４完という残念な結果で終了です。

パフォーマンスは、惜しくも水色に届かず。一応、勝ちを収めたものの、少し物足りなさが残る結果でした。

４完終了でしたが、なんとか勝ち😅
devgenjin77さんのAtCoder Beginner Contest 335（Sponsored by Mynavi）での成績：1980位
パフォーマンス：1185相当
レーティング：1162→1165 (+3) :)#AtCoder #ABC335（SponsoredbyMynavi） https://t.co/kdFIuQiJxa
— devgenjin77 (@devgenjin77) 2024年1月6日

振り返り

E問題のTLEを解消することができませんでした。

A問題

A - 202<s>3</s>

文字列 $S$ の末尾を4に変えて出力するだけ。

実装して、問題なくAC。1分16秒で1完です。

提出コード

https://atcoder.jp/contests/abc335/submissions/49061659

B問題

B - Tetrahedral Number

$x, y, z$ を、それぞれ $0$ から $N$ まで全部試して、 $x + y + z \le N$ なら出力という感じの全探索でOK。

こちらも問題なくAC。3分18秒で2完です。

提出コード

https://atcoder.jp/contests/abc335/submissions/49066589

C問題

C - Loong Tracking

以下考察。

$i$ 回目の移動後の、頭のパーツの位置の $x$ 座標、 $y$ 座標を、それぞれ $posx \lbrack i \rbrack$ $posy \lbrack i \rbrack$ とする。
2のクエリが来た時、 $p$ の値が、1のクエリの回数以下の場合、答えは、1のクエリの回数から、 $(p - 1)$ を引いた回数の移動後の頭のパーツの位置になる。
2のクエリが来た時、 $p$ の値が、1のクエリの回数より大きい場合、答えは、 $x$ 座標が、 $p$ から1のクエリの回数を引いた値。 $y$ 座標が、 $0$ となる。

という感じの実装で提出したら、問題なくACが取れましたとさ。20分50秒で3完。

元々の全パーツの位置を配列で持っておけば、分岐が要らないようにできてシンプルになったかなあという印象ですが、まあACが取れたのでよし。

提出コード

https://atcoder.jp/contests/abc335/submissions/49082063

D問題

D - Loong and Takahashi

考察してみると、 $N \times N$ サイズのグリッド上で、左上から始めて時計回りに $1$ ずつインクリメントしながら移動していくという感じの実装でOKかという感じです。

ということで、少し実装に苦労したものの、問題なくACが取れましたとさ。

36分20秒で4完です。

提出コード

https://atcoder.jp/contests/abc335/submissions/49094184

E問題

E - Non-Decreasing Colorful Path

考察してみると、広義単調増加なパスでない場合は、得点が $0$ になるということで、 $A_u \gt A_v$ の場合は、 $u$ から $v$ への辺を引かない有向グラフとして定義すれば良いのではないかという感じ。

あとは、頂点 $1$ から始めて、BFSを使って、各頂点毎の最大得点を計算し、最終的に、頂点 $N$ の得点を見ればOKかと。。

ということで、実装してみたら、WAこそ無いものの、TLEという結果に。。。

もう少し考察して、 $A$ の値が同じ頂点で直接辺が引かれている場合、Union-Findを使って、頂点を同一視することで計算量が落とせるのでは？という考えが浮かぶ。

が、、これを実装するものの、TLEが少し減っただけで通らず。

結局、TLEを解決することができずで時間切れになりましたとさ。

F問題

F - Hop Sugoroku

Eが解けないので、これならなんとかなるかと目を通したものの、なにもわからずで終了。

G問題

G - Discrete Logarithm Problems

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

これまでの実績

今年最初のコンテストをなんとか勝ちで終えました。

総括

Eは惜しいところで解けませんでしたが、これも実力不足というもの。次回ABCまでにきっちりと復習していこうと思います。

あと、Fは平方分割だった模様。これもまだまだ理解できていないアルゴリズムなので、これを機会に勉強していきます。

ということで、今年も１年競プロを頑張ります。

2023-12-29

ユニークビジョンプログラミングコンテスト2023 クリスマス(AtCoder Beginner Contest 334)参加記

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

2023/12/23に開催された、ユニークビジョンプログラミングコンテスト2023 クリスマス(AtCoder Beginner Contest 334)に参加しました。

atcoder.jp

先週は、所用のためコンテスト不参加だったので、２週間ぶりの参加。年内にRatedで出られるコンテストは、これきりということで、年内再入水は絶望的ですが、来年に向けて良い成績が残せるように頑張るのみです。

２週間ぶりの参加。年内の再入水は厳しそうだが、とにかくレートを上げられるように頑張るのみです。

ユニークビジョンプログラミングコンテスト2023 クリスマス (AtCoder Beginner Contest 334) - AtCoder https://t.co/gAMakBWFY2
— devgenjin77 (@devgenjin77) 2023年12月23日

今回の結果

ACDEの４完で終了。超久しぶりにB問題を落としてしまいました。

それでも、なんとか水パフォ確保という結果で、レートは上昇。なんとか今年最後のコンテストを勝ちで終えることができましたとさ。

B問題を落としたが、なんとか水パフォ確保で勝ち😅

devgenjin77さんのユニークビジョンプログラミングコンテスト2023 クリスマス (AtCoder Beginner Contest 334)での成績：1620位
パフォーマンス：1262相当
レーティング：1151→1162 (+11) :)#AtCoder #ABC334 https://t.co/qhgZYBGMfx
— devgenjin77 (@devgenjin77) 2023年12月23日

振り返り

B問題でやらかしてしまいましたが、なんとかリカバリできたという印象です。

A問題

A - Christmas Present

$B \gt G$ の場合Bat、それ以外は、Gloveを出力するだけ。

実装後、テストもそこそこに提出してAC。51秒で1完です。

提出コード

https://atcoder.jp/contests/abc334/submissions/48733223

B問題

B - Christmas Trees

見るからに、ややこしそうな問題という印象。

とりあえず、基点を $0$ にしておいたらシンプルになるかということで、 $L$ と $R$ ぞれぞれから $A$ を引いて補正してみる。

あとは、 $L$ 、 $R$ を、それぞれ $M$ で割った整数部を足した後、原点を跨ぐ場合は $1$ 足してみるという感じでOKか思い、提出してみたら、これがWA。。

どっかのコーナーケースに引っかかっているのかという感じだが、すぐには原因が分からない感じ。

IF文でゴリ押せばなんとか通りそうだが、もう時間が30分経過していることと、順位表を見てると通常B問題よりは躓いている人が多い印象ということから、これ以上B問題にとりかかるのはリスクが高いのではという判断で、一旦スキップすることにしました。

C問題

C - Socks 2

これもC問題にしては、やたら難しそうな問題という印象だが、B問題をスキップしている手前、なんとか解かないといけない。

以下考察。

残っている靴下で計算した「奇妙さ」の総和と、なくした靴下で計算した「奇妙さ」の総和は、おそらく一緒になるので、なくした靴下で「奇妙さ」を計算すればよい。
$K$ が偶数の場合、なくした靴下の色でソートしてから、隣接するペアで「奇妙さ」を計算していくのが最善かと。
$K$ が奇数の場合どうするか。 $K=1$ の場合は、「奇妙さ」を $0$ にできるが、そうでない場合、どの靴下を捨てるかを全探索しないといけない感じ。
結局、靴下の色でソートしてから、先頭から隣接するペアを見た時の「奇妙さ」の累積和、および、末尾から隣接するペアを見た時の「奇妙さ」の累積和を前計算し、作成するペアの数を $\lfloor \frac{K}{2} \rfloor$ で固定した時に、「奇妙さ」の合計が最小になる組を選べばOKかと。

ちょっと、これがC問題で求められる解法かよという印象だが、なんとか実装して提出したらACが取れましたとさ。

54分50秒で2完。大分立ち遅れてますが、なんとか1完で大爆死は免れたという感じです。

提出コード

https://atcoder.jp/contests/abc334/submissions/48778438

D問題

D - Reindeer and Sleigh

順位表上からみても、そんなに難しくはないという印象の問題。

とりあえず、 $R$ をソートしてから累積和を作り、 $A \lbrack i \rbrack :=$ $i$ 台のソリを引くために必要な最小のトナカイの数を前計算する。

あとは、各クエリの $X$ で何台のソリが引けるかを、先ほど計算した $A$ を二分探索することで求めればOKかと。

ということで、あとは実装して問題なくAC。64分0秒で3完です。

提出コード

https://atcoder.jp/contests/abc334/submissions/48782912

E問題

E - Christmas Color Grid 1

連結ということで、Union-Findを使って解くべきかという印象。

とりあえず、初期状態の $S$ より、隣接する#のマスを連結させることで、連結成分の数を前計算。

次に、 $S$ 上の、各.のマスを見ていき、そこに隣接する#がどの連結成分に属するかを、Union-Findのleader()関数を使って見ていく。

すると、連結成分の種類が0なら、連結成分数が1増える。1なら、0増える。2なら1減るという要領で、.を#にしたときの緑の連結成分数が計算可能。あとは、普通に期待値を計算すればOK。

実装も、なんとか時間内に間に合ってAC。94分54秒で4完です。

提出コード

https://atcoder.jp/contests/abc334/submissions/48795569

F問題

F - Christmas Present 2

なんとか目を通したものの、なにもわからずで終了。

G問題

G - Christmas Color Grid 2

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

これまでの実績

今年最後のコンテストをなんとか勝ちで終えました。

総括

今回、Bが解けなかったのは大きな反省材料。これも日々の精進が足りないのが原因でしょうなあ。

これで、2023年のコンテストも終了。今年は、目標であった入水をなんとか達成できましたが、レートの方はというと、行ってこいという感じで、大した上昇にはなりませんでした。

来年は、まず再入水して、水色で安定させることが目標。その先に入青まで目指せればという所でやっていきたいです。しかしながら、今年のレートの推移をみると、もうちょっと、精進のやり方を見直していかないと、これ以上の成長は無いかという感じなので、精進のやり方を見直すのが先決だなあという感じです。

ということで、また来年も頑張ります。

2023-12-12

HACK TO THE FUTURE 2024(AtCoder Heuristic Contest 027)参加記

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

2023/12/1〜2023/12/10に開催されたHACK TO THE FUTURE 2024(AtCoder Heuristic Contest 027)に参加しました。

atcoder.jp

ここ最近のAHCでは、ギリ水パフォか緑パフォを取ってしまうことが多く、自分の実力の無さを感じている状況です。

AHCは結果が悪くてもレートが下がらないので、なんとか青コーダーの地位を確保してますが、そろそろレート以上のパフォーマンスを出していかないとというところ。今回は青パフォ以上目指して挑んでみます。

参加します。最近、AHCの結果が悪いので、今回はレート以上のパフォを出したい。

HACK TO THE FUTURE 2024 （AtCoder Heuristic Contest 027） - AtCoder https://t.co/umzqY13pNb
— devgenjin77 (@devgenjin77) 2023年12月1日

今回の結果

26.7Gの484位で終了。今回も残念な結果になりました。

パフォーマンスは、ギリ水色という結果。前回は１上がりましたが、今回は２上がりました。

何もできず終了。。

devgenjin77さんのHACK TO THE FUTURE 2024 （AtCoder Heuristic Contest 027）での成績：484位
パフォーマンス：1247相当
レーティング：1619→1621 (+2) :)
Highestを更新しました！#AtCoder #HACKTOTHEFUTURE2024（AtCoderHeuristicContest027） https://t.co/XFAvNwf1gm
— devgenjin77 (@devgenjin77) 2023年12月11日

振り返り

今回も、初手の方針につまづいてしまい、スコアの改善もままならぬ状態となりました。

A問題

A - Recurring Cleaning Route

今回の方針の概要です。

#AHC027 #HTTF お疲れ様でした。
26.7Gで最終484位でした。。
サンプルで作った初期解を元に、早く１周が完了することを目標にしてみましたが、ハズレ方針だったようで、早い段階でスコアが頭打ちになってしまいました。
（添付：Seed=0 Score = 2550634）
また、次頑張ります。 pic.twitter.com/JXJplHPMPa
— devgenjin77 (@devgenjin77) 2023年12月11日

今回の問題は、ロボット掃除機を部屋中全てのマスを掃除するよう操作して、最終的に平均の汚れを少なくするという問題。

まず、部屋中全てを掃除する制約があるので、初期解を作るのも中々しんどそうだという印象。コンテスト開始より、初期解の構築に結構悩みながら実装が進まないという時間を過ごしていました。

しかし、そんなことしてるうちに、残り日数も徐々に少なくなって来たので、とりあえずサンプルのDFS実装をJavaに移植して１度提出。そして、ビジュアライザでサンプルの実行結果を観察してみると、汚れの少ないマスについてDFSの戻りターンでも清掃してるため、他の汚れが大きいマスで汚れが累積することが結果に悪影響を与えているのでは無いかという考えが浮かびました。

ということで、可能な限りDFSの戻りターンで形成される経路を省略できるような実装にし、全体として短いターンで１周回ることができるようにすればスコアが改善するのでは、と実装してみたら、予想通りスコアは改善されました。

が、、その後の改善アイデアが全くダメ。。経路を乱択にしてみたり、汚れの多いマスを２回回るようにしてみたりしてみましたが、スコアが改善の方向に向かわず、逆に悪化するばかりという状態に。。

最終日まで、このような状況から抜け出せなかったので、結局、一番スコアの良かった、なるべく早く１周する実装で最終提出とすることにしました。

最終提出コード

https://atcoder.jp/contests/ahc027/submissions/48408634

感想

今回も、初回の方針決定が誤っていた模様。経路を短くすることばかり考えていましたが、その考えに固執しすぎたのがよくなかった模様です。

これまでの実績

$2$ 上がりました。

総括

今回も、ハズレ方針を引きからのリカバリが効かなかったなあという感じです。

また、アイデアの試行が足りてないというのも、伸び悩みの原因かと。この結果にめげずに、他の上位解法を復習して、次に備えていこうと思います。

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

2023-12-12

AtCoder Beginner Contest 332参加記

AtCoder 競プロ ABC

2023/12/10に開催された、AtCoder Beginner Contest 332に参加しました。

atcoder.jp

土曜のARCでは、なんとか水パフォを確保して少しレートを戻すことができました。

しかしながら、直近ではABCだけでみると３連敗中。。精進不足ということもありますが、凡ミスのせいで順位を大きく落としてます。

今回は、なんとか連敗を止めようという感じで臨んでみます。

Rated参加します。
ABCだけで見ると３連敗中なので、今回はなんとか水パフォ以上取ってレートをあげていきたいです

AtCoder Beginner Contest 332 - AtCoder https://t.co/eEhP1bZcFB
— devgenjin77 (@devgenjin77) 2023年12月10日

今回の結果

E問題以降の難易度が高かったこともあり、４完で終了。Dは、もう少し早く解けてたなあという印象です。

パフォーマンスの方は、ギリ水色に到達。なんとかABCの連敗を止めることが出来ましたとさ。

４完確保でギリ勝ち😅
Dの解答時間で大分上下しそうな感じだが、一部勘違いがあって時間ロスしたのが悔やまれる。。

devgenjin77さんのAtCoder Beginner Contest 332での成績：1556位
パフォーマンス：1229相当
レーティング：1142→1151 (+9) :)#AtCoder #ABC332 https://t.co/z6i48NUF4v
— devgenjin77 (@devgenjin77) 2023年12月10日