2026-01-21

【精進録】ABC441 E - A > B substring

皆様はじめまして、みろくと申します。
upsolveしたのでまとめをば...

問題

$A, B, C$ からなる文字列のうち、 $A$ が $B$ より多く含まれる部分文字列の数は？
という問題です。

コンテスト中の思考

一番最初に思ったことはdpで処理できないかな～ということで、
$dp[i][j] := i文字目までで、(Aの個数) - (Bの個数)がjの部分文字列の数$ みたいなのを効率よく保持・更新できないか、というのを考えました。
が、各 $j$ について毎回更新が走るので辛そう...と思い捨てました。(解説の $O(N)$ 解法はこの方針に近そうですが...)
そうして各文字ごとに、 $(Aの個数) - (Bの個数)$ (簡単のために以下 $i$ 文字目までの $(Aの個数) - (Bの個数)$ を $C[i]$ とします)と、
条件を満たす文字列を眺めていると、
$i \lt j かつC[i] \lt C[j]を満たす(i, j)の数$
では？と思いつきました

実装にあたって

こうなったらあとは転倒数の逆のようなものを求めるだけ！...なのですが、私は転倒数どころかBITも履修してません。
そしてコンテスト時間も残ってません。
う～～～ん...となり、配列をreverseしてネットの海から頑張って実装するなどして頑張ったのですが、バグがとれず結局通せませんでした。

そしてコンテスト後にきっちりBITと転倒数を履修してACしました。
一応座圧に関してもできるけど利用例をあんまり履修できてなかったので、N足して補正する方向ではなく座圧を用いました。
atcoder.jp

$O(N)$ 解法について

