2026-05-16

SMBCプログラミングコンテスト #1（AtCoder Beginner Contest 458）

SMBCプログラミングコンテスト #1（AtCoder Beginner Contest 458）に参加しました。

結果

A, B, C, Dの4問正解でした。

D問題までは比較的さくさく解けたけど、E問題が難しい...

A - Chompers

文字列Sと整数Nが与えられる。文字列の先頭N文字と末尾N文字を除去した文字列を出力する問題。

N+1文字目から末尾-N文字目までを順番に出力する問題。

問題文のとおりに実装すれば解ける問題。文字列の扱い方が分かっていれば解けると思う。

B - Count Adjacent Cells

N行W列のグリッドがあるので、各マスに対して辺で接しているマスの個数を答える問題。

基本的に4だけど端や隅のマスだけ2とか3になる。（1行とか1列だけの場合は1とか2になるけど...）

とは言え、各マスに対して上下左右のマスが存在するか確認して存在する個数を出力するだけで解ける。

ランダムアクセスできるデータ構造でグリッドを再現して、注目しているマスに対してどのマスをチェックすればよいかを分かっていれば解ける問題だと思う。

C - C Stands for Center

文字列Sが与えられるので、文字数が奇数で中心がCの部分文字列の数を出力する問題。

Cの位置を一通りチェックして、各Cに対して注目しているCがセンターとして左右どれだけ部分文字列を伸ばせるのかを確認していき、そのCがセンターなら何個部分文字列を作れるのかを数えていった。

例えば、OOOOCOOOみたいな文字列の場合、左には4文字、右には3文字伸ばせるけど、このCをセンターにしたいから3文字までは伸ばせると判断するみたいな具合。 3文字まで伸ばせるので、C単体、1文字伸ばす、2文字伸ばす、3文字伸ばすの4通りの部分文字列が作れる。よって、このCに注目した場合は4つ分の部分文字列を求めることができた。みたいな具合で全部のCに対して処理を繰り返していった。

D - Chalkboard Median

整数が1つ与えられている。以下の処理をQ回繰り返す。

2個の整数が追加されるので、これまでに与えられた整数に対する中央値を出力する。

multisetに数値を入れていき、ポインタで中央の位置の値を管理しつつ出力していくことで解いた。

与えられた2つの整数が現状の中央値より大きいか小さいかで、今見ている中央の位置が1つずれるか今の位置のままかのどちらかとなる。なので入力値を確認して場合によってポインタを1つずらして、中央値を差しているポインタが差している値を出力した。

配列に入れたらランダムアクセスできるからポインタなんて使わずに中央値を取得できるけど、毎回ソートする必要が出てくるのでTLEになるだろうなと思ったのでこの案はボツにした。

毎回ソートしてるとTLEになりそうだと思ったのでデータ構造側で勝手にソートしてくれるset系のデータ構造を使うことにしたけど、解説を見てみると優先度付きキューで解く解法が書いていた。たしかに上半分と下半分にキューを分けてキューごとに昇順・降順を正しく設定しておけば、キューの先頭が中央値という状態にできるので簡単に中央値を取得できる。

E - Count 123

全然解けなかった問題。

1が $X _ {1}$ 個、2が $X _ {2}$ 個、3が $X _ {3}$ 個で構成されていて、且つ、隣接する項の差が1以下である数列の個数を求める問題。

DPなのかなと思って解いてみたけど、数列の長さによってはメモリが足りなくてエラーになった。どうにかしてメモリ量節約できないかなと考えて試してみたけど、改善しきれなかった。

たぶんDPで解こうとする方針自体が違うんだろうなと思いつつ、他にうまく解けそうな方針も思いつけなかった...

2026-04-25

Ｓｋｙ株式会社プログラミングコンテスト2026（AtCoder Beginner Contest 455）

Ｓｋｙ株式会社プログラミングコンテスト2026（AtCoder Beginner Contest 455）に参加しました。

結果

A, B, C, D問題の4問正解でした。

E問題はさっぱりわからない。よくよく考えると文字列に関するアルゴリズムはあんまりストックがない気がしてきた。
ちゃんと勉強して対応できるようにしておかないとなあ...

A - 455

整数A,B,Cが与えられる。 $A \neq B$ かつ $B=C$ であるかどうかを判定して答える問題。

