AtCoder Regular Contest 155 参加記

2023/1/29に開催されたAtCoder Regular Contest 155に参加しました。

atcoder.jp

今年に入ってから2回あったARCでは、いずれも1完で終了という体たらく。さらに、今回はA問題から400点ということで、1完できるかも不安という状況でした。

しかし、今回なんとか1完を確保して、その上で2完以上取れれば入水に大きく近づけるというチャンスでもあるので、目標は高く2完をとるぞという気持ちで臨むこととしました。

今回の結果

なんと、今回は0完という結果。。。

ARC155結果
ARC155結果

パフォーマンスは茶色の下の方。昨日のABCで稼いだレートを全部吐き出す結果になりましたとさ。。

振り返り

時間いっぱい使ってA問題に取り組んだものの、ACを取り切ることはできませんでした。

ARC155提出結果
ARC155提出結果

A問題

A - ST and TS Palindrome

初期の見通しとしては、NKの大小関係で判別するのかなという印象。

まず、N = Kの場合は、Sを反転させた文字列をS^{\prime}にすればどちらの順で繋げても回文になるのでYesでよい。

次に、N \gt Kの場合は、Sの先頭K文字を反転させた文字列をS^{\prime}にするしかない。どちらの順に繋げても回文になるかを愚直に判定する。

最後に、N \lt Kの場合が一番ややこしい。机上でいろいろシミュレーションしてみると、S^{\prime}の末尾がSを反転したものになり、次にS^{\prime}の先頭がS^{\prime}Sと埋まっていく感じになるので、最終的に残った部分がどうなるかを計算する感じになるのかもしれない。

この残った部分の長さとしては、(K - N) \% (2N)になるので、あとはこの部分が回文になれば良い??回文チェックは、N \gt Kの場合を流用して組み込んでみれば上手くいきそう?

ということで、実装をしてみたら一応サンプルはAC。が、、肝心の本番が通らない。。。

A問題以外の問題をみても、ちょっとACの見込みはなさげ。。ということで、時間いっぱい、なぜ通らないかを考えてみましたが、力及ばず。結局時間切れになってしまいました。

B問題

B - Abs Abs Function

A問題を諦めかけたところで、一度問題をチラ見したものの、よくわからんという感じで考察すらできておりません。

C問題

C - Even Sum Triplet

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

D問題

D - Avoid Coprime Game

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

E問題

E - Split and Square

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

F問題

F - Directable as Desired

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

これまでの実績

土曜でレートを稼いだと思ったら、日曜で稼いだ分以上に吐き出すという結果。停滞モードは、まだまだ続きそうです。

コンテスト実績
コンテスト実績

総括

今回のA問題とB問題は自力で解いてみたいというところで、実はまだ解説をみていない状況。今後のために、自分で考えて答えを出す練習をしていきます。

今回のARCは残念な結果でしたが、結果よりは次に向けて精進を積み重ねることが大事。レートは後からついてくるだろうという思いで、まだ次に向けて準備していきたいと思います。

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

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

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

atcoder.jp

先週はABC、ARCと立て続けに残念な結果になってしまい、レートの方は1100台を切ってしまう状態に。。

今回も負けを喰らうと、4桁レート維持も厳しくなるかというところ。ここいらで連敗を止めようという気持ちで臨む事としました。

今回の結果

有言実行!今回は、なんとか5完を確保することができましたとさ。

ABC287結果
ABC287結果

タイムは結構早めだったので、水パフォが出てくれました。これで先週の負けを大分取り戻せました。

振り返り

B問題で少しやらかしましたが、概ね早いペースで5完まで行くことができました。

ABC287提出結果
ABC287提出結果

A問題

A - Majority

Forの数を2倍した値が、Nより大きければYes、それ以外はNoという感じで実装。

問題なく、提出一発でACが取れましたとさ。

1分35秒で1完。

提出コード

https://atcoder.jp/contests/abc287/submissions/38375909

B問題

B - Postal Card

N \times Mパターンの全探索を行なっても、十分足りるような制約のため、シンプルにendsWithメソッドがTrueになるかの全探索で実装。

ここで、変数のnmの配置をミスってしまい、初回提出で1ペナ。そのあと修正してなんとかACが取れましたとさ。

6分20秒1ペナで2完。最近、ポカミスが増えたような気がする。反省しないとなあ。

提出コード

https://atcoder.jp/contests/abc287/submissions/38383315

C問題

C - Path Graph?

