E問題難しい…
セグメントツリーを使って解く問題かなあと思いつつ、ライブラリは用意してなかったからAtCoderのライブラリを探して来て使えるようにして、セグメントツリーの使い方を調べてってやってたけど導入が難しすぎて諦めた。
しかも解説をちらっと見てきたらセグメントツリーを使う問題ですらなかった…

A - Triangular Number

整数Nが与えられるので1からNまでを足した数を答える問題。 1+2+...+N = N(N+1)/2 を覚えていれば簡単に解ける問題。
覚えてなくてもループ処理で順番に足していけばよいだけの問題。

B - No-Divisible Range

長さNの数列{ $A _ {1}, A _ {2}, ... , A _ {N}$ }が与えられるので条件を満たす(l,r)の個数を答える問題。( $1 \leq l \leq r \leq N$ )

条件
$A _ {l} + A _ {l+1} + ... + A _ {r}$ が $A _ {i}$ で割り切れない。 $(l \leq i \leq r)$

事前に累積和を計算して任意の区間の和をすぐに算出できるようにしてから、全探索して解いた。 2重ループで(l, r)の全組み合わせを処理できるようにして、2重ループの内側でlからrまでの $A _ {i}$ を順番に区間の和の約数かどうかを確認していった。

C - Domino

N個のドミノが数直線上にある。ドミノiは座標iに立っていて、高さは $A _ {i}$ である。右に倒れると $i + A _ {i}$ 未満の範囲のドミノが倒れる。

この時1番目のドミノを右に倒すと全部でいくつのドミノが倒れるかを答える問題。

ドミノiを倒すと $A _ {i}-1$ 個分となりのドミノを倒せる。なので1番目から順番に倒せるかどうかを確認していった。具体的には、あと何個隣まで倒せるかを管理しながら、あと0個隣まで倒せるようになるまで順番に見ていった。 $A _ {i}$ を倒すと、残り倒せる数は $max(今管理している値, A_{i}-1)$ になるので随時更新しながら処理していった。

D - Reachability Query 2

有向グラフが与えられる。 Q個クエリが与えられるので順番に処理していく問題。

クエリ1：頂点vを黒色にする
クエリ2：頂点vから黒色の頂点へ到達可能かどうかを答える。
※最初、頂点はすべて白色。

色々考えたけどしばらくは良さそうな案が思いつかなかった。以下の案を出してみたけどダメそうだなあとなった。

クエリ2のたびにダイクストラ等で探索をする
事前に全組み合わせで到達可能かどうかを確認しておいて、黒い頂点を管理しつつ、vから黒い頂点の何処かに到達可能かどうかを計算量少なめの処理で確認する。
Union-Find木で連結成分ごとにグループ分けしてみる

もう少し考えてみて、辺の向きを逆にして黒い頂点が増えるたびにその頂点から到達可能な頂点にはフラグを立ててみることを思いついたので、試しに実装して提出してみたら解けた。

2025-11-09

トヨタシステムズプログラミングコンテスト2025（AtCoder Beginner Contest 431）

トヨタシステムズプログラミングコンテスト2025（AtCoder Beginner Contest 431）に参加しました。

結果

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

久々にD問題が解けた気がする。 DPの問題だったけど、割とあっさり解けた気がする。DPの理解度がちょっと深まった気がする。

A - Robot Balance

数値が2つ(H, B)与えられるので、max(0, H-B)を出力する問題。

問題文に書いてある通りに計算して結果が負にならないよう調整して結果を出力すれば良い問題。

B - Robot Weight

N個のアイテムがあって、Q回どれかのアイテムを選択される。

選ばれたアイテムが未選択ならアイテムの重みを加算して選択状態に、選択済みならアイテムの重みを減算して未選択状態にする。という処理を毎回実施してその時点の重さを出力し続ける問題。

これも問題文に書いてある通りに実装して出力する問題。

C - Robot Factory

N種類のパーツHとM種類のパーツBがある。パーツHとパーツBからそれぞれ1つずつ、重さがパーツH $\leq$ パーツBとなるように選んで、条件を満たすパーツの組み合わせをK個以上作れるかどうかを判定する問題（ただし各パーツは1回しか選べない。）

パーツ $H _ {i}$ 以上となるパーツ $B _ {j}$ を探していけば良いけど、たくさんのペアを作るためにパーツ $H _ {i}$ $\leq$ パーツ $B _ {j}$ をギリギリ満たすパーツBを選んでいきたい。

