2023-10-24

AtCoder Heuristic Contest 025 参加記

2023/10/14〜2023/10/22に開催されたAtCoder Heuristic Contest 025に参加しました。

ヒューリスティックのレートは入青直前という状況でありながら、ここ数回のAHCでは残念な結果しか出ずで足踏みが続いている状況です。とりあえず、今回こそは入青を決めようという気持ちで挑みました。

参加します。
AHCでは最近良い結果が出てないですが、なんとか今回でHeuristic入青を決められるように頑張ります

AtCoder Heuristic Contest 025 - AtCoder https://t.co/qSRbNa6AGJ
— devgenjin77 (@devgenjin77) 2023年10月14日

今回の結果

最終196位で終了。ここ最近のAHCでは、比較的良好な結果でした。

パフォーマンスは、なんとか青色を達成。念願の入青を達成することができました。

青パフォ取って、Heuristicは入青しました！😂
devgenjin77さんのAtCoder Heuristic Contest 025での成績：196位
パフォーマンス：1738相当
レーティング：1576→1618 (+42) :)
Highestを更新し、2 級になりました！#AtCoder #AtCoderHeuristicContest025 https://t.co/nXpNlU2bg9
— devgenjin77 (@devgenjin77) 2023年10月23日

振り返り

個人的にはかなり頑張ったつもりでしたが、終わってみると色々改善の余地はあるかなあという内容でした。

A問題

A - Balancing by Balance

とりあえず、今回の方針の概要です。

#AHC025 お疲れ様でした。
最終結果196位でした。
基本方針としては、未配置の最も重い商品を、最も軽い袋に入れるを繰り返し、クエリが余ったら細かい交換をして改善を試みるをしました。

GIFはSeed=4で811865点。
それなりに上手く出せたつもりでしたが、上には上がいるもんだと思いました。 pic.twitter.com/IiVd40oQqW
— devgenjin77 (@devgenjin77) 2023年10月23日

まずは、各袋の重さの分散を最小化する方法のアイデア出しからです。

アイテムの重さが分かっていればランダムの初期解から焼きなましが効くんだろうが、今回は大小関係ぐらいしか分からんということで、これは難しいだろうと。

で、色々考えた所、とりあえず重たいアイテムから順に軽い袋に入れる貪欲を試してみることに。これがテストデータを元に検証してみると、それなりの結果が出たので、大体この方針で行こうと決めました。

未使用のアイテムのうち、重いアイテムを取る方法としては、未使用のアイテムを２グループに分けて１回比較し、軽い方を排除する操作を繰り返し、残った１つを最も重いアイテムとする方法を採用。

この方法だと、厳密には最も重いものが取れない可能性もあるのですが、クエリ回数を抑えつつ大体重たいものを引っ張ってくるにはいい方法かと考えました。なお、軽い袋を取ってくる方法も同じような考え方です。

どうしても十分なクエリ回数がないケースでは、ある程度ランダムに配置するしか無いのですが、その場合は前半の方で、できるだけ複数個まとめて配置し、後半にかけてちゃんと計測していくなどの工夫を実施。

最後の方は、この辺のバランス調整を色々やって、小手先の工夫では限界だと感じたところで終了としました。

ちなみに、最も軽い袋に対して、別の袋からアイテムを一個移動し、移動後の大小関係が変わらない場合は必ずスコアが改善されるという考え方から、クエリ回数が余るケースでは、この操作をできるだけ実行したのですが、気持ち程度の改善にしかなってなかったようです。

最終提出コード

https://atcoder.jp/contests/ahc025/submissions/46859842

感想

コンテスト後のTLを見てみると、実際の重さを推測する方法があるということで驚きでした。改めていろんな解法があるものだと感心しきりです。
比較方法については、全然改善の余地があったという感じ。特に袋のソートを完全にしていれば、スコア改善の余地はまだまだあったと思ってます。

これまでの実績

とりあえずヒューリスティック入青です。

