トヨタ自動車プログラミングコンテスト2024#12（AtCoder Beginner Contest 384）に参加しました。

結果

A～E問題の5問正解でした。

久々にE問題まで解けた気がする。
F問題は $O(N ^ {2})$ くらいの解き方は思いついたけど、そこから早くする方法が見つからなかった。

A - aaaadaa

文字列が与えられるのでc1以外の文字をc2に置き換えて出力する問題。

文字列を1文字ずつ取り出したり、if文で判定できたりが使えれば解ける問題。

B - ARC Division

N回コンテストを受けるので最終的にレーティングがいくつになっているかを答える問題。

現在のレーティングとコンテストの種類、そのコンテストでのレーティングの増減量が与えられるので、コンテストを受ける時点でのレーティングをもとにそのコンテストでレーティングが変化するかどうかを判定して新しいレーティングを計算する。っていうのをN回繰り返す。

ループの中で、

現在のレーティングだと今回のコンテストでレーティングが変化するかどうかの判定
新しいレーティングの計算

が正しく実装できれば解ける問題。

C - Perfect Standings

A～E問題の5問の配点が与えられるので、このコンテストで取りうる点数の高い順にどの問題を解けば良いかを出力する問題。点数が同じ時は解く問題セットの文字列を辞書順に並べる。

要するに点数別回答問題別にソートして順番に出力する問題。問題の解き方は全32通りで全問解かないの1通りは出力対象外（といってもAtCoderの仕様上最後に空文字を出力すると無視してくれるので空白行を最後に出力しても大して問題はない）。

どうやって32通り全通りを検証するかを考えるのがポイントなのかなと思う。
私はbit全探索で全通り確かめて、点数別に解いた問題セットの文字列をsetに入れて点数が高い方から順にsetの文字列を出力していって解いた。

たぶん、点数と解いた問題セットの文字列をpairにして、点数を昇順、文字列を降順にソートできればvectorに入れてソートするだけで解ける。
自分でソート時の大小をboolで返す関数を作って、それでソートさせられれば実装できるけど、何かが間違っていてエラーが解消できなかった。

D - Repeated Sequence

周期Nの数列Aの先頭N項が与えられる。この周期Nの数列の部分列のうち、総和がSとなる部分があるかどうかを答える問題。

総和がSとなる部分列なので、典型的な尺取法の問題。
第N項までの和を求めておけば、Sが総和以上の場合には何周期かをまたがった部分列だと判断できる。総和以下になるまでSから総和を引いていけば（＝総和でSのmodを取れば）、周期Nいくつ分かを丸々省略できるようになる。

1周目の後半から2周目の前半の部分列が正解のパターンを考慮して、長さ２Nの数列に対して尺取法で部分列がSとなるかを探索していき、答えれば解ける。

この考慮が漏れていて６WAだった…
コンテスト後にSNSを見るとこの6WAが解消できなくて、でも原因がわからないと嘆いている人がそこそこいた。
意外と気づかないハマるポイントなのかなあ。

E - Takahashi is Slime 2

H✕Wのマス目があり、各マスに強さが設定されている。
指定された座標が開始時の強さで、隣接するマス目の強さが自分の強さの $\frac{1}{X}$ 未満の時、そのマスを吸収して更に隣接したマスが吸収できるようになる。
吸収すると自分の強さは吸収したマスの強さ分大きくなる。

この設定の時自分はどれだけ強くなれるかを答える問題。

明らかに強さが小さいマスから吸収していった方が良い。
また、吸収するマスの強さ/Xとわり算をして大小比較をすると小数点以下の誤差が原因で正確に計算できないかも知れないと思ったので式変形してマス目の強さ✕Xが現在の強さ未満かどうかで判定した。
また、数字が大きいとオーバーフローするかもしれないなと思ったのでこの比較時にはdoubleに型変換してから比較した。

強さが小さいマスから処理したいので優先度付きキューを使って現在隣接しているマスとそのマスの強さを管理していった。

要するに、候補の中から強さの弱い順に探索する幅優先探索でシミュレートして解いた。

2024-12-07

大和証券プログラミングコンテスト2024（AtCoder Beginner Contest 383）

競技プログラミング

大和証券プログラミングコンテスト2024（AtCoder Beginner Contest 383）に参加しました。

結果

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