パーツHの方をソートしてパーツ $H _ {i}$ が小さい順にペアにできるパーツ $B _ {j}$ を探していった。パーツ $B _ {j}$ の方も小さい順にソートしてから比較していった。

$H _ {i}$ をギリギリ超える $B _ {j}$ を見つけたとして、 $H _ {i+1}$ とペアになれるのは $B _ {j+1}$ 以降のものになる。 $H _ {i}$ を小さい順に見ているのでさっき見つけた $B _ {j}$ よりも小さいものは確認する必要がない。ということで、Bは全部優先度付きキューに入れて小さい順に $H _ {i}$ と比較していった。小さい順に見ている $H _ {i}$ よりも小さいは $B _ {j}$ キューから出してしまって良いので配列で管理するより優先度付きキューで管理するほうが探索が楽だと思う。

D - Robot Customize

N個のアイテムがあるのでそれぞれHかBどちらかのグループに分けていく。アイテムにはグループHに入れた場合とグループBに入れた場合で得られる価値が異なる。また、最終的にグループHのアイテムの総重量 $\leq$ グループB のアイテムの総重量となるようにアイテムをグループ分けしていかないといけない。この時得られる価値の最大値を求める問題。

要するにナップサック問題。
愚直に実装するならDP[i番目のアイテムまで見た][現在のグループHの総重量][現在のグループBの総重量]=得られる価値の最大値　と実装したいけど、アイテム数が最大500、各アイテムの重みの最大値が500なのでDPの要素数が最大で500 $\times$ 500 $\times$ 500になる。ちょっと要素数が多すぎて配列で確保できる要素数の上限を超えているっぽくてテストケースの時点でエラーになった。

全部のアイテムを2つのグループのうちのどちらかに入れることになるので、事前にアイテム全部の総重量を計算しておけば、一方のグループの総重量からもう一方のグループの総重量を計算することができる。

ということでDPはDP[i番目のアイテムまで見た][現在のグループHの総重量]=得られる価値の最大値として処理をしていった。最後に得られる価値の最大値を探すタイミングで、アイテム全部の総重量とグループHの総重量からグループBの総重量を計算し、グループHのアイテムの総重量 $\leq$ グループBのアイテムの総重量となっている時だけ答えの候補として扱うことにした。

2025-10-25

Polaris.AI プログラミングコンテスト 2025（AtCoder Beginner Contest 429）

Polaris.AI プログラミングコンテスト 2025（AtCoder Beginner Contest 429）に参加しました。

結果

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

D問題がアイデアは思いついたけど、実装するのに苦労した。なんとか時間内にACできたから良かった。

A - Too Many Requests

M回"OK"と出力したあとN-M回"Too Many Requests"と出力する問題。

ループとifで実装すれば解ける問題。

ループとかifとか基本的な処理の実装練習みたいな問題。

B - N - 1

長さNの整数列と整数Mが与えられる。
数列N個の要素中N-1個の要素の和がMにできるかどうかを答える問題。

数列N項の総和を求めつつ、どの値が存在するかを管理しておく。総和-Mと一致する値が数列中に存在するかどうかで、Mピッタリにできるかどうかを判断できる。

C - Odd One Subsequence

長さNの数列が与えられる。数列中から3つの要素を選ぶ全組み合わせに対して、2要素は同じ値で1要素は他の2つと異なる値となる組み合わせ数を答える問題。

Nの値が大きいので三重ループで全通りの探索はできない。
どの値が何個あるのかを連想配列で管理する。
同じ値が2個以上存在する時、2要素はその値から選んだことにして、残り1要素はその値以外から選ぶことにする。というのを同じ値が2個以上存在するすべての値に対して計算して合計すると求めたい組み合わせ数が計算できる。

全通りの探索はできないので、どの値が何個あるのかと情報を圧縮することで探索する範囲を小さくして、条件を満たす組み合わせを算出して解くタイプの問題だった。

D - On AtCoder Conference

長さMの池があり、N人の人が基準地から距離 $A _ {i}$ の地点にいる。

i = 0,1,...,M-1に対してi+0.5の位置からスタートしてC人とすれ違うまで時計回りに進み続けて池を周回していく。止まるまでにすれ違った人数を $X _ {i}$ とする。この時に $\sum ^ {M-1} _ {i=0} X _ {i}$ を求める問題。
同じ位置に複数人いる可能性があるので単純に $X _ {i} = C$ となるわけではない。

