みろくの精進日記

競プロに関することを主につづります

JOI2023/2024 2次予選参加記

皆様初めまして。みろくと申します。
もうすぐ本選の時期になってしまいましたが、プライベートが落ち着いてきたので、今更ながらJOI2023/2024の2次予選に参加した時のことについて書いていこうと思います。
問題についての説明はしないので、過去問ページを見ながら読むことを推奨します。

atcoder.jp

JOI2023/20242次予選問題の解法のネタバレを含みます！解いていない方はご注意ください！

1.結果

早速ですが、結果を述べてしまいます。
合計223点で、ボーダーラインの240点に17点届かず、予選Bランクとなりました。
ということで各問題について考えていたことや、思考の順序などに触れた後、反省などについて述べていこうと思います。

2.各問題の振り返り

A - カードゲーム 2 (Card Game 2)

最初は、隣り合う3要素がx,x+3,x+6になっているか順番に見ていくというコードを書いていたんですが、入力例4を実行して、間に違う要素が入るパターンがある！と気づき、急いでset/mapを使う解法に書き直してACしました。

B - 買い物 2 (Shopping 2)

今回一番多くの時間を使った問題です。 問題文を少し読んで、累積和だ！となりました。
しかしセール情報を取り入れるのにとても苦戦した末に、種類ごとの累積和とそれのどこまでがセールなのかを二分探索で探す、という方法をなんとか思いつき、実装したのですが、入力例が通らない。
二分探索の境界や、オーバーフローなど、何度も何度も修正を重ね、何とかACできました。

C - 白色光 2 (White Light 2)

今回の一番の反省点です。
問題を一目見て、DPっぽい？と思いました。
しかしこの時の私はナップサックDPを学び始めたぐらいの身。全く遷移も方針も思いつかず、小課題を解こう、と思いました。
そして小課題1,4,5は3の倍数まで消した後、埋めるだけだ！と思い、これらを通しました。
そして、最初のDPっぽさや、解法を全く思いつかない、という第一印象にとらわれ、消す範囲を全探索するだけの小課題2を見落としていたのです...

D - 庭園 2 (Garden 2)

Cを通せておらず、すでにこの時「とりあえず問題をすべて見よう」という気持ちだったので、問題を見て、ほぼ理解が出来ず、出力例を見て、小課題1だけ解こう、と思いました。
その結果小課題1の条件では(x,y) = (2,2)以外ではr=1にできない、と気づけず、すべてのマスからr=1にして全探索をしていたので通せず、0点でした。

E - 高速道路の通行料金 (Highway Tolls)

Dと同じく、すでに小課題の最初のほうを取ろう、と思っていたので、小課題1だけを見てダイクストラ法だ！と思い、手元の書籍からダイクストラ法を丸写ししたらサンプルすら通らず、慣れないアルゴリズムであるこれを詰めるよりCやDの小課題を考えるべきだ、と思い放置したため、0点でした。

3.反省

コンテスト中の反省

まず、コンテスト中の反省としては次の2つです。
1. 問題文をよく読まなかったこと
2. 小課題を解くため新しい解法を考える頭に切り替えられなかったこと

「問題文をよく読まなかったこと」については、主にA問題、D問題についてで、 しっかり問題文を読んでいればA問題で順番に見ていくだけでは通らないことも、D問題で中央だけ見ればいいことも気づけたはずでした。
一目見て楽そうでも、きっちり問題文を読むこと、そして逆に一目見て面倒そうでもちゃんと問題文を読もうとすることが大切だと思い知らされました。
「小課題を解くため新しい解法を考える頭に切り替えられなかったこと 」については完全にC問題です。一目見た時のDPっぽさ、そしてこれは解けなそうという感覚に囚われて、ただ消す範囲を全探索して、かかる金額を順番に計算するだけ、という小課題の解法を思いつくことが出来ませんでした。これを通せていれば本選出場できていた、と考えるといまだに引きずるほど悔しいです...
また、この小課題を通せなかった理由としてもう一つ、B問題が私にとってとても難しいと感じていたため、それを通せたことでもうかなりボーダーラインに近づけているんだろう、という油断が生じて必死さがB問題を考えていた時より欠けていたこともあると思います。