総括

今回は、そこそこ良い成績が取れた方でしたが、ここから上を目指すには、まだまだ知識が足りないなというのが率直な感想です。

今後の目標としては、入黄を目指していく感じになるというところ。道のりは長くなりそうですが、引き続き精進していきます。

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

2023-10-23

キーエンスプログラミングコンテスト2023秋(AtCoder Beginner Contest 325)参加記

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

2023/10/21に開催された、キーエンスプログラミングコンテスト2023秋(AtCoder Beginner Contest 325)に参加しました。

atcoder.jp

今週は長期AHCの開催期間だったので、アルゴリズムの精進は程々にAHCの考察と実装に取り組んでいたのですが、ABCにはきちんと参加することに。

とりあえず、再入水に向けて、水パフォ目標で挑むこととしました。

AHCの途中ですが、Rated参加します。
再入水に向けて、水パフォ目標で頑張ります✊

キーエンスプログラミングコンテスト2023秋（AtCoder Beginner Contest 325） - AtCoder https://t.co/glOZTxgIGf
— devgenjin77 (@devgenjin77) 2023年10月21日

今回の結果

なんとか、５完を確保しました。

久しぶりの３桁順位ということで、青パフォもあるかなという期待もありましたが、結果は少し及ばすで水パフォ。

それでも、レートは大幅に回復して、なんとかギリギリで再入水を果たすことが出来ました。

５完水パフォで再入水！😂😂
devgenjin77さんのキーエンスプログラミングコンテスト2023秋（AtCoder Beginner Contest 325）での成績：857位
パフォーマンス：1529相当
レーティング：1162→1204 (+42) :)#AtCoder #キーエンスプログラミングコンテスト2023秋（ABC325） https://t.co/AOG8buQ2P3
— devgenjin77 (@devgenjin77) 2023年10月21日

振り返り

Dで多少詰まったことを除けば、概ね良い内容でした。

A問題

A - Takahashi san

文字列 $S$ の後ろにsanを付けるだけ。

今までやってきたA問題の中でも、最も簡単な部類に入る問題という感じだったので、テストもせずに投げました。51秒で1完。

提出コード

https://atcoder.jp/contests/abc325/submissions/46790739

B問題

B - World Meeting

世界標準時で $0$ 時開始から $1$ 時間刻みに $23$ 時開始までの $24$ パターンについて、それぞれ参加できる拠点の人数を足し合わせた合計の最大を答えれば良い。

これもやるだけの実装でACでした。5分58秒で2完です。

提出コード

https://atcoder.jp/contests/abc325/submissions/46797528

C問題

C - Sensors

見た目の感じ、Union-Findを使うやつかなあと思ったので、素直に連結をUnion-Findで管理する方針としました。

まずは、それぞれのマス目について、#のマスの上下左右斜めのマスが#だった場合、Union-Findで連結させる。

あとは#の連結成分が何個かが分かれば良い。#のマスについてUnion-Find上のleader関数の値をSetに格納して、最後にサイズを出力する実装としました。

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

提出コード

https://atcoder.jp/contests/abc325/submissions/46803592

D問題

D - Printing Machine

最初、区間スケジューリング問題の変形みたいな感じだと思ったので、とりあえず後ろから印字する方向で考えてみました。

考え方としては、印刷範囲から出るのが遅い順、次に印刷範囲に入るのが遅い順から優先して印字していけば良いだろうという感じ。

まず、印刷範囲から出る順の降順の優先度付きキューに全商品を入れておき、次に印刷範囲に入る順の降順の優先度付きキューを空で用意する。

次に後者のキューが空の場合、前者のキューの先頭の終了時刻と同じ終了時刻の商品を後者のキューに入れる。

最後に、後者のキューの先頭から見て、前回印字した時刻より前の時刻で印字可能であれば可能な限り最大の時刻で印字する。出来ない場合はキューから捨てる。