色々あってしばらく参加できなかったABCだったけど割といつも通りだった気がする。

A - Humidifier 1

毎秒1だけ水が抜けていく器に対して時刻 $T _ {i}$ に $V _ {i}$ だけ水を追加してく。 $T _ {N}$ に水を入れた時、器の水の量はどれだけなるかを答える問題。

A問題にしては難易度高めな気がする。

イベントドリブンでシミュレートできればちゃんと答えられる問題だと思う。もしくは、時刻は100までしかないので時刻0から $T _ {N}$ までを毎秒処理していっても正解できると思う。

B - Humidifier 2

マス目があって、通路と障害物がある。通路上の2箇所に加湿器を置く。加湿器はマンハッタン距離でD以下の範囲を加湿する。
最大何マスの通路が加湿できるかを答える問題。

通路のマスを列挙して、その中から2つ選ぶ組み合わせ全通りを確かめれば正解できた。

私が解いた時は、以下の2つの関数を作って解いた。

2つ座標を渡すとマンハッタン距離を計算する関数
座標を1つ渡すと、そこに加湿器を置いた時に加湿できるマスの座標全てをsetで返す関数

始めに列挙しておいた通路のマス2つを二重ループで全探索し、ループの中では2つの座標それぞれで2つ目の関数を使って、それぞれの結果をマージした。そうすると重複は排除して加湿できるマスの集合が求められるので、集合の要素数の最大値を回答として出力した。

C - Humidifier 3

B問題とほぼ同じ設定。違うのは以下2点。

加湿できるのは通路マスだけを上下左右に移動したときの移動距離D以下となるマス。
加湿器を置く位置は指定されている。

こっちは幅優先探索で解いていった。

最初に加湿器の置かれている座標を探索し、そこを始点として幅優先探索をしていった。 B問題のときと同様に加湿できるマスの座標はsetで保存していき、最後にsetの要素数を答えた。

D - 9 Divisors

N以下の正整数のうち正の約数をちょうど9個持つものの個数を答える問題。

解く方針はあってたけど解ききれなかった問題。

約数の数は、Nを素因数分解したときの指数+1の積で計算できるらしい。例えば、 $N=a ^ {i} * b^ {j} * c ^ {k}$ 　の時、約数の数は $(i+1) (j+1) (k+1)$ 個になる。

約数がちょうど9個と言うことは、 9 = 1 * 9 = 3 * 3なので

ある素因数を8乗した数　 $X=a ^ {8}$
ある素因数を2乗した数同士の積（=2つの異なる素因数の積の二乗）　 $X=a ^ {2} * b^ {2}$

上記の場合だけ考えれば良い。

解き方の方針としては $\sqrt{N}$ 以下の素因数を列挙し、

8乗してN以下となる数
それぞれの2乗を計算し、その中から2つ選んでその積がN以下となる数

それぞれを求めて数字の種類数を答えれば良さそう。

どっかで処理をミスっているのか入力例2の方が全然数が合わなくてひたすらコードとにらめっこしてた…

＜追記　2024/12/08＞

データの型選択をミスってただけだった。

8乗してN以下となる数
それぞれの2乗を計算し、その中から2つ選んでその積がN以下となる数

これをlong longでsetに入れてたけど、大きな値だとオーバーフローしていたみたい。 doubleに変換して保存するように修正したら1発でACだった...
ほぼACできるコードが始めのうちにできていて、割と無駄な時間をそこそこ過ごしていたらしい… もったいない。

2024-11-16

AtCoder Beginner Contest 380

競技プログラミング

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

色々あって、3週間ぶりのコンテスト。

結果

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

C問題までは問題文を読んで考察らしい考察もなくこうやれば解けそうって即思いついて大体あってるけど、 D問題からはじっくり考察しないとわからないことが多いし、実装もちょっと手こずるなあ。

A - 123233

6桁の数字が与えられるので、1が1つ、2が2つ、3が3つ持つ数値かどうかを判断する問題。

1桁ずつ値を確認してカウントして、１，２，３が指定された個数となっているかを確認して答えれば解けそう。

私は与えられる数値を文字列とみなして、ソートした結果が122333になるかどうかで判断して答えた。こっちのほうが1桁ずつ取り出すとかしなくて済んで楽な気がする。

B - Hurdle Parsing