問題文のとおりにif文で判定して答えれば解ける問題。

B - Spiral Galaxy

H行W列のグリッドがあって、各マスが白か黒かに塗られている。このグリッドの長方形領域のうち点対称のものの個数を数える問題。

正直言うとよくわからない...
問題文の最後にこの条件を満たすものの個数を求めろって書いてあるので、そっちを愚直に実装し、個数を数えることで解いた。

ある意味、問題文のとおりに実装して答えれば解けた問題。

C - Vanish

整数列Aが与えられる。任意の $x$ を選ぶと $A _ {i} = x$ の $A _ {i}$ をすべて0にできる。

K回この操作を行った後の数列Aの総和として考えられる最小値を求める問題。

1回の操作でできるだけ大きく数列Aの総和を減らしたい。なのでどの値が何個あるのかを数えて、値*その値の個数　の計算値を一通り求めて、計算値が1番大きい値をxとして選ぶことで1回の操作で最も大きく数列の総和を減らすことができる。

ということを考えて以下のように解いた。

数列を一通り確認してどの数値が何個あるのかをカウントする。数値*個数の値を計算して大きい順にソートする。数列Aの総和から、ソート済みの値の上からK個の数値を引く。

これで答えを求めることができた。例外として、数値*個数の値の要素数がK以下の場合がありえる。（K回操作する前に数列の総和が0とできたパターン）

D - Card Pile Query

1からNが書かれたカードが1枚ずつあって、１からNと番号が振られたカードの山が1山ずつある。

最初は山iにはカードiが1枚だけ配置されている。

カードCとカードCの上に積まれているカードを順序を保ってカードPの上に移動させる。という操作をQ回実施した後、各カードの山には何枚のカードが有るのかを答える問題。

どんなデータ構造を使えばきれいに解けるかなと悩んだ。よくよく考えるとカードxはどのカードの上にあるかだけを管理できれば良さそうなことに気がついた。最初は自分の下にはカードが無いくて、移動させることでカードCの下はカードPに更新される。

ここに気がついたのでUnion-Find木を使って親として自分の下にあるカードを管理することで解けると思った。一通りカードの移動を終えた後に、カードiの親を辿って行くことで自身がどのカードの山にいるのかが分かる。なのでどの山に何枚あるかが数えられる。

順番に各カードがどの山にいるのかを確認して各山の枚数を数えていき、最後にどの山にカードが何枚あるのかを順番に出力することで正解できた。

2026-03-21

AtCoder Beginner Contest 450

AtCoder Beginner Contest 450に参加しました。

結果

A, B, C, Dの4問正解でした。
D問題解けた！と思ってたけど、正解者数自体は結構いる。最近はD問題も当たり前に解ける程度にはできないとレーティングの現状維持もできなさそう。

A - 3,2,1,GO

Nが与えられるのでNから1までカンマ区切りで順番に出力する問題。

問題文のとおりに処理すれば良いだけの問題。 Nから2までループ処理で　数字,　を出力させて、最後に1を出力して改行すれば正解できる。ループで1まで処理させようとすると最後が　1,　になるので注意が必要。

B - Split Ticketing

N個の駅が直線上にある。

a駅で乗って、c駅で降りることを考える。 c駅までずっと乗っているときのコストと途中駅bで一旦降りてb駅で乗り直してc駅まで行った場合のコストを比較する。途中で一旦降りたときの方が、c駅までずっと乗っている場合と比べてコストが低くなる場合があるかどうかを判定して答える問題。

3重ループで、乗る駅、途中下車する駅、終点の駅を決めて全通り探索すれば正解できる問題。

問題文を読んだ時ワ－シャルフロイド法を想起したけど、途中下車することでコストが改善する場合が有り得るかどうかだけの判定なので、そこまでではなかった。最少のコストを、みたいな話だったらワ－シャルフロイド法を使うことも考えることになりそう。

C - Puddles

グリッドがあって、各マスが白か黒に塗られている。白に塗られている連結成分のうち、グリッドの外周と接していないものの個数を答える問題。

どうやれば効率的なのかは思いつかなかったので、最初に外周の白色を探してその連結成分を潰してから、内側に残っている未チェックの白色の連結成分の数を数えることにして解いた。