最初、パスグラフというのが何のことかよくわからなかったので、とりあえずググってみる。で、ようは一本道になっているグラフのことだということで解決。

本題に戻って、パスグラフの判定方法としては、

  • 次数が1の頂点が2個であること。
  • 次数が2を超える点がないこと。
  • 連結であること。

でいけそう。

連結かどうかは、Union-Findで行うという実装で提出。問題なくACが取れましたとさ。

13分44秒1ペナで3完。

提出コード

https://atcoder.jp/contests/abc287/submissions/38389972

D問題

D - Match or Not

制約からすると、各xの値についてO(1)で判定する必要がありそうだ。

ということで、STを前から照合した時に何文字までマッチするかと、後ろから照合した時に何文字マッチするかというのを前計算しておけば、各xについて素早く結果が計算できそう。

ということで、上記の考え方で実装。本番で通るかどうか少し心配でしたが、なんとかACを取り切ることができましたとさ。

35分44秒1ペナで4完。

提出コード

https://atcoder.jp/contests/abc287/submissions/38401736

E問題

E - Karuta

なんか難しそうな見た目をしており、以前やった文字列アルゴリズムを知らないと解けない問題かという印象。

ただ、他の文字列と、前からどのぐらい一致するかというのを全探索するのは変で、文字列をソートしてあげればだいぶ効率化できるのではないかと推察。

一応、サンプル2で検証してみると、やはり文字列でソート後、前後の文字とのLCPを取れば答えと合ってくれるみたい。

ということで、文字列とその出現順でソートし、前後のLCPのMaxを答えとする実装で提出。TLEだけが心配でしたが、なんとか通ってくれました。

61分39秒1ペナで5完。

提出コード

https://atcoder.jp/contests/abc287/submissions/38411214

F問題

F - Components

だいぶ時間が余った状態でF問題に取り組みましたが、これはよくわからず。

見た目から推察するに、典型90で少し触った木DPなのかというところと、計算量はO(N^{2})なのかという印象だが、肝心の遷移をどうすればいいのかわからない。

結局、この問題の考察を進めているところで時間切れになりました。

のちほど解説を見ると、たしかに木DPだった模様だが、遷移については難しいという感じでした。後ほど復習します。

G問題

G - Balance Update Query

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

Ex問題

Ex - Directed Graph and Query

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

これまでの実績

先週減らしたレートを取り戻しました。ここからさらに上に行けるといいんだが。。

コンテスト実績
コンテスト実績

総括

順位表の状況を見ると、今回はE問題までの難易度が甘めだったのかというところでした。

タイムは少し良かった方でしたが、肝心の高難易度の問題を解くというところがまだできていないかと。この結果には満足せず、次に向けて今回解けなかった問題を中心に復習していこうと思います。

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

AtCoder Regular Contest 154 参加記

2023/1/22に開催されたAtCoder Regular Contest 154に参加しました。

atcoder.jp

前回ARCは1完で惨敗という結果でしたが、今回のARCは問題ABCが300-400-500という配点のため、もしやすると2完は行けるかという印象。

前回ARCで食らった負けを取り戻すべく、まずは2完、行ければ3完を目指そうという気持ちで臨むことにしました。

今回の結果

が、、今回もあえなく1完で終了という残念な結果。。。

ARC154結果
ARC154結果

パフォーマンスは、やっと緑というところ。とうとう、レートは1100を切ってしまいました。

振り返り

全体的に、やらかしがあったり、考察が足りなかったりと、反省点が多い内容でした。

ARC154提出結果
ARC154提出結果

A問題

A - Swap Digit

問題の趣旨はわかったが、どうすればA \times Bが最小になるのかがわからん。

とりあえず、サンプルを見る限り前の桁の大小関係と今の桁の大小関係が入れ子になればOK?という感じで実装してみたら、あえなくWA。。

改めて、サンプルを元によく考えてみると、どちらかの値をできるだけ小さくしたらいいように見える。ということは、Aを可能な限り小さくするように操作したらどうか?

物は試しということで実装してみたら、なんとかACを取ることができましたとさ。

因みに、A \times Bmod 998244353はどうやったら上手く計算できるかがわからんかったので、BigDecimalでゴリ押しできるかと実装。結果、実行時間がほぼ2000msいくかどうかというギリギリのところで耐えてくれましたとさ。

ということで、ジャッジサーバの頑張りにも救われた形で、なんとか0完を回避することができました。24分1秒1ペナで1完。