ある数列があって、それが何かを推測して答える問題。数列をもとに|区切りで項の値だけ-が並んだ文字列が与えられるのでそれをもとに各項の値を求めて答える。

例えば、1,2,3という数列が答えだった場合、|-|--|---|が入力として与えられる。

単純に-が何個連続して並んでいるかカウントしつつ、|が出てくるとカウントをリセットしていく。

C - Move Segment

0と1からなる文字列が与えられる。同じ値が連続している部分を塊とみなして、K番目の1の塊をK-1番目の1の塊の直後に移動させた時の文字列を答える問題。

例えば、010011100011001でK=3のとき010011111000001が正解になる。もとの塊ごとに分解すると0,1,00,111,11,000,00,1となり、3番目の1の塊が2番目の1の塊の直後に来ている事がわかる。

0の塊から文字列が始まっているとみなして1の塊、0の塊それぞれを個別に配列に入れていき、K番目の0の塊と1の塊を入れ替えてから、 i番目の0の塊、i番目の1の塊を交互に順番に出力していけば良い。

例えば010011100011001でK=3のとき
0の塊：0,00,000,00
1の塊：1,111,11,1

3番目の1の塊と0の塊を入れ替える
0の塊：0,00,11,00
1の塊：1,111,000,1

0の塊と1の塊を交互に順番に出力する
0,1,00,111,11,000,00,1

D - Strange Mirroring

文字列Sが与えられる。Sから大文字と小文字を入れ替えた文字列をTとする SをS+Tに更新する処理を何度も繰り返した文字列Sを対象に、指定された文字が何かを答える問題。

最後まで解けなかった…
考察としては、最初に与えられた文字列を $S _ {0}$ として大文字小文字を入れ替えた文字列を $T _ {0}$ とすると、
$S _ {1} = S _ {0} T _ {0}$
$S _ {2} = S _ {1} T _ {1} = S _ {0} T _ {0} T _ {1}$
$S _ {3} = S _ {2} T _ {2} = S _ {0} T _ {0} T _ {1} T _ {2}$
・・・
$S _ {n} = S _ {N-1} T _ {N-2} = S _ {0} T _ {0} T _ {1}・・・T _ {n-1}$ と変化していく。また大文字と小文字を入れ替える処理を $\overline{　}$ で表すことにすると

$T _ {0} = \overline{S _ {0}}$
$T _ {1} = \overline{S _ {1}} = \overline{ S _ {0} T _ {0}} = T _ {0} S _ {0}$
$T _ {2} = \overline{S _ {2}} = \overline{ S _ {0} T _ {0} T _ {1}} = T _ {0} S _ {0} S _ {1}$
・・・
$T _ {n} = \overline{S _ {n}} = \overline{ S _ {0} T _ {0} T _ {1}・・・T _ {n-1} } = T _ {0} S _ {0} S _ {1}・・・S _ {n-1}$
となる。この性質を使ってうまく解けないかなあと頑張ってたけどだめだった。
文字数とKから
$S _ {0}$ か $T _ {i}$ の何文字目なのかは計算できるから頑張れば解けそうな気がするんだけどなあ…
考えているうちに頭がこんがらがってきた。

2024-10-26

トヨタシステムズプログラミングコンテスト2024（AtCoder Beginner Contest 377)

競技プログラミング

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

結果

A,B,Cの3問正解でした。 D問題はぱっと考えて解けそうな方法が思いつかなかったので飛ばしてE問題を解くことに。でもE問題はTLEが解決できず結局解ききれなかった。

A - Rearranging ABC

長さ3の英大文字の文字列が与えられるので並べ替えてABCにできるかどうかを判断する問題。

文字列をソートしてABCになるかどうかで判断して解いた。 ABCはたまたまソート済みだけど、別の文字列だったらABCをソートしたものと入力をソートしたものが一致するかどうかで判断すれば解ける。

B - Avoid Rook Attack

8×8のチェス盤にいくつかルークがいる。どのルークにも取られない位置のマスが何マスあるかを答える問題。

チェス盤自体が小さいので8つある行と列それぞれでルークがいるかどうかのフラグを用意して、 64マスそれぞれで同じ行、列にルークがいるかどうかをフラグをもとに判断して、数えていった。

C - Avoid Knight Attack

縦横Nマスのチェス盤が合ってM個ナイトがいる。ナイトの座標が与えられるのでナイトに取られない現在空いているマスの数を答える問題。