連結成分1つぶんの探索は深さ優先探索とか幅優先探索を使って、連結成分１個分の白色を探索して潰していった。

D - Minimize Range

整数数列Aと生成数Kが与えられる。整数の任意の項に対してKを足す。　という操作が何度でも実行できる。この時 $\max(A) - \min(A)$ の最小値を求める問題。

数列をソートして、最小のものを取ってきたとしてもKを足すとその元最小値が加算後も最小値とは限らないのでややこしい。もしかするとKを足したら最大値を超えて新しい最大値になることも有り得るかもしれない。

色々考えた結果、setとか優先度付きキューとかでデータ構造の方で勝手にソートしてもらって、最小値をとって、max-minを計算して、Kを足して、最大値をメンテしてキューに戻す。という処理をずっと繰り返せば正解できそうと思って実装してみた。

それだとTLEが１件だけ出て、ちょっとした改善をいくつか試してみたけど結果は変わらなかった。色々考えてみた結果、数列Aの各値に対してKでmodをとってから同じことをすれば正解できた。

setを使いつつ、Aの値域をK以下に限定することで処理するデータの種類を減らせるからTLEを回避できたと思ってる...

2026-03-01

AtCoder Beginner Contest 447

AtCoder Beginner Contest 447に参加しました。

結果

A,B,C,D問題の4問正解でした。

割と早めにD問題まで解けたものの、E問題以降が全然解けなかった。
E、F問題くらいまで解けるように精進しないとなあ。

A - Seats 2

N個の座席が1列に並んでいて、人がM人いる。隣り合う2つの席の両方に人が座らないように人を配置することは可能かどうかを答える問題。

隣り合わないように人を並べないといけないので、奇数番目の座席にだけ人を配置して全員を配置できるのかどうかで判断することにして考えてみた。

実装としては、座席数を2で割って端数を切り上げた値がM以上かどうかで判断した。

B - mpp

文字列が与えられるので出現回数が1番多い文字を取り除いた文字列を出力する問題。

以下の手順で解いた。

各文字の出現回数を数える。
1番出現回数が多い文字の出現回数を取得する。
文字列を1文字ずつ出力させつつ、その文字の出現回数が最大だった場合は出力しない。

文字ごとの出現回数をカウントできて、文字を元に回数をすぐに取得できるようにデータを管理できていればあんまり苦労せずに解ける問題だと思う。

C - Insert and Erase A

2つの文字列S, Tが与えられる。

Sは任意の位置のAを削除したり、任意の位置にAを追加したりができる。

Sに対してAを追加したり削除したりしてTと一致させることができるかどうか、できるなら最少で何回操作すれば一致させられるかを答える問題。

まずは、SとTからAを除いた文字列S', T'を作ってこの2つの文字列が一致するかどうかを確認する。
S',T'が一致しない場合、Sに対してAを追加・削除してもSとTを一致させることはできない。

後はSとTを1文字ずつ比較しながら、TにだけAがある、SにだけAがあるをもとに必要な操作回数を数えていき最後に最終的な操作回数を出力した。

D - Take ABC 2

A,B,Cだけで構成された文字列Sが与えられる。

A, B, Cを3つ1セットで文字列から除去する時、最大何回除去できるかを答える。ただし、BはAより後ろのものしか選べないし、CはBよりも後ろのものしか選べない。

Aを決めたとして、選択したAのに1番近いBを選んだほうがCの選択肢が広がるし、選択したBに1番近いCを選んだ方が以降の操作を行う時のCの選択肢が広がる。

一旦、文字ごとにどの位置にその文字があるかを配列で管理することにして、 Aを小さいものから1つ、そのAよりも後ろにある最初のB,そのBより後ろにある最初のCの3つを1セットとして除去していくことにした。除去対象とするB, Cは二分探索で探すことにして、A, B, C3つを1セットで削除できなくなるまで、削除できるセットを探索し続けた。

2026-02-14

AtCoder Beginner Contest 445

AtCoder Beginner Contest 445に参加しました。

結果

A,B,C問題の３問正解でした。

C問題まではかなり早めに解けたけど、D問題以降が全然解けなかった。

A - Strong Word

文字列が与えられるので最初の文字と最後の文字が同じかどうかを判定する問題。

問題文の通り、文字列の最初の文字と最後の文字を取り出して、それが同じかどうかをifで判定して答える。