コンテスト前、精進についての反省

こちらは一つに絞りました。それは、
- バチャが足りなかった
これです。
精進が足りない、なんていうのは当たり前なのでそこからさらに踏み込んで考えた結果これにたどり着きました。
普段のAtcoderなどのコンテストのための精進をしても、難しい問題を簡単な制約で解くという小課題への取り組み方や、早解きではなく1点でも多くの得点を取りに行く、というJOIのための精進はできなかったのです。
実際ボーダーラインのB問題が解けているわけなので問題をACする能力は不足していなかったと思います。ということで、JOIで得点を取るために、バチャをしなかったことが今回の結果を招いたと考えます。

一つだけ言い訳をすると、今回の2次予選の1週間前まで、学校で定期テストだったんですよね...まあ相手も同年代なわけで条件は似たようなものだと思うんですが、そういうところはあったかもしれないです。ただテストがあるからと言ってずっと勉強していたわけではないので結局私の精進が足りなかったことに変わりはないですが...

4.まとめ

長々と書いてしまい申し訳ありません。
この記事を読んでいただいている高2以下の方には、是非、JOIに参加していただきたいです！私は今回が最初で最後の出場だったので、もう1年早く参加していたら...と思っています。出場料が必要なわけでもないですし、エントリーしてから勉強する時間もたっぷりある大会ですので、積極的に参加していただきたいと思います！
そして参加する際は、JOIのための精進をすることをお勧めします。受からなかった人の意見なのでほどほどに聞いてほしいですが、落ちた人間だからこそわかる部分もあると思います。せっかくここまで読んでいただけたのですから、これだけは覚えていただけると嬉しいです！

たくさんバチャをしましょう！！！

長くなってしまいましたがここまで読んでくださりありがとうございました！
私はパソコン甲子園で絶対に競プロ全国大会出場リベンジします！

AtCoder Beginner Contest 326参加記

前置き

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

atcoder.jp

今回はD問題、E問題ともに450点問題ということで、425点問題を先日のABC324で初めてコンテスト中ACしたばかりの私は、C問題をそれなりに早く解き緑パフォをとることを目標として、あわよくばDまたはE問題を解くことを目標としていました。

コンテスト結果

今回の結果は、約22分での3完で、パフォーマンスは848でした。 正確な値は記憶にありませんが、C問題を提出した時点で緑パフォギリギリで、4完しないと800に届かないのではないかと思いましたが、無事緑パフォをとることが出来ました。

各問題の解法、感想

A - 2UP3DOWN

atcoder.jp

まずxとyのどちらが大きいか判定し、 x \gt yなら x - y \le 3のとき、x \lt yならy - x \le 2のときに階段を利用する、
という方針でACをとりましたが、 x \gt yかx \lt yかを判定せずともy - xをすれば符号で判定できるので、-3 \le y - x \le 2を判定すればよかったですね...

B - 326-like Numbers

atcoder.jp

まず、その数が326-like numberかの判定部分は、各桁の抽出さえできれば、326-like numberである判定は、問題通り百の位の数と十の位の数の席が一の位の数と等しいかを判定すればよいと考えました。
制約から、入力が3桁なので、各桁の抽出はそれぞれ、
(百の位の数) = N / 100
(十の位の数) = N % 100 / 10
(一の位の数) = N % 10
で求められます。
あとは、Nが326-like numberであればNを出力、違えば1を足した数が326-like numberであるかを判定していくことでACを取れました。
　　

C - Peak

atcoder.jp