Mが $1 \leq M \leq 10 ^ {12}$ なので全探索はTLEになって間に合わない。

$A _ {i} \leq i ＜ A _ {i+1}$ の間は $X _ {i}$ は変化しないので、人と人の間の区間+2個程度の区間を対象に探索をすれば良い。これくらいの探索範囲ならTLEしなさそう。

0から $A _ {1}$ 、 $A _ {1}$ から $A _ {2}$ 、...、 $A _ {N}$ からM-1までの各区間で $X _ {i}$ *区間の長さを計算して合計すれば求めたい値になる。

池を周回していくけれど、たかだか2周程度しかしないので、２N人の人がいることにして、 $A _ {i}$ と $A _ {i} +M$ の位置に人がいることにすれば1つの配列で2周分までは人のいる位置を管理できる

これくらいのことを考えて実装を始めていったけど、ちょっと苦戦して割と時間切切りでACになった。

2025-10-11

パナソニックグループプログラミングコンテスト2025（AtCoder Beginner Contest 427）

パナソニックグループプログラミングコンテスト2025（AtCoder Beginner Contest 427）に参加しました。

結果

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

C問題でちょっと嵌って時間がそこそこ溶かしちゃった。
D問題のパターンは解き方をよくわかっていないので手を出しづらかった。
F問題はなんか解けそうな気がして挑戦してみたけどやっぱりTLEになった…

A - ABC -> AC

文字数が奇数の文字列が与えられる。真ん中の文字を抜いた文字列を出力する問題。

文字数が奇数なことは保証されているので真ん中が何文字目なのかを計算して、その文字以外を順番に出力すれば良い。

B - Sum of Digits Sequence

f(x) を十進数表記の各桁の数値の和とする。また、 $A _ {i} = \sum\limits_ {j=0} ^{i-1} f(A _ {j})$ (※ $A _ {0} = 1$ ) とする時に $A _ {N}$ を求める問題。

$A _ {N}$ を求めるために $A _ {0}$ から $A _ {N-1}$ まで全部計算する必要があるので愚直に順番に計算していく。

f(x) を簡単に計算できるように関数を定義しておけばコードがスッキリしそう。ループ処理で順番に計算していけば問題なく $A _ {N}$ を計算できる。

C - Bipartize

N頂点M辺の単純な無向グラフがある。これを二部グラフにするために最小でいくつの辺を削除すれば良いかを答える問題。

制約を見ると頂点の数も辺の数もそこまで多くない。なので全通りでの探索をしてもそこまで時間がかからなさそう。と思って、どの辺を削除するのかをbit全探索を使って探索してみたらTLEになった。
bit全探索でループごとに、辺を削除後のグラフが二部グラフになっているかどうかを判定していたけれど、そこの処理がちょっと重いみたい。ちょっと工夫して削除する辺が少ない順に探索・判定をして最初に見つけた答えを出力としてみてもTLEのままだった…

結局、頂点に関して全探索することにしたら拍子抜けするくらいあっさりACできた。
bit全探索で頂点を色分けして、各辺の両端が異なる色かどうかでその辺を削除するかどうか決めてというのを全通り探索して、1番削除する辺の数が少ないものを答えとして出力した。

最初に2択を間違えたせいで結構時間をロスしてしまって悲しい。

D - The Simple Game

2人のプレイヤーがターン制のゲームをする。両プレイヤーが最適の行動をした時にどっちが勝つかを出力する問題。

こういった、ターン制でそれぞれが最適な行動をした時の勝者判定をする問題は正直解き方がよくわからないので手が出せなかった。問題を読んで考えれば考えるほどビームサーチで良くないかなあと思う。

解説を読んで考え方を勉強しないとなあ…

F - Not Adjacent

長さNの数列が与えられるので以下の条件を満たす部分数列が何個あるかを答える問題。

連続する2項を部分数列の要素として選ばない
部分数列の和がMの倍数である。

数列の長さは最大で60項なので全探索できる範囲だと思ってbit全探索で解いてみた。でもTLEになったので別の解き方があるっぽい。

2025-10-04

AtCoder Beginner Contest 426

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

結果

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