提出コード

https://atcoder.jp/contests/arc154/submissions/38255593

B問題

B - New Place

とりあえずS,Tでアルファベットの種類と個数が違うとNoというのはわかるが、それ以降がわからんという感じ。

桁ごとに、それ以降に出てくるアルファベットと個数を累積和で持てば、効率的に処理できるかと思ったが、これは単なる検討違い。

とりあえず、全く良いアイデアが出ないまま1時間を経過しようかという状況になったので、一旦この問題は諦めることにしました。

C問題

C - Roller

一読した感じ、なんかB問題よりは解けそうな感じがするが、さてどうなるかというところ。

とりあえず、A_i = B_iとなる最小のiを探索し、一致が一つもなければNoかなあと。。

あとは、先ほど探索したiをスタート地点として、逆順に配列を走査し、A_i \ne B_iの時にA_iA_{i + 1}で置き換えても一致しない場合はNo。それ以外はYesという感じで組んでみました。

が、、これはサンプルが通ったぐらいで、提出したら半分ぐらいWA。。。

結局、ACは取りきれずで時間切れになりましたとさ。

D問題

D - A + B > C ?

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

E問題

E - Reverse and Inversion

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

F問題

F - Dice Game

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

これまでの実績

この土日は連敗という残念な結果。。入水どころかレート3桁突入を危惧しないといけない状態です。

コンテスト実績
コンテスト実績

総括

今回のARCも1完終了で惨敗という残念な結果でした。

最近の精進内容が、どうもABCの典型に偏っていたのが良くなかったのかもしれません。今後、ARCの過去問埋めも並行して進めようかと思います。

まあ、レートは下落傾向ですが、落ちたものを悔いても仕方なし。来週は再びARCとABC立て続けに開催されるので、これをレート上げのためのチャンスととらえて、また準備をしていこうと思います。

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

ウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286)参加記

2023/1/21に開催された、ウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286)に参加しました。

atcoder.jp

ここ最近のABCでは4完止まりが続いており、レートの方も停滞気味。

今回は、そろそろ5完以上取ってレートを上げていこうという気持ちで臨むこととします。

今回の結果

結局、今回も4完止まりになりましたとさ。

ABC286結果
ABC286結果

パフォーマンスは、なんとか4桁を確保というところで、今回は負け。停滞モードは、まだまだ続くのでした。

振り返り

D問題ですこしやらかしてしまい、E問題は解き損ねてしまいました。

ABC286提出結果
ABC286提出結果

A問題

A - Range Swap

A問題にしては、だいぶややこしい問題を出すなあという印象。問題文の意図を読み解くのに時間がかかってしまいました。

読み解いてみれば、単に区間  \lbrack P, Q  \rbrack  \lbrack R, S  \rbrackを交換すればよいということで、あとは単純にfor文で実装。

実装に少し時間がかかりましたが、一発でACが取れました。

6分17秒で1完。最近のABCでは一番時間が掛かったA問題でした。

提出コード

https://atcoder.jp/contests/abc286/submissions/38194228

B問題

B - Cat

個人的には、A問題より簡単な気がする。

Javaだと、Stringクラスのreplaceメソッドを呼ぶだけの実装でOK。問題なくACが取れました。

7分50秒で2完。

提出コード

https://atcoder.jp/contests/abc286/submissions/38195747

C問題

C - Rotate and Palindrome

最初解法が分からずで詰みそうでしたが、なんとか解法が閃きました。

どの状態からでもB円払う操作を \lfloor \frac{N}{2} \rfloor回行えば回文になるということから、A円の操作を0回~N - 1回行った時のB円払う必要がある操作の回数を全部試せば最小のコストが求まる。

あとは実装。問題なく一度の提出でACが取れましたとさ。

16分52秒で3完。

提出コード

https://atcoder.jp/contests/abc286/submissions/38202117

D問題

D - Money in Hand

ナップザックDPの応用かという見た目の問題。

とりあえず、 dp \lbrack i \rbrack \lbrack j \rbrack := i番目までの硬貨を使って、j円払えるかというDP配列を作成。

あとは遷移を書いて提出。。といったところだったが、WA。。。

遷移処理で下らないバグを埋めてしまったようです。都合8分程度費やしてやっと解決。

36分18秒2ペナで4完。少しもったいない結果になりましたが、E問題で取り戻せればと。。

提出コード

https://atcoder.jp/contests/abc286/submissions/38209942

E問題