文字列の任意の位置の参照が正しく実装できれば解ける問題。

B - Center Alignment

長さが奇数の文字列がN個与えられる。
最大の長さの文字列長をmとすると長さm以下の文字列iには前後に同じ数だけ.をつけてその文字列を出力する。

つまり、....文字列i....みたいに文字列の前後に.をつけて長さがmになるように調整して文字列iを出力させる問題。

文字列に付与する.の数は（m　-　文字列iの長さ）個になる。（文字列の長さは奇数という設定なので、奇数-奇数でこの値は必ず偶数になる。）
前後それぞれに付ける.の数はこの計算結果を2で割れば求められる。

C - Sugoroku Destination

N個のマスがある。各マスには移動先のマス目の番号が書いてある。マス1からマスNそれぞれを始点として $10 ^ {100}$ 回移動した場合、最後にはどのマスにいるのかを答える問題。

結論だけ言うと、Union-Find木を使えば簡単に解ける問題。

各マスには遷移先が1つだけ存在するので、遷移先のマス目はUnion-Find木でいうところの親ということになる。なのでこの問題は任意のマスiから $10 ^ {100}$ 回親をたどり続けるとどこにいるかを答える問題と言える。

問題を解いている時は見逃していたけど、制約として遷移先のマスは自分自身か、自分自身よりも後ろのマスに限定される。そのためどこか後ろの方のマスから前の方のマスへ遷移することはない。この制約のおかげで自己ループ以外にはループが存在しないことになる。

$10 ^ {100}$ 回移動と言いつつ結局はそこまで移動するよりも早く何処かで自己ループに入るので、Union-Findの親をたどり続けて、自分自身がルートになっている要素を見つければ良い。

コンテスト中は用意しているUnion-Find木のコードをコピペして、木を作って順番に親を辿って、辿った結果を出力するだけで正解できた。

2026-02-07

AtCoder Beginner Contest 444

AtCoder Beginner Contest 444に参加しました。

結果

A,B,C,Dの4問正解でした。

D問題にしては解きやすい方だったとは思うけど、ここ最近の参加者レベル高くない？ D問題も解けている人結構多い気がする。現状維持だとレートがじわじわ解けていってる…

A - Repdigit

3桁の数字が与えられるので、すべての桁が同じ値かどうかを判定する問題。

色々解き方はありそう。
今回は数字を文字列として受け取って、各桁が同じ文字かどうかを確認して答えた。

各桁をsetに入れて最終的なsetのサイズで判定する方がスマートな気がする。

数字として受け取ったなら、10で割った余りを取り出すのと、10で割るのを繰り返せば各桁の値を数字として取り出せるので、各桁を取り出した後は数値の内容をチェックすれば判定できる。

B - Digit Sum

N以下の整数のうち、各桁の和がKになる数字は何個あるかを答える問題。

Nがそれほど大きすぎないので、1からNまで順番に処理していっても間に合いそう。

各桁の和を求める処理を関数として切り出しておいて、1からNまでのループの中で呼び出し結果がKになっているかどうかを確認してカウントしていく。最後にカウントした数を出力すると正解できる。

C - AtCoder Riko

長さLの棒状のお菓子が何本かある。パッケージをシェイクして何本かが折れて2本になったかもしれない。パッケージを開けるとN本のお菓子が有り、i本目の長さは $A _ {i}$ だった。
元々の長さLとして考えられる値を出力する問題。

前提条件として、1本のお菓子が折れたとしても1回だけなのでLの候補として考えられるのは以下の2つ。

1番長いもの
1番長いものと1番短いものの和

各パターンが成立するかどうかを確認して、成立するなら解の候補に追加する。

最後に解の候補を順番に出力する。

長さ別にmapに入れておけば、2本のうちの一方の長さを決めた時、他方の長さを算出して、その長さが何本あるかの確認がすぐにできる。

D - Many Repunit Sum

N個の整数が与えられる。1を $A _ {i}$ 個並べた数をN個分足した合計を求める問題。

$A _ {i}$ は1を何個並べるかの値なので、桁数を表す。そして $1 \leq A _ {i} \leq 2 \times 10 ^ {5}$ なので最大で $2 \times 10 ^ {5}$ 桁の数字が出てくる可能性がある。