C問題から面倒な問題だなあと思いながら解いてた。
飛ばして次の問題を解こうと思っても、次の問題のほうがもっと面倒なのでしょうがなくこれを解くかあ…と言うのを挟みながら順番に解いていった。

E問題は3分探索でやれば解けそうだなあと言う方針は定まったけど、上手に実装する方法が思いつかず愚直に1個ずつ処理を書いていくかあとやってたら時間切れになった。
解説を読むと3分探索で合ってたっぽいからあとは実装力を上げればかなあ。

A - OS Versions

OSのバージョンを表す文字列が3種類ある（ "Ocelot", "Serval", "Lynx"）。この中から2つのバージョン文字列が与えられるので1つ目の入力されたバージョンと2つ目に入力されたバージョンの新旧比較を行う問題。

文字列のまま比較しようとするとパターン数が多くなるので、まずは文字列をもとにバージョン数に変換した。こうすると1つ目のバージョン数と2つ目のバージョン数の比較1回で新旧比較ができるようになる。

B - The Odd One Out

長さ3以上の文字列が与えられる。文字列がN文字あるとするとN-1文字は同じ文字で、1文字だけ他と異なる文字となっている。
1文字だけ紛れ込んでいる他のN-1文字とはと異なる文字を出力する問題。

とりあえず連想配列で文字ごとの文字数を管理して、文字数=1となっている文字を出力した。

C - Upgrade Required

N個のOSバージョンが有り、古い順に1, 2, …, Nと順番に番号が振られている。
PCがN台ありi番目のPCには $OS _ {i}$ が入っている。

この状態から開始して以下の処理をQ回行う

バージョンX以下のOSが入っている端末すべてのOSをバージョンYに更新する。更新完了後、今回OSを入れ替えた端末数を出力する。

配列を使ってどのバージョンが何台あるかを管理しながら処理をしていった。何も考えないとバージョン1からバージョンXまでを線形探索することになるのでQとNの組み合わせ次第ではTLEになる。
しかし、1度処理を完了するとバージョンX以下の端末は存在しなくなるので、今はどのバージョン以下が存在しないのかを管理して、存在する最小のバージョンからバージョンXまでを対象に線形探索していくことで、探索範囲を狭めた。

D - Pop and Insert

0か1で構成された文字列が与えられる。先頭か末尾の文字を削除し、その文字の0,1を反転させた文字を好きな位置に挿入する。すべての文字を同じ文字にするために必要な処理回数の最小値を出力する。
ということをテストケースT個分処理する問題。

シミュレーションするには反転後の文字を挿入する選択肢が有りすぎるからどうしようかなと思いつつ、制約からテストケース1個分の処理はどれくらいの計算量まで許されそうなのかを逆算してみた。
そうするとテストケース1個でO(N)みたいなかなり高速な処理を求められているなあと考えた。

たぶんシミュレーションするのではなく、線形に数値計算っぽい処理をしていくことになるんだろうなと思いつつ考察をしていくことにした。

以下考えたこと

たぶん1番大きな塊は触らず、その塊以外の全部を塊と同じ文字にすればよいのかなあ
揃えたい文字と異なる文字は1回処理するだけで良さそう。（1回反転して揃えたい文字にしたら、1番大きな塊の中に挿入すればよいだろうから。
揃えたい文字と同じ文字は2回処理することになりそう。（揃えたい文字が0だとすると　0100000みたいな時は先頭の0を処理しないとその後ろの1は処理できないので先頭の0の処理は必須。1回処理して1にしたあとその1を0に変換する処理が必要なので最低でも2回の処理が発生する。

これくらいのことを考えて以下の手順で処理することにした。

ランレングス圧縮でっぽい処理で（0 or 1,何個連続している）というペアの配列を作る。
全部を0に揃えることとして、1番大きな0の塊を探す。
見つけた塊以外を処理の対象として処理回数を数えていく。
0の塊なら連続している個数×2回、1の塊なら連続している個数×1回
全部を1に揃える場合の処理回数を同様に計算する。
全部を0にする場合、1にする場合で処理回数が少ない方を回答とする。

E - Closest Moment

高橋君と青木君がそれぞれ決められたスタート・ゴールで二次元平面上を直線に移動する。二人は速度1で移動するので、二人の距離が最も近いときの距離を答える問題。

時間がなくて解ききれなかった問題。

時刻0から何処かのタイミングまでは近づいて、それ以降は遠ざかって行きそう。たぶん、二人の距離関係は下に凸な二次関数で表現されるだろうなと思った。