この要領で、前者のキューが空になるまで処理を行い、最終的に印字できた商品数を出力すればOKという感じです。

考察と実装にやたら時間が取られましたが、なんとかACを確保。63分36秒で4完です。

提出コード

https://atcoder.jp/contests/abc325/submissions/46820361

E問題

E - Our clients, please wait a moment

車から電車に乗り換えるのが１回だけということで、都市 $1$ から各都市に車だけで移動した時の最短距離と、都市 $N$ から各都市に電車だけで移動した時の最短距離をそれぞれダイクストラで求めておき、あとはどこで乗り換えるのかを全探索すれば良いかという感じの問題でした。

実装も問題なく完了し、なんとかACを確保。80分30秒で5完。

とりあえず、この時点で順位は８００台あたりというところで、勝ちは確定したという状況でした。

提出コード

https://atcoder.jp/contests/abc325/submissions/46824850

F問題

F - Sensor Optimization Dilemma

２０分弱という残り時間ながらも、とりあえず挑戦してみることに。

見た目上、とりあえず難し目のDPという感じ。制約から察するに、 $dp\lbrack i \rbrack \lbrack j \rbrack \lbrack k \rbrack :=$ $i$ 個目の区間まで見て、センサー１が $j$ 個かつ、センサー２が $k$ 個の場合の最小コストというのを考えてみましたが、これだと全然計算量が抑えられてないということ気付いたところで時間切れとなりました。

G問題

G - offence

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

これまでの実績

２回目の再入水を果たしました。今度こそ、緑落ちしないようにしないと。。

総括

全体的に出来が良かった回でしたが、これでも水パフォが精一杯かという印象です。

今後、入青を目指していくためには、今回のようなセットで６完以上狙えるレベルまで実力を上げていきたいところ。引き続き、今回の復習を含め、精進を継続していきたいと思います。

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

2023-10-17

AtCoder Regular Contest 167 参加記

AtCoder 競プロ ARC

2023/10/15に開催されたAtCoder Regular Contest 167に参加しました。

atcoder.jp

先週のARCで０完爆死をしてしまい、一気に緑落ちという仕打ちを喰らいましたが、今回のARCもRated参加で挑むこととしました。

今回、大勝ちできれば再度の入水が果たせるという状況。とりあえず、２完を目標とします。

先週、０完了爆死しましたが、今週も懲りずにRated参加します。
２完以上取って再入水できるよう頑張ります✊

AtCoder Regular Contest 167 - AtCoder https://t.co/M0l5dGPG66
— devgenjin77 (@devgenjin77) 2023年10月15日

今回の結果

１完で終了。２完を達成することはできませんでした。

パフォーマンスは、緑の中間辺り。結局、今回のARCも負けてしまいました。。

１完緑パフォで終了でした。
また次回も頑張ります。