E - Souvenir

どうもワーシャル–フロイド法を使って最短経路を求める問題という事らしいが、土産の価値の最大を求めるということで少しひねりを入れてみたという感じ。

とりあえず、最短経路という前提で、土産の価値の最大を求めるにはどうすればいいのかがよくわからん。

とりあえず、クエリ毎にDFSしてみたらどうかと実装してみたら、WAは出ないもののTLEで終了。。

ではメモ化DFSしたらどうかと改造したら、今度はTLEは無いもののWAが出てしまう。

あれこれ試行錯誤しても、結局ACは取り切れずで時間切れになりましたとさ。

F問題

F - Guess The Number 2

とりあえず、問題に目を通しましたが、わからず。制約の110にも深い意味がありそうだが前提知識が無かったので単純に意味不明でした。

中国剰余定理。この後、履修しておきます。

G問題

G - Unique Walk

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

Ex問題

Ex - Don't Swim

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

これまでの実績

まだまだ、停滞モードは続きます。いつになったら入水できるのやら。

コンテスト実績
コンテスト実績

総括

今回のE問題が解き切れなかったのは、アルゴリズムの理解不足なのか、実装力の不足なのか。とりあえず、解けないといけない問題だったので、そのあたりは残念です。

最近、平日は毎日競プロの精進に時間を充てていいるのですが、なかなか結果が出ないのがもどかしいところ。しかし、力をつけていけば、いつかレートは後から付いてくると信じて、今後も精進とコンテスト参加を続けていきます。

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

AtCoder Beginner Contest 285 参加記

2023/1/15に開催されたAtCoder Beginner Contest 285に参加しました。

atcoder.jp

2023年のRatedコンテストは、ここまで2戦2敗という体たらく。

このままずるずると負け続けるのは、さすがに精神衛生上よろしくないということで、今回はまず連敗を止めようという気持ちで臨むことにしました。

今回の結果

先週のABCと同じく、4完で終了となりました。。。

ABC285結果
ABC285結果

しかしながら、順位は1000位近辺という好位置で水パフォが出てくれました。なんとか、連敗脱出成功です。

振り返り

D問題がパッと見えてくれたのが、勝因のようです。

ABC285提出結果
ABC285提出結果

A問題

A - Edge Checker 2

A問題から、いきなりグラフ問題??と思ったが、要はa,bが辺で直接つながっているかを見るだけということで、まあA問題の難易度の範囲なのかなと。

解法としては、問題図にあるツリーの親子関係の特徴を見て、b = 2ab = 2a + 1ならYesという感じで実装。問題なくACが取れましたとさ。

1分55秒で1完。

提出コード

https://atcoder.jp/contests/abc285/submissions/38042446

B問題

B - Longest Uncommon Prefix

問題文の説明が回りくどすぎて、何を言っているか良くわからんという状態でしたが、サンプルの説明などを見てなんとか実装のイメージができました。

チェックする文字の間隔とチェック開始位置で二重ループを行い、文字が一致したところで内側のループを抜けるような感じで実装。サンプルと合ったので、そのまま提出してACが取れましたとさ。

9分53秒で2完。

提出コード

https://atcoder.jp/contests/abc285/submissions/38048553

C問題

C - abc285_brutmhyhiizp

文字列Sを26進数として解釈し、10進数の数値に変換すればよい。

最初、実装をバグらせてしまい、サンプルを通すのに少し苦労しましたが、なんとかサンプルが通る実装を完成させて提出。問題なくACが取れました。

17分8秒で3完。

提出コード

https://atcoder.jp/contests/abc285/submissions/38052653

D問題

D - Change Usernames

答えがYesとなるサンプルとNoとなるサンプルの違いを見てると、どうも変更したい名前どうしでループが発生するとNoになるみたい。

ということは、Union-Findを使ってサイクルが検出できればNo。あと名前の文字列がノードになるが、HashMapを使って各ユーザー名に対してユニークにIDを振ってやればグラフっぽく扱えるかと。

この解法でいけるかどうか、半々ぐらいの気持ちで実装してましたが、提出してみると一発でACが取れました!

27分7秒で4完。このD問題が解けたところで、なんと順位は670台という好位置に。すこしエスパー気味の考察でしたが、早めに解けてよかったです。

提出コード

https://atcoder.jp/contests/abc285/submissions/38056832

E問題

E - Work or Rest

順位表のAC数を見ると、大分手ごわそうな問題のように思える。。