時刻を指定すればそれぞれの位置は計算できそうだし、下に凸の放物線の最小値を計算することなるので、三分探索を使えば回答を求められそう。

このあたりのことを考えて、三分探索を実装しようとしたけど時間が足りなかった。

解説を見てみると三分探索で解くのは正解だったみたい。

2025-09-20

AtCoder × Engineer Guild オンサイトコンテスト～集結！高レート人材～予選（AtCoder Beginner Contest 424）

AtCoder × Engineer Guild オンサイトコンテスト～集結！高レート人材～予選（AtCoder Beginner Contest 424）に参加しました。

結果

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

C問題まではサクッと解けたけど、D問題で躓いてた。

DとE問題を見比べるとD問題の方が簡単そうだったのでD問題を先に解くことにしたけど最終的に解けなかった。残り10分ぐらいになってからE問題を解き始めてみたけど、時間内にデバッグが終わらなかった。コンテスト後5分くらいでデバッグが終わったから提出してみたらあっさりACして拍子抜けだった。
先にE問題から解き始めればよかった…

A - Isosceles

三角形の3辺の長さが与えられるので、この三角形が二等辺三角形かどうかを判定する問題。

数値3つの内、同じ値が2つ以上あるかどうかを判定すればよい。

数値3つを配列に入れてソートし、1,2番目か2,3番目の数値が同じ長さかどうかを判定して回答して解いた。

もしくは全部をsetに入れてsetの要素数が3かどうかでも判定できると思う。要素数が3なら3つ全部が違う値だけど、要素数が2以下なら数値の被りがあることになるので二等辺三角形だと判定できる。

B - Perfect

N人がM問の問題を解いている。Aさんが問題Bを解いた。という情報をK個与えられるので、全問解いた人の番号を解ききったのが早い順に出力する問題。

誰が今何問解いているのかを配列とかで管理する。解けたと言う情報を基に配列をメンテしてからAさんがM問解いたかどうかを確認してM問解けていれば番号を出力していった。

今回は人別に何問解けているかだけ管理すれば良くて、どの問題は解けていてどの問題は解けていないかは管理する必要がないので簡単だった。 mapなりで人別に回答問題数を管理していれば解ける問題だと思う。

C - New Skill Acquired

N個のスキルがあり、各スキルには取得の前提となるスキルA,Bがある。 AかBどちらかのスキルを取得していればスキルiは取得できる。

一部のスキルは最初から取得しているので最終的に取得できるスキルの個数を答える問題。

グラフの問題だと思ったのでBFSで取れるスキルを探索してフラグを立てて、最後にフラグが経っているスキルの個数を数えて出力した。

AとBからスキルiに有向辺が伸びているグラフだと思ったので、最初から取得できているスキルを始点としてDFSを実行した。

問題が有向グラフの問題だと気づけて、DFSやBFSを自力で実装できれば解ける問題だと思う。

D - 2x2 Erasing 2

縦Hマス横Wマスのマス目がある。マス目は黒か白に塗られている。初期状態のマスからいくつかのマスを白く塗ることで、2×2が全部黒マスとなっている箇所をなくしたい。最小で何マスの黒マスを白くすれば達成できるかを回答する問題。

最終的には解けなかった… マスの最大サイズがそこまで大きくないので、愚直な実装でも解き切れるんじゃないかなと思うけ。
解けたと思ってもWAが結構あるし、どんなパターンでWAになるのか全然思いつかなかった。

E - Cut in Half

N本の棒がある。1番長いものを1本取り出して長さを二等分にしてから戻すと言う処理をK回実行する。 N＋K本の中からX番目に長い棒の長さを出力する問題。

長い棒の選択には優先度付きキューを使えば簡単にできそうだなと思った。とはいえ同じ長さの棒が複数あるときに1本ずつ、取り出して二等分してキューに戻すと言う処理をしていたら制限時間内に解けないと思う。そこでmapで棒の長さとその本数を管理することにした。棒の長さの種類を優先度付きキューで管理し、長さ別の本数をmapで管理して、K回分の処理の実行やX番目に長い棒の探索を1本ずつではなく複数本分まとめて処理できるようにした。

デバッグに手間取って時間内に提出できなかったけど、デバッグ後に提出すると1回でACできたのでE問題にしては簡単に感じて拍子抜けした。