imos法を使って解いてみた。1桁目を+1し、 $A _ {i}$ +1桁目を-1することで任意のx桁目に1が何個足されているのかが分かるようにした。後は繰り上げに気をつけながら1桁目から順番に各桁の値として出力すべき数字を計算して出力していった。

2026-01-24

JPRSプログラミングコンテスト2026#1（AtCoder Beginner Contest 442）

JPRS プログラミングコンテスト2026#1（AtCoder Beginner Contest 442）に参加しました。

結果

A,B,Cの3問正解でした。

D問題はぱっと見セグメントツリーの問題かなと思いつつ、ライブラリを用意してないしそこまで複雑なことは本当に必要なのかなと思いつつ、一旦飛ばしてE問題を先に解いた。

E問題は極座標に変換して、角度でソートしてどうこうすれば解けそうだなと思って解いてた。WAが2件あってどんなコーナーケースに引っかかったのかわからず頭を抱えてた…

A - Count .

文字列が与えられるのでiとjの個数を数える問題。

線形探索でiとjの数をカウントしていけば良いだけの問題。

B - Music Player

初期状態は音量0、再生は停止中から始まり、

音量を上げる、下げる、再生・停止の状態を入れ替える

の3種類のクエリが与えられるので、各クエリを処理した後に、音量3以上で再生中かどうかを答える問題。

音量と再生状態を管理しながら、クエリが与えられるたびにメンテし、条件を満たすかどうかを確認して答えを出力し続けるだけの問題。

音量を下げた時はmax(下げた後の音量、0)で更新すると、if文を使わずに0より小さい時は0にするというのが簡単に実装できる。

再生状況はboolで管理して、状態を入れ替えるクエリが来た時は!で反転させることでメンテが楽になる

new_state = !now_state　みたいな感じで

C - Peer Review

問題文を簡単に言い換えると、無向グラフが与えられるので、指定されたノードiに対してノードi＋隣接ノード以外のノードから3つを選択する組み合わせ数を答える問題。

組み合わせの具体例ではなく結果の数値だけがわかれば良いので、与えられる入力から各ノードの隣接ノード数を数えて、全iに対してノードi＋隣接ノード以外のノードから3つを選択する組み合わせを計算して出力すれば良い。

問題文を読んで要するにグラフの問題と変換できれば解ける問題だと思う。

D - Swap and Range Sum

解けそうで解けなかった問題。

長さNの数列が与えられる。

2種類のクエリがQ個与えられるので順番に処理する問題

クエリ1　x番目とx+1番目の要素を入れ替える
クエリ2　l番目からr番目までの要素の和を出力する。

クエリ2を計算量少なめに処理できないとTLEすることになりそう。
あらかじめ累積和を計算して、クエリ1の影響を調整して出力すれば良いかなと思って実装してみたけど、やっぱりTLEになった。

解説を読んで確かにと思ったけど、隣の要素を入れ替えたところで累積和はスワップが起きた0~xまでの1要素分の累積和しか影響しない。 0~x-1までの累積和はスワップの影響を受けないし、右端がx+1以降の累積和もスワップの影響を受けない

だからスワップと同時に0～xまで分の累積和1要素だけをメンテすれば、累積和は常に最新の状態を維持できていると言える。

累積和が最新の状況を反映できているので、クエリ2はO(1)で処理できるので時間内に全部のクエリを処理できるようになる。

E - Laser Takahashi

解けそうで解けなかった問題。

2次元平面上にN体のモンスターがいる。原点から時計回りに回転し、モンスターAからモンスターBまでの範囲の角度にいるモンスターを除去する。

AとBが指定されたときに何体のモンスターが除去されるかをQ回答える問題。

考えた方針としては、平面座標から極座標に変換して、角度だけを取り出してソートしておく。モンスターA,Bが指定されると、A,Bの座標から角度を計算し、前述したソート済みの配列から指定された範囲の要素数を数える。開始と終了の位置関係から、数えた要素数をそのまま出力したり、Nから引いた数を出力したりする。（計算した範囲が除去する対象だったり、除去された後に残る要素だったりするので場合分けして対応）

解説を読むと、方針自体はあっていたみたい。特定の場合に微妙に誤差が出ているのかなあ。

あと、極座標の角度だけを計算してソートすることを偏角ソートと呼ぶらしい。知らなかった。