まず、制約からO(N^{2})のDPで解くのかという感じだが、肝心のDPの定義が思いつかない。

ネックになることとして、先週の最後の休みの位置が確定しないと一週間の初日の計算値が確定しないだろうとか、いろいろ悩んでいました。

結果としてはこの問題で時間を使い切ってしまい終了。

あとで解説を見ると、初日を休日として確定させておくというオチ。こんな発想も浮かばないようではダメだという感じです。

こういう発想を出すためには、類題を多く取り組まんといかんのかなあ。

F問題

F - Substring of Sorted String

E問題が解けないので、一応F問題もチェックしてみましたが、手も足も出ず。

G問題

G - Tatami

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

Ex問題

Ex - Avoid Square Number

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

これまでの実績

2023年初勝利!内容はともかく、連敗を止めることができてホッとしたというのが正直なところです。

コンテスト実績
コンテスト実績

総括

今回は、D問題まで比較的早めに解けてくれた効果でなんとか高いパフォーマンスが出てくれました。

しかしながら、本当は、5完、6完を達成して高パフォーマンスを取って勝つというのが理想なので、今回の内容で満足はできません。

また、次週のコンテストに向けて、水Diff、青Diffの問題に取り組んで精進していこうと思います。

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

AtCoder Regular Contest 153 参加記

2023/1/14に開催されたAtCoder Regular Contest 153に参加しました。

atcoder.jp

前回のARC152では、高難易度のB問題が解けてくれて、レートが大幅に上昇という結果でした。

ARCは問題セットとの相性で大分結果が違ってくるという印象なので、今回もどうなるかわかりませんが、とりあえず今回は2完目標で臨むことにします。

今回の結果

目標の2完には全く及ばず。。1完で終了という結果になりました。

ARC153結果
ARC153結果

パフォーマンスは緑色の中間ぐらい。結局今回も負けです。

振り返り

B問題は考察が全く足りていませんでした。

ARC153提出結果
ARC153提出結果

A問題

A - AABCDDEFE

一読したところ、直接求めるのがややこしそうな問題という印象。しかし、よくよく考えると、美しい整数を決めるには、実質6桁分決めれば良いので、全探索が効きそうと判断。

ということで、6重ループを書き、美しい整数を全部求めてソートしてからN番目を求める方法で実装。

大分実装が重くなったせいか、デバッグに少々苦労してしまいましたが、なんとか一度の提出でACを取り切ることができました。

15分39秒で1完。とりあえず、0完だけは無くなりました。

提出コード

https://atcoder.jp/contests/arc153/submissions/38006034

B問題

B - Grid Rotations

大分難しそうな問題だったが、この手の問題の解法としてありがちな、横方向と縦方向の移動はそれぞれ単独で考えるというやり方ができそうな気がする。

あとは、それをどうやって計算するかをひたすら考えてみたが、結果としては一向に上手くいかず。途中、いもす法の応用で累積和とればよいかと考え、実装とテストをそれなりにやってましたが、結局時間のムダでした。

で、結局この問題だけで残り時間を使い果たしてしまい時間切れです。

解説を見ると、横と縦を単独で考えるところまでは当たっていたものの、先頭の要素の移動のみを見ればよいというところに全然気づけていませんでした。

C問題

C - ± Increasing Sequence

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

D問題

D - Sum of Sum of Digits

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

E問題

E - Deque Minimization

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

F問題

F - Tri-Colored Paths

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

これまでの実績

ここまで3連敗中。次のABCでなんとか盛り返したいなあ。

コンテスト実績
コンテスト実績

総括

今回のARCは、B問題の考察が足りずで、結局負けという結果になりました。

しかしながら、来週、再来週は、ARCとABC立て続けに開催される期間なので、取り戻せるチャンスはあるかと思います。次回にむけて、また準備をしていこうと思います。

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

AtCoder Beginner Contest 284 参加記

2023/1/7に開催されたAtCoder Beginner Contest 284に参加しました。

atcoder.jp

2023年一発目のRatedコンテストということで、幸先良いスタートを切るために、今回はなんとか勝ちで終わりたいところ。なんとかプラスの結果になれるようにという気持ちで臨むこととしました。

今回の結果

4完で終了。E、F問題に使える時間はだいぶありましたが、結局解けずという残念な結果となりました。

ABC284結果
ABC284結果

順位表から見て、だいぶ下げるかと思いましたが、なんとか4桁パフォには届いていた模様。とりあえず、かすり傷程度で済んだという印象です。