私の頭を悩ませたところです。
転倒数が $O(N)$ で...？？？？
みたいな思考に陥っていたのですが、どうやら $C[i]$ が1ずつしか変動しないことを利用するらしいということに気づいてからはスムーズに腑に落ちました。
$i$ 文字目を追加することによって増える、条件を満たす文字列を計算するためには、
$j \lt i$ を満たすすべての $j$ のうち、 $C[j] \lt C[i]$ を満たす要素の個数が必要です。
これを知るためには、累積和を毎回変動させるような処理が必要となるので、一般にはBITを用いる必要があるのですが、 $C[i]$ は1ずつしか変動しないので、
各 $C[i]$ の登場回数を管理する配列 $counter[N + 1]$ を持っておくことで、
$counter[C[i]]$ を足し引きするだけで上記の要素の個数を適切に計算することができる、というわけです。
$counter[i]それぞれの値を書き出して、条件を満たす要素がどこからどこまでの和なのか、というのを各[tex: i$ ごとに書き出してみるとわかりやすいと思います

まとめ

自分の適性帯の問題で名前を見たアルゴリズム・データ構造をちゃんと履修しておく
その問題が一般のアルゴリズムで解ける問題の特殊パターンではないか、ということと、それを利用できないかということを考える

それが簡単にできたら苦労しないんですがって？君は正しい。多分。

2025-12-21

ABC437参加記

皆様初めまして、みろくと申します。
Atcoder Beginner Contest 437に参加しました～
結果はABDの3完でした。うーーーーん......もうちょっと取れたよなぁ...という気持ちです

atcoder.jp

A - Feet

簡単すぎ、という意見も見た気がしますが私はA問題ってこれぐらいが良いよね～と思いました。

B - Tombola

それなりに色々な解法が浮かびましたが、3重ループ作ってバグらせるのが嫌だったのでSetを使って楽しました。
問題名気になって調べてみたらそういう感じのゲームがあるんですね。初耳。

C - Reindeer and Sleigh 2

え、無印の方2年前...？ほんとに...？
というのは置いておいて、こういうのが一番無理～と見て5秒で確信し、まず2完の覚悟をしました。
若干考えて、DP辛そう...貪欲っぽい...答えで二分探索とかできなくない...？でも評価関数思いつかん...一回全部乗せてどれをおろせばいいか考えるか...？軽くて力強い奴とかどっちにしていいか分からなくない...？
見たいなことを数分考えて、早々に解くのを諦めました。
貪欲って分かってるんだからもうちょっと考えようね。はい。

D - Sum of Differences

やった～主客転倒だ～こういうの結構得意なイメージがあったのもCを早々に捨てた理由の一つです。
A_i > B_iならA_i - B_i、
A_i < B_iならB_i - A_iということで、
反対側の配列の内、今見ている要素より大きい要素の数を数えられたらその今見ている要素の寄与が分かるので、Sortしてにぶたんを結構スムーズに思いつけて良かったです。
あとmintをコンテスト中に持ちだしてACしたの初めてな気がしています。

E - Sort Arrays

やった～グラフだ～こういうの(以下略)
とはいったものの、Trie木という存在を知らず、A_iごとに頂点と末尾に追加された整数を持つ、という方法で木を構築してしまった結果、
今見ている頂点の子について最小の整数が書かれている頂点すべてをqueueに入れ、そのqueueを引数にDFSを走らせる...
という実装をした結果queueに順番に頂点を追加していく処理でバグらせてしまい、結果時間内にACできませんでした
queueで渡すとどの変数を見ているかがcoutでデバッグしづらく、「デバッガー欲しい～～～」と言い続けていました。環境構築をサボるのをやめましょう。

まとめ

どうせE通せなかった、ということを考えればCをもっと考えるべきだったとは思うのですが、そこに時間を使っていたらEを通せていた可能性が見えなかったと感じています。
つまり現実的に望めていた最高得点はABDEだったかなと思うのでCを即座に思いつけないのは反省ですが、コンテスト中にとった戦略としてはそんなに悪くなかったのではないかと思っています。
貪欲に強くなりた～～～い
ICPCなんかだとチームメンバーの一人が天才貪欲系に鬼強いせいでそこら辺を訓練してなかったんですよねぇ

2025-04-28

【精進録】ABC402 E - Payment Required

はじめに

お久しぶりです。きちんと振り返りたいと思った問題に出会っため記事を書こうと思い立ちました。
丸1年以上ぶりですが、マイペースに書いていけたらと思います。

問題概要

お金 $C_i$ を支払って問題 $i$ に提出すると $P_i \%$ の確率で $S_i$ 点が獲得できる時、 $X$ 円で獲得できる点数が最大になるように行動した時の得点の期待値を求める問題です。

コンテスト中に考えたこと

$N$ の制約を見るに、bitDPを使う問題ではないか、ということを思いついたのでDPの遷移を考えました。
$X$ も小さかったので、
$dp [T ] [i ] =$ Tに含まれる問題をi円で解いた時の〇〇
のような形の遷移を考えていたのですが、いまいち遷移や、答えへの結びつけ方を思いつくことができませんでした。

解法

ここからは解説を見た後の記録です。
解説を見たところ、bitDPという方針は間違っておらず、やはり遷移を思いつけなかったことが原因だったようで、正しい遷移は
$dp [T ] [i ] =$ Tに含まれる問題を正解していて、残りのお金がi円の時に今からとれる得点の期待値
とすることによって、 $dp [T ] [i ]$ から $T$ に含まれない問題 $j$ に提出したときの得点の期待値は、問題 $j$ を解いた後の得点の期待値は $dp [T \cup j ] [i - C_{i} ]$ と $dp [T ] [i - C_{j} ]$ から求められます。問題が解けたら前者に、解けなかったら後者に遷移するため、 $P_{j}$ を用いて両者への振り分けを計算して、解けた方には $S_{j}$ を足す、とすれば良いからですね。

実際の実装では $i - C_{j}$ という部分に注目すると、 $i$ の昇順に計算すれば $T$ の順番を気にする必要が無くなるため、 $T$ も昇順に計算することが出来ます。

提出

反省と学び

この問題で学んだことは、今までで得た得点の期待値ではなく、これから得られる得点の期待値で遷移する、という考え方であり、これを思い付けなかったことが反省だと思います。
ゴールから考えるというDPは知っているつもりでしたが、あまりDPの問題を解いてこなかったことが出た部分かなと思います。
bitDPと期待値の勉強をしなければなと思います…

2024-01-20

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のための精進をすることをお勧めします。受からなかった人の意見なのでほどほどに聞いてほしいですが、落ちた人間だからこそわかる部分もあると思います。せっかくここまで読んでいただけたのですから、これだけは覚えていただけると嬉しいです！

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

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

2023-10-30

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の方にてご意見くださるとありがたいです！

2023-10-07

ブログ始めてみました

1.自己紹介

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

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

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

3.さいごに

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