devgenjin77さんのAtCoder Regular Contest 167での成績：1634位
パフォーマンス：1016相当
レーティング：1177→1162 (-15) :(#AtCoder #ARC167 https://t.co/4yyTcJlEhz
— devgenjin77 (@devgenjin77) 2023年10月15日

振り返り

B問題を解き切る事ができませんでした。

A問題

A - Toasts for Breakfast Party

最初、二分探索で解くかと思ったりもしましたが、普通に貪欲で解けるやつでした。

先ず $A$ をソートして、大きい方から $M$ 個の要素を順に皿に配置していく。次に、余った要素から大きい順に、既に皿に置いている美味しさが小さい皿に対して配置していけば良い。

普通に実装して、ACが取れましたとさ。13分40秒で1完。

とりあえず、２連続の０完爆死は阻止できて一安心という所です。

提出コード

https://atcoder.jp/contests/arc167/submissions/46626440

B問題

B - Product of Divisors

なんか苦手の数学問題という感じでしたが、時間があるのでなんとか解き切れればという感じで挑んでみます。

法則性がよくわからんので、一応、小さい数字で貪欲解を出してみたが、さらによくわからん感じに。。

とりあえず、 $A$ を素因数分解してみて、実際に $B$ 乗してみると、約数の個数は、各素因数の次数に $1$ を足した時の総積になる。すると、まず $1$ から素因数の最小次数の $B$ 乗までの総和に対して先ほどの総積かけてみればそれなりに近い値がでるかなあと思い、いざ実装してみたら、なんとサンプルが通ってくれました！

が、、これを提出してみると結局WAで終了。

結局、時間いっぱい格闘したものの、この問題を解くことはできませんでした。

後で解説を見ると、約数の総積は公式で求められるとの事。一応ググっていればワンチャンあったので、ちゃんと調べる作業をしておくべきでした。

C問題

C - MST on Line++

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

D問題

D - Good Permutation

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

E問題

E - One Square in a Triangle

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

F問題

F - Tree Tree Tree

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

これまでの実績

ARCでなかなか勝てません。

総括

B問題は、大分難しめの問題でしたが、一応ある程度の考察が出来ていたようなので、その点では昔よりも成長があったと思う次第。

考察力をもっとつけて、次回のARCは高パフォーマンスを取れるように精進していきます。

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

2023-10-15

日本レジストリサービス（JPRS）プログラミングコンテスト2023(AtCoder Beginner Contest 324)参加記

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

2023/10/14に開催された、日本レジストリサービス（JPRS）プログラミングコンテスト2023(AtCoder Beginner Contest 324)に参加しました。

atcoder.jp

先週は、ABC、ARCと、立て続けに惨敗してしまい、あっという間の緑落ちを喰らってしまいました。

再度の入水に向けて地道にレートを稼いでいこうということで、今回も水パフォ目標で頑張っていきます。

Rated参加します。
先週で緑落ちしてしまったので、再度入水に向けて頑張ります✊

日本レジストリサービス（JPRS）プログラミングコンテスト2023（AtCoder Beginner Contest 324） - AtCoder https://t.co/gwQUK9y1qH
— devgenjin77 (@devgenjin77) 2023年10月14日

今回の結果

なんとか５完を達成しました。

パフォーマンスは、水色中間というところ。再度の入水に近づくことが出来ました。

５完水パフォでした😃
devgenjin77さんの日本レジストリサービス（JPRS）プログラミングコンテスト2023（AtCoder Beginner Contest 324）での成績：1298位
パフォーマンス：1398相当
レーティング：1149→1177 (+28) :)#AtCoder #ABC324 https://t.co/JxlnSHItqB
— devgenjin77 (@devgenjin77) 2023年10月14日

振り返り

相変わらず、小さいミスが続いてしまったことが反省材料です。

A問題

A - Same

数列 $A$ の値が全て同じかを判定する問題。ループで判定すれば良いので、やるだけの実装をしました。1分17秒で1完。

提出コード

https://atcoder.jp/contests/abc324/submissions/46521548

B問題

B - 3-smooth Numbers

$N$ を $2$ と $3$ で割れるだけ割った後、 $1$ になっているかを判定すれば良い。

これもやるだけの実装でACが取れました。2分56秒で2完です。

提出コード

https://atcoder.jp/contests/abc324/submissions/46526045

C問題

C - Error Correction

文字列 $S_i$ が、文字列 $T$ と最大１文字違いであるのかを判定する問題。

愚直に判定していくしかなさそうで、なかなかシンプルに実装するのが難しそうな感じ。

仕方なく、 $|S_i| = |T|$ の場合、 $|S_i| = |T| + 1$ の場合、 $|S_i| + 1 = |T|$ の場合それぞれでループを回し、最大１文字違いなのかを判定する実装をしました。

初回の提出では、答えが０件の場合を考慮できておらず、REを喰らいましたが、修正してなんとかAC。23分10秒1ペナで3完です。

提出コード

https://atcoder.jp/contests/abc324/submissions/46544237

D問題