まず、区間について考えました。プレゼントが置かれている座標は0以上の整数なので、xを整数にしてもxを実数にしても、x以上の最小の整数から、x+M未満の最大の整数までのM個の整数にあるプレゼントを獲得することが出来ます。
続いて区間の左端(x の値)についてですが、任意のA_{i}のみとしてよいと考えました。これはxがA_{i-1}より大きくA_{i}未満にある場合ならxをA_{i}まで進めても獲得できなくなるプレゼントはないと考えられるからです。
このように区間の左端を決定するとA_{i}からA_{i}+M-1までの数字にあるプレゼントを獲得できることになります。
区間の位置の候補を決められたので、あとはその区間にいくつのプレゼントがあるかを調べますが、二重ループを用いてA_{i}からA_{i}+Mまで調べるとTLEすると考えられます。
座標0からA_{i}までのプレゼントの数をあらかじめ求めておく、累積和の解法も少し考えましたが、同じ座標にプレゼントがあったときにバグの原因になりそうだなと考えたため、二分探索を考えました。
前もってAをソートしておくことで二分探索を用いることが出来るので、 各A_{i}について、A_{i}+M以上の最小の座標にあるプレゼントを二分探索で求めます。これがj番目のプレゼントとすると、獲得できるプレゼントはj - i個となります。これをすべてのA_{i}に対して求め、最大値が答えとなります。
この解法の計算量はO(NlogN)なので、これでACをとることが出来ました。

提出したコード atcoder.jp

D - ABC Puzzle

atcoder.jp

この問題をC問題ACした後コンテスト中考えていましたが、通せませんでした...

まずNが5以下なので適切な全探索をすればよいのではないかと考え、DFSを用いた全探索をしました。各行と列において既に現れた文字をbit列で管理し、ABCを書くことが出来るなら「.」と書ける文字を書くパターンを試すというのを再帰的に繰り返していき、最後の文字までたどり着いたらR,Cの条件を満たすかどうかを確認するという方法をとりましたが、実行結果は4419msで、TLEでした。各行や各列で最後の文字で書くべき文字が二つ以上ある場合やR,Cを探索中に調べることで通るのではないかと考えましたが時間内に実装できませんでした。

TLEしてしまった提出 atcoder.jp

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

Dを解く前に少しだけ見ましたが、期待値mod 998244353という表記を見たことがなく、定義を見てもすぐ理解できなかったため、諦めてD問を解きました。

F,G

問題を見ていません...

まとめ

それなりのスピードでC問題を解くことができ、緑パフォも出せて満足のコンテストでしたがD問題の枝刈り全探索という問題に慣れておらず、あと少しの実行時間が縮められなかったため、くやしさが残るコンテストとなりました。E問題の期待値modも含めて、しっかり復習をして行きたいと思います。
また、今回解法をここまで書いてきたわけですが、かなり文字数の多い記事となってしまったため、次回からは解法というより感想を書いていくほうが良いのか迷っています。よろしければコメントまたはtwitterの方にてご意見くださるとありがたいです！

ブログ始めてみました

1.自己紹介

皆様初めまして！みろく(@tellfar)と申します。 今年の3月頃に競プロを本格的にやり始め、アウトプットの場が欲しいなと思いはてなブログをはじめてみました。今は主にatcoderで毎週ABCに参加したり、過去問を解いたりしています。
1月ほど前に入茶した茶コーダーで、現在は入緑することと、JOI本線出場することを目標に精進を頑張っています！
こちらがatcoderアカウントページです
harun210 - AtCoder

2.これから書きたいこと

主に、毎週のABCの参加記、過去問の精進記録などを書いていくと思います。また、かなり時間がたってしまっていますが入茶記事なんかも書ければいいなと思っています。

3.さいごに

ブログを通じて人に伝えられる文を書けるようになることと、競プロを上手くなることを目標としているので、読みづらい文、間違っている部分、意見や感想などあれば気軽にコメントしてくださるととてもうれしいです！
ここまで読んでくださりありがとうございました！