振り返り

E問題を難しく考えすぎていました、

ABC284提出結果
ABC284提出結果

A問題

A - Sequence of Strings

もらった文字列S_1, S_2,..., S_Nを逆から出力する問題。

色々実装方法はあると思いますが、とりあえず配列に格納後、for文で逆から出力する方針で実装。問題なくACが取れましたとさ。

1分38秒で1完。

提出コード

https://atcoder.jp/contests/abc284/submissions/37793052

B問題

B - Multi Test Cases

ちょっと前のABCでクエリ問題のテンプレートがB問題として出ていたような気がするが、今度は複数テストケース問題のテンプレートかという印象。

最近こういうのが流行っているのか、たんなるネタ切れなのかよくわかりませんが、問題としては配列の要素中に奇数が何個あるかを数える程度なので、実装はやるだけ。

こちらも、提出1回で問題なくACが取れました。

4分39秒で2完。

提出コード

https://atcoder.jp/contests/abc284/submissions/37800633

C問題

C - Count Connected Components

連結成分の個数を求めるということで、Union-Find一発で解ける問題のように見える。

C問題でこれを使うのは少しやりすぎという印象があったが、方針が見えてしまえば、さっさと実装した方がよい。

ということで、上記の解法で提出。問題なくACが取れましたとさ。

7分44秒で3完。

提出コード

https://atcoder.jp/contests/abc284/submissions/37804954

D問題

D - Happy New Year 2023

素因数分解の問題に見えるが、今回Nの最大値が 9 \times 10^{18} という、ちょっと見慣れない制約だったので少し戸惑いました。

ただ、よくよく検討してみると、問題文の条件より、pqのいずれかはNの三乗根以下の数値になるということが導かれるので、まずNの三乗根以下の範囲で割り切れる素数を見つけておき、あとはその素数で1回割れるか、2回割れるかで場合分けすれば良いということに気づきました。

あとは実装して。問題なくAC。とりあえず素数判定用に、エラトステネスの篩を使っては見たものの、とくに要らなかったのかもしれません。

29分31秒で4完。

ちなみに、コンテスト後の解説では、高速に素因数分解するアルゴリズムを使っても解けるとのこと。今後のためにライブラリ化しておこうと思います。

提出コード

https://atcoder.jp/contests/abc284/submissions/37804954

E問題

E - Count Simple Paths

単純パスの数え上げという、あまり個人的に経験のない問題。

とりあえず、解法の糸口を見つけるべく、いろいろググってみるが、ヒントになりそうな物はなし。

ということで、あれこれ試行錯誤しながら、気がつけば30分もたってしまったので、一旦この問題は諦めることにしました。

で、コンテスト後に解説を見てみると、なんとDFSで解けば良いとのこと。答えの最大が10^{6}だったのも次数に制約があったのも、これの伏線と考えるべきだったのかと、思い知る結果に。

次数に変な制約がある問題は、単純に探索していくことを検討した方がよいという知見を得ました。

F問題

F - ABCBAC

一見したところ、文字列の比較をN回繰り返せば答えが見つかる問題だが、一回の比較にかける時間を高速化できないとTLEになりそうな感じ。

高速化する方法などわからないため、とりあえず愚直に実装を行って通るかどうかを試してみることに。

が、、結局愚直実装すらまともに組めないまま、時間切れを迎えましたとさ。

解説をみると、SuffixArrayやらZ Algorithmやらの文字列比較用のアルゴリズムの準備が必要だった模様。

このアルゴリズムについては、ac-libraryにあるのは知っていましたが、使う機会がなかったので、これまで放置してました。今回の問題を機に、Java用に移植しておきたいと思います。

G問題

G - Only Once

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

Ex問題

Ex - Count Unlabeled Graphs

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

これまでの実績

2023年初Ratedコンテストは負けという結果になりました。

コンテスト実績
コンテスト実績

総括

E問題については、難しく考えすぎでした。どうせなら、E問題を愚直解で解こうという発想が働けばよかったというところ。今後は、順位表を見てAC数が多そうな感じだったら、愚直を考えてみるという方針で行ってみようかと思います。

F問題については、ライブラリの準備がないとダメな問題だったので、今回解けないのも仕方なし。次に向けて準備していきます。

2023年最初のコンテストは残念な結果でした。しかしながら、諦めずに努力を重ねていけば、いつか上の色に到達できると信じて、この1年頑張り通していきたいと思います。

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