D - Square Permutation

平方数を全探索して、問題の条件に合うように各ケタの数字の数が合っているかを判定していけば解けるだろうという感じの問題。

で、実装して提出してみたら、惜しいところで１WA。。

直感で、 $0$ のケースが抜けてるのかと思い、ググってみると、 $0$ も平方数に入るとのこと。こういうケアレスミスもなんとかしないといけないなあと。

とりあえず、修正してなんとかAC。37分15秒2ペナで4完でした。

提出コード

https://atcoder.jp/contests/abc324/submissions/46553939

E問題

E - Joint Two Strings

最初、難しめの文字列アルゴリズムを使うやつかとおもってましたが、よくよく考えると、単純に解ける問題だとわかりました。

文字列 $S_i$ が $T$ を先頭または末尾から見て、最大何文字を部分文字列として含んでいるかが分かれば、あとは単純な計算で解ける筈。

具体的には、

数列 $A$ を $A_k:=$ 配列 $S$ のうち、 $T$ と $S_i$ をそれぞれ先頭から見て、最大 $k$ 文字を部分文字列として含んでいる文字列の個数とする。
数列 $B$ を $B_k:=$ 配列 $S$ のうち、 $T$ と $S_i$ をそれぞれ末尾から見て、最大 $k$ 文字を部分文字列として含んでいる文字列の個数とする。
連結の先頭にする文字列が、 $T$ の先頭から $k$ 文字を部分文字列に含んでいるとすると、連結の末尾には $T$ の末尾から $|T| - k$ 文字以上を部分文字列に含んでいれば良い。
数列 $A$ でループし、上記の考え方で、答えに足し込んでいく。累積和を使えば、計算量は $O(N)$ に収まる。

という感じの実装でACが取れましたとさ。

70分44秒2ペナで5完。とりあえず、今回は下げは無さそうです。

提出コード

https://atcoder.jp/contests/abc324/submissions/46571551

F問題

F - Beautiful Path

なんか途中の平均値の大小でダイクストラ法を使って解けないかという感じだったので、実装してみたところ、サンプルまではなんとか通せました。

しかし、提出してみると、TLEとWAを連発してしまい、結局解けずじまい。ここで時間切れになりました。

G問題

G - Generate Arrays

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

これまでの実績

先週の大負け分を、少し取り戻しました。このまま再度の入水を狙います。

総括

F問題が解けなかったのは、仕方なしにせよ、凡ミスでの２ペナが痛かったかなあという印象です。

そのうち１個はサンプルを通していれば防げたミスだけに残念な感じがします。C問題までは早めの提出をするためにサンプルのテストは省略していたのですが、ちょっとその戦略は考え直した方がいいかなあという感じです。

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

2023-10-09

AtCoder Regular Contest 166 参加記

AtCoder 競プロ ARC

2023/10/8に開催されたAtCoder Regular Contest 166に参加しました。

atcoder.jp

土曜のABCは、３完緑パフォという残念な結果で、レートの方は緑落ち間近というところまで落ちてしまいました。

今回負けを喰らえば、即緑落ちというところですが、これまでも目先のレートを守るためにUnratedで参加する意味もないという考えでやって来たので、今回もRated参加します。

配点を見ると、２完行かないと水パフォは厳しいかという感じなので、２完目標で挑むこととしました。

Rated参加します。
爆死で即緑落ちという状況ですが、なんとか２完以上確保してレートを上げられるように頑張ります✊

AtCoder Regular Contest 166 - AtCoder https://t.co/ecCQ1tawHI
— devgenjin77 (@devgenjin77) 2023年10月8日

今回の結果

結局、０完爆死を喰らってしまいました（泣）

今回の０完は灰パフォということで、レートの方は大きく下落。またまた緑コーダーの身分に戻ることとなりましたとさ。

結局０完爆死を喰らい、緑落ちしました😭😭
また、再入水できるように頑張ります