Nが最大で $10 ^ {9}$ なので全マスを個別にチェックしていくのはTLEになって不可能。
なので逆にナイトの位置情報からナイトが移動できるマスの数を数えて $N ^ {2}$ （＝全マスの数）から引いた数を答えた。

ナイトの移動先には重複があるかもしれないので、setでナイトの位置とナイトの移動可能なマスの位置を保存して、 setのサイズ＝ナイトの移動可能なマスの数として考えた。

E - Permute K times 2

１～Nを並び替えた数列Pが与えられる。
次の処理をK回行う。
- $P _ {i}$ を $P _ {P _ {i}}$ に更新する※i＝1~Nに対して同時に更新する。

K回処理後のPを出力する。

例
処理前：5 6 3 1 2 4
処理後：2 4 3 5 6 1

Kは最大で $10 ^ {9}$ なのでどうにかして処理を誤魔化して最終結果を取得する必要がある。
遷移の様子を手元で計算してみると、何回か処理することでループすることに気づいた。

各項を独立して考えて、x項目は何回処理するとループするかを検出して、Kからループ周期の剰余を求めると律儀にK回処理しなくても、ループ後に数回残っている処理の何ステップ目を答えれば良いかが計算できる。

上記の方針で実装して提出してみるとTLEになった。最終的にこのTLEが解決できなかった。

ループの検出とループ内の任意の位置の値を簡単に求めるって処理は時々出てくるから問題なく実装できるようになっておきたいなと思った。

2024-10-12

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

競技プログラミング

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

結果

A,Bの2問正解でした。
C,D問題は愚直になら実装できたけどどっちもTLEになって、でもどう工夫して計算量を減らすかが全然思いつかなかった。

ダメ元でE問題に手を出してみたけど、最初の方針が間違ってたのに気づかなかったから実装してもサンプルケースで答えが合わなくてデバッグしてた。

A - Seats

＃と.でできた文字列が与えられるので#.#となっているのが何箇所あるかを数える問題。

文字列から3文字ずつ取り出して、それが#.#担っているかどうかを判定していく。最後に条件を満たした回数を出力すればよい。

B - Traveling Takahashi Problem

2次元座標平面上の点を複数与えられるので、原点から与えられた座標を順番に回って、最後に原点に戻るまでの移動距離の合計を答える問題。

距離はユークリッド距離で良いので、計算を間違えなければ特につまらずに解けると思う。

C - Spiral Rotation

N×Nのグリッドが与えられる。グリッドには一部色が塗られている。

i=1,2,..,N/2の順に、
i以上N+1-i以下の整数x,yを対象に、(y,N+1-x)のマスの色を(x,y)の色に塗り替える。
最終的にグリッドの状況を出力する問題。

愚直になら実装できたけど、TLEになった問題。
思いついた計算量削減方法としては、
N/2回分の処理を毎回グリッドをメンテするのではなく、この座標の値は結局どこの座標の色になっているかという参照情報だけをメンテして、最後のメンテした参照情報をもとにグリッドの色を出力すると言う方法。
結局この方法だとだめだった。

制限時間3秒だし、TLEになったテストケースは3つだけだったからちょっと頑張ればACできるかもと思ったんだけどなあ…

D - ABA

文字列が与えられるので、3文字選んで回文を作るインデックスの組み合わせ数を答える問題。
愚直になら実装できたけどTLEで解ききれなかった。

3文字の回文なので最初と最後の文字を固定して、真ん中の文字が何通りあるのかを数えていけば良いと思って解いていった。
文字毎にその文字がどこにあるのかというインデックスを配列で管理しておき、配列ごとに、2つ選んで回文の最初と最後の位置ということにして間が何通りあるのか計算するというのを全組み合わせ、全文字種でやっていき、最後に計算結果の合計を出力していった。結局これだとTLEになったし、全組み合わせの処理で二重ループがあるからそこで遅くなっていると思うけどどうやったら早くできるのか思いつかなかった。

E - 3 Team Division

3つチームが合って、N人の人がランダムにどこかのチームに所属している。各人には強さが設定されている。最少で何人の移動で各チームの強さを均等にできるかどうかを答える問題。

最初は、強さの目標値を計算して最少何人の移動で過剰な分の強さを減らせるかを計算してその合計を答えることにしてみた。