devgenjin77さんのAtCoder Regular Contest 166での成績：1609位
パフォーマンス：354相当
レーティング：1216→1153 (-63) :(#AtCoder #ARC166 https://t.co/Fxg7AFpGdG
— devgenjin77 (@devgenjin77) 2023年10月8日

振り返り

Aはともかくとして、BのREを解決することが出来なかったのが残念でした。

A問題

A - Replace C or Swap AB

C→A、C→B、AB→BA、以上3種類の操作を繰り返すことで、文字列 $X$ を文字列 $Y$ にすることができるかという問題。

最初の方、BA→ABの操作も可能と誤読したせいで、誤った実装方針で突き進んでしまいました。

当初の実装方針としては、

$X$ の文字をCにすることができないので、 $Y_i$ がCで、 $X_i$ がCでない場合はNG。
$Y$ の文字をCで区切った範囲で $X$ を見た時、それぞれの文字列を、 $X(i, j)$ 、 $Y(i, j)$ とすると、 $X(i, j)$ 上のAの文字数が、 $Y(i, j)$ のAの文字数を超えるか、 $X(i, j)$ 上のBの文字数が、 $Y(i, j)$ のBの文字数を超える場合はNG。

という感じで組んでましたが、サンプルが通らなかったタイミングで、結局、文字の移動がAB→BA一方通行になるのでこれではダメということに気づきました。

方針は半分合ってそうな気がするので、あとはAB→BAの操作に限定された時にどのような判定をすべきかというところなのですが、これが思いつかず。

色々悩んでるうちに、コンテスト時間の半分を使ってしまったので、一旦飛ばしてB問題に取り組むこととしました。

B問題

B - Make Multiples

相異なる $i,j,k$ について、 $A_i$ を $a$ の倍数、 $A_j$ を $b$ の倍数、 $A_k$ を $c$ の倍数にする操作をしたときの最小操作回数。
相異なる $i,j$ について、 $A_i$ を $lcm(a,b)$ の倍数、 $A_j$ を $c$ の倍数にする操作をしたときの最小操作回数。
相異なる $i,j$ について、 $A_i$ を $lcm(a,c)$ の倍数、 $A_j$ を $b$ の倍数にする操作をしたときの最小操作回数。
相異なる $i,j$ について、 $A_i$ を $lcm(b,c)$ の倍数、 $A_j$ を $a$ の倍数にする操作をしたときの最小操作回数。
$A_i$ を $lcm(a,b,c)$ 倍数にする操作をしたときの最小操作回数。

以上の操作回数から最小のものを選ベば良いだろうというのが方針として見えて来たので、あとは実装するだけ。

最初は、配列 $A$ に対して、前記の7種類の操作回数をそれぞれ愚直に計算して、それぞれ操作回数で降順ソートしてから、先頭の高々３要素を引っ張ってきて全探索すれば良いかということで組んでみました。

が、これを提出してみたら、なぜかRE。。。

当初、 $N$ 要素について７種類全ての操作回数を計算したあとソートしているので、メモリの食い過ぎかと思い、途中で不要になった配列を廃棄したり、GCをかましてみたりしましたが、全くREが取れず。

結局、このREが取れないまま、時間切れを迎えてしまいました。

で、後で振り返ってみると、REの原因は単なる配列外参照ということが判明。。

このバグをとっておけば、最初の７種の操作回数全てソートでも普通に通っていたようです。サンプルのテスト結果を普通に確認できていれば防げたバグだけに、悔やまれます。

C問題

C - LU / RD Marking

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

D問題

D - Interval Counts

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

E問題

E - Fizz Buzz Difference

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

F問題

F - Tangent Addition Formula

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

これまでの実績

この土日で、レートを99落としてしまいました。。

総括

A問題は、自分の考察力不足で解けず。B問題は、自分の単純ミスで解けずということで、まだまだ足りない部分があるということを痛感した回でした。

今回は惨敗しましたが、また水色コーダーに戻れるように、今回の復習を含め、日々精進していきます。

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

2023-10-08

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

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

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

atcoder.jp

先週のABCは、水パフォ真ん中あたりという結果で、レートの方は１回爆死したぐらいでは緑落ちしないぐらいまで伸ばすことが出来ました。

今週も、順調にレートを伸ばしていこうということで、水パフォ目標で挑みます。

Rated参加します。今回も水パフォ目標で頑張ります✊

ユニークビジョンプログラミングコンテスト2023 秋 (AtCoder Beginner Contest 323) - AtCoder https://t.co/xYLQgBkZK2
— devgenjin77 (@devgenjin77) 2023年10月7日

今回の結果

３完で終了です。。

パフォーマンスは、なんとか緑色を確保。レートは暴落しましたが、なんとか水色で耐えたというところです。

３完で冷え😭😭
devgenjin77さんのユニークビジョンプログラミングコンテスト2023 秋 (AtCoder Beginner Contest 323)での成績：4051位
パフォーマンス：820相当
レーティング：1252→1216 (-36) :(#AtCoder #ユニークビジョンプログラミングコンテスト2023秋(ABC323) https://t.co/M5tR5HfTGs
— devgenjin77 (@devgenjin77) 2023年10月7日

振り返り

D問題で大きくハマってしまいました。。

A問題

A - Weak Beats

$S$ の偶数文字目が全部0かどうかを判定する問題。

愚直にループで判定すれば良いので、やるだけの実装をしました。2分16秒で1完。

提出コード

https://atcoder.jp/contests/abc323/submissions/46281812

B問題

B - Round-Robin Tournament

$N$ 人のプレイヤーについて、勝利数の降順、プレイヤーの番号の昇順で並び替えるだけの問題。

ソートの典型問題みたいなものなので、こちらもやるだけの実装をしました。9分0秒で2完です。

提出コード

https://atcoder.jp/contests/abc323/submissions/46290913

C問題

C - World Tour Finals

各プレイヤーの得点と、全体の最高得点を予め計算しておく。

あとは、各プレイヤーについて、最高得点のプレイヤーは0、それ以外のプレイヤーは、最高得点を超えるには何問解けばいいかを、未解答の問題の点数の降順で見ていけば良い。

という感じで解ければ良かったのですが、初回提出はソートの順番を間違ってしまい、１WAを喰らいました。。

修正して、なんとかAC。21分19秒1ペナで3完です。

提出コード

https://atcoder.jp/contests/abc323/submissions/46304412

D問題

D - Merge Slimes

あまり見たことがないような問題だったので、戸惑いましたが、順位表を見ると大分解かれている問題なので、なんとかACは取っておきたい問題という感じです。

とりあえず、愚直に解いていくなら、スライムのサイズ $S$ とその数 $C$ をMapで管理しておき、サイズの小さい順から見ていけば良いかなあと。

次に、サイズの昇順で見た場合、各サイズについて２匹以上いる場合は合成すれば良い。数が奇数の場合は１匹合成できない個体が余るので、それを答えに足していく。合成できた個体については、サイズ $S$ の２倍になるので、Map上で足し合わせていく。

サイズの小さい順に見ていくためには、優先度付きキューでサイズを管理しておけば良いかという感じでなんとかサンプルが通る実装が出来ました。

が、、これを提出してみると、残念ながらTLE。。。

その後は、処理する順番を入れ替えするなど色々いじってみましたが、結果は出ず。結局この問題は一旦撤退することにしました。

E問題

E - Playlist

見た目、確率計算をDPでやるような感じがする問題だが、肝心のDP配列と遷移が思いつかない。。

とりあえず、 $dp \lbrack i \rbrack \lbrack j \rbrack :=$ $i$ 秒の時点で、曲 $j$ が流れている確率、という感じのDPがいけるかと思ったが、実装してみたら全くサンプルすら通らず。

結局、この問題を通せずに時間切れになりましたとさ。

F問題

F - Push and Carry

本番中は目を通していなかったのですが、今見たら本番でもワンチャン解けてたかなあという問題でした。

D、Eで詰まっている状況だったので、Fにも目を通しておいた方がよかったかなあという感じです。

G問題

G - Inversion of Tree

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

これまでの実績

水色安全圏まで上げたつもりが、もう一回爆死を喰らったら緑落ちという状況になってしまいました。

総括

今回、改めて見ると、F問題までは高度なアルゴリズムの知識が必要ない感じだったのですが、大負けしたのは、まだまだ実装力が不足しているということかもしれません。

今回通せなかった問題については復習して、理解を深めていこうと思います。

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

2023-10-01

AtCoder Beginner Contest 322参加記

AtCoder 競プロ ABC

2023/9/30に開催された、AtCoder Beginner Contest 322に参加しました。

atcoder.jp

再入水以降は、なんとか水色レートは維持できているものの、直近のレートは1224というところで、まだまだ一発爆死で緑落ちしかねない位置にいます。

まず、目先はなんとか水色安全圏ぐらいには行きたいところ。今回も水パフォ取って、Highest更新していこうという気持ちで挑みます。

Rated参加します。
水パフォ目指して頑張ります✊

AtCoder Beginner Contest 322 - AtCoder https://t.co/4tK0GOSMiL
— devgenjin77 (@devgenjin77) 2023年9月30日

今回の結果

Dに苦戦したものの、なんとか５完確保しました。

パフォーマンスの方は、余裕で水色に到達出来ており、レートの方もHighestを更新することが出来ましたとさ。

５完水パフォでHighest更新😂
次回も頑張ります✊

devgenjin77さんのAtCoder Beginner Contest 322での成績：1154位
パフォーマンス：1478相当
レーティング：1224→1252 (+28) :)
Highestを更新しました！#AtCoder #ABC322 https://t.co/Pc1yglmqeH
— devgenjin77 (@devgenjin77) 2023年9月30日

振り返り

AからCが簡単目でしたが、D、E問題が実装重めで、だいぶ苦労しました。

A問題

A - First ABC 2

Javaだと、indexOfを使うだけで解ける問題でした。1分4秒で1完。

提出コード

https://atcoder.jp/contests/abc322/submissions/46057216

B問題

B - Prefix and Suffix

Javaだと、startsWithとendsWithを使って解ける問題でした。4分10秒で2完。

提出コード

https://atcoder.jp/contests/abc322/submissions/46062857

C問題

C - Festival

まず、解答用にサイズ $N$ の配列 $Ans$ を作っておき、-1で初期化する。

次に、花火の打ち上がる日について、解答用の配列 $Ans$ に0を設定する。

あとは、 $N - 1$ 日目から $1$ 日目にかけて処理していき、 $Ans(i) = -1$ であれば、 $Ans(i) = Ans(i + 1) + 1$ というように、翌日の値プラス１を入れれば良い。

ということで、軽めの実装でACが取れました。8分51秒で3完です。

提出コード

https://atcoder.jp/contests/abc322/submissions/46070083

D問題

D - Polyomino

問題を読んだ瞬間、これは実装重めの全探索という感じでした。なんかハマりそうな嫌な予感しかしないので、一旦、この問題はスキップすることに。

で、その後E問題が解けて、F問題が解ける見込みがなさそうという事で、D問題に取り組むことに。以下の要領で、頑張って全探索を実装しました。

#の合計をカウントし、16でない場合はNoとする。
３つのピースについて、回転の $4$ パターン $\times$ タテの並行移動が $-3$ から $+3$ の $7$ パターン $\times$ ヨコの並行移動が $-3$ から $+3$ の $7$ パターンを全探索。
上記のうち、#が外にはみ出るパターンや、枠内で#が重なってしまうパターンは除外することで枝刈りを行う。
最終的に、枠内全てが#で埋まればYes