でもサンプルケースでも答えが合わないし、サンプルケースの解説を見ると、強さが過剰なチームの人が足りていないチームに移動するだけではだめなのでこの方針はそもそも間違いだったみたい。

2024-10-05

キーエンスプログラミングコンテスト2024（AtCoder Beginner Contest 374）

競技プログラミング

キーエンスプログラミングコンテスト2024（AtCoder Beginner Contest 374）に参加しました。

結果

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

D問題はどっかに微妙なバグがあるのか一部のテストケースがWAになって解ききれなかった。解説を読んでみたらほとんどやっていることは一緒なんだけどなあ…

E問題は、最小値の最大化をというワードから二分探索を使って解く問題だなと思って実装を進めていった。でもサンプルケースの時点で一部答えが合ってなくてどこをどう直そうかなと色々と試行錯誤してみたけど、期待した答えが出る処理にはできなかった。

コンテスト後に解説を軽く読んでみたらD問題もE問題も解く方針自体はあっていたのに、どちらも解けてなくてもったいないなあと思った。

A - Takahashi san 2

文字列が与えられるのでその文字列がsanで終わっているかどうかを判定して答える問題。

問題文の通り文字列の最後3文字を取り出して、それがsanかどうかを判定すれば良い。
部分文字列を扱うのが面倒くさいなら、文字列をひっくり返して最初3文字がnasになっているかどうかを判定すれば良い。こっちなら部分文字列を作らなくても済ませられて、1文字ずつインデックスが0,1,2でアクセスしてnasになっているかどうかを確認すれば判定できる。

B - Unvarnished Report

2つ文字列が与えられるので違う部分があるなら1番最初に違っているのは何文字目かを答える問題。

文字列の長さ自体は対して長くないので、先頭から短い方の文字列分順番に確認していけば良い。違う文字が見つかればそこが答えになる。短い文字列分は完全に一致するなら、2つも文字列の長さが同じかどうかで答えが分岐する。

長さが同じなら2つは同じ文字列と判断できる。長さが異なるなら、問題文に従い短い方の文字列の長さ＋１文字目が最初に異なっている文字として答える。

C - Separated Lunch

N個の部署があるので2つのグループに分ける。2つに分けたグループの内、人数の多い方の人数は最小で何人にできるかを答える問題。

Nの最大値が20程度なので、ビット全探索で全通り探索して答えれば良い。

人数の多い方のグループの人数を最小化したいので、ビットに応じて対応する部署をどっちのグループに振り分けるか判断して、その結果2つのグループは何人になるのかを計算して、人数の大きい方のグループの人数を取り出す。この人数が最少で何人になるかを管理して答える。

全通り確かめるという愚直な方法で間に合う程度の制約なので、ビット全探索を理解して実装できれば解ける問題だと思う。ビット全探索知らないなら、最悪ループを20個の力技で実装しないといけないのかな。

D - Laser Marking

xy平面がある。線分がN本与えられるので、原点から移動してこの線分を全部なぞるまでの最短時間はどれくらいになるかを答える問題。
線分をなぞる時は、線分の最初から最後まで一気になぞることとして、途中から途中までなぞるといったことはできない。
問題のテーマがレーザー刻印ということもあり、線分をなぞっている時と、なぞっていない時で移動速度が異なる。

線分の数は最大で6本しかないので、なぞる線分の順番は全通り試せる。 next_permutationとかで全通り試しつつ、順番が決まったときに、線分の両端のどっちからなぞれば良いかをいい感じに選びながら全部でどれくらい時間がかかるかを計算して答えれば良さそう。

どんな順番で線分を選択したとしても線分上を移動する距離の合計は変わらないので、線分をなぞっていない時の移動時間を最小化すればそれが答えになりそう。
なので、どの線分をなぞるか決めたら、その線分にある2つの頂点の内どちらから始めるかを決めて時間を計算する。私は、現在地点から近い方の頂点へ移動してなぞり始めれば良いと思って実装してみたけど、一部のテストケースがWAになってだめだった。

改めて考えてみると、この考え方だと、今いる地点から次の線分がなぞり終えるまでの時間は最適化できてると思うけど、それが全体最適にはならないパターンがあるのかも。今回はわざとちょっと遠い方からなぞった方が、その次の線分をなぞり終えるまでの時間は実は短くなるみたいなパターンがありそう。