最小公倍数以下の条件を満たす数を一通り求められれば簡単に算出できるけど、 ”最小公倍数以下の条件を満たす数”を一通り求めるのが簡単にはできなくて解ききれなかった。制約ギリギリの入力があった場合に候補となる数が多すぎて配列の要素数が上限を超えててエラーになったり、その部分だけでTLEになってだめだった。

2024-02-10

鹿島建設プログラミングコンテスト2024（AtCoder Beginner Contest 340）

鹿島建設プログラミングコンテスト2024（AtCoder Beginner Contest 340）に参加しました。

結果

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

E問題は色々と考えた結果セグメント木が必要そうな気がしつつ、どんなデータ構造なのかの概要は知っているけど実装方法はしらないし、コードも用意してないので諦めることにした。完全二分木をつかってうまいことやっているらしいことぐらいしか実装面では知らない

A - Arithmetic Progression

初項と項差と末項が与えられるので、項差数列を出力する問題。

forで項差だけ加算した値を出力しつつ末項より大きくなったら処理を打ち切る。 for(int i=初項;i<末項;i=i+項差)の1行で全部表現できる。

B - Append

空の数列に値を入れつつ時々指定された位置の数字を出力する問題。

指定された位置が全部、後ろからk番目となっているので、配列の先頭からに置き換えるとどこになるのかを正しく計算するのがポイントな問題。

数列は配列でも使って表現すれば特に困らない。

C - Divide and Divide

最初に与えられるNを2分割し続けていき全部1にするとき、処理した数値の総和を求める問題。

愚直に1回解いてみたけどTLEになった。
同じ数字が何回も出てきそうだなあと思ったので、メモ化を導入して解くことにした。メモ化を導入したら重複した処理はスキップできて早くなるだろうと思った。

メモ化を導入するために処理を関数に切り出して再帰で処理をできるようにした。それで提出したら数mSecで答えを出しててかなり高速に解けるようになった。

ただどこかでバグがあったみたいでWAだったので、どこが間違っているのか確かめつつそれでもどこがおかしいのかわからないので一部の処理をちょっと手直しして提出したらACできた。

D - Super Takahashi Bros.

ゲームをしていて、ステージクリア時に次のステージに進むかステージXiに進むかを繰り返して最速でステージNにたどり着く秒数を答える問題。

DPっぽいなと思って解いてみたけどサンプルケースで答えが合わないものがあって、これはDPじゃなくてグラフだなと考え直して解いてみたら大丈夫そうだったので提出した。

E - Mancala 2

名前の通りマンカラの石の動きを再現しつつ、最終的な状態を答える問題。

愚直に解く方法なら実装は難しくないけど、石を配る部分で時間がかかりすぎるので石を配る部分の高速化が必要だと思った。

どうにかして早くできないかなと考えたけど、石を配る時点で何個配るかわかっていないと処理が進められないし、各箱に石が何個あるかを計算するには $O(A _ {i})$ 必要なので配列を使っている内は同しようもないなと思った。石を動かす箱の隣から $A _ {i}$ 個となりの箱まで1個ずつ配っていくのでimos法でどうにかできないかなとか考えてみたけどダメそうだし、毎回任意の区間を一括で更新する必要があるのでセグメント木じゃないとどうしようもない気がした。

2024-02-03

日本レジストリサービス（JPRS）プログラミングコンテスト2024（AtCoder Beginner Contest 339）

日本レジストリサービス（JPRS）プログラミングコンテスト2024（AtCoder Beginner Contest 339）に参加しました。

結果

A,B,Cの3問正解でした。 D問題からやけに難しくなった気がする。

A - TLD

.とアルファベットでできた文字列が与えられるので、.で分割したときの最後の要素を出力する問題。
要するに問題の名前通りURLのトップレベルドメインを出力する問題。

pythonなら瞬殺な気がする。
それ以外の言語なら前から順番にアルファベットをメモしていきつつ、.が出てきたらメモをクリアしていき、最後にメモとして保持している文字列を出力すれば解ける。

文字列の扱い方がわかっていれば解ける問題だと思う。

B - Langton's Takahashi

グリッドがあって最初は原点にいるとき、指定されてた手順で行動したときの結果を出力する問題。

指定された通りに処理を実装できれば解ける問題。
工夫する点としては、グリッドはトーラス構造で右端の右が左端、上端の上が下端といった具合にループするので、グリッドの端とか気にせずに移動して移動後の座標からmodを取ればいい感じに座標が循環してくれるので、移動先がグリッドの中かどうかを気にせずに済む。

C - Perfect Bus

バスがあって、バス停毎に乗客の増減だけ与えられるので与えられた情報に矛盾しない現在のバスの乗客の数として考えられる最小値を求める問題。

色々解き方はあるのかもしれないけど、私は二分探索を使って解いた。二分探索で情報に矛盾しない初期のバスの乗客数を求めて、あとはそこから情報を元に人数を増減させていき、最後に何人になっているかを出力した。

2024-01-27

AtCoder Beginner Contest 338

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

結果

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

D問題とE問題どちらとももうちょっと頑張れば解けそうな気がする難易度だった。結局時間内には解けなかったので後で解説を確認して復習しておきたい。

A - Capitalized?

英字の文字列が与えられるので、先頭の文字だけが大文字となっているかどうかを判定する問題。

文字列を1文字ずつ切り出せて、その文字が大文字か小文字かを判定する方法を知っていれば解ける問題。文字列とか文字の扱いに慣れていれば苦労しないくらいの難しさだと思う。

B - Frequency

文字列が与えられるので最頻出の文字を答える問題。

文字列から1文字ずつ取り出して、各文字が何回出てくるかを正しくカウントできれば解ける問題。
文字数のカウントは連想配列を使うなり、要素数26個の配列を用意してaからの何文字離れているかを要素番号にして数えていくなりやり方は色々ありそう。

C - Leftover Recipes

N種類ある材料がそれぞれ $Q _ {i}$ グラムある。 2種類の料理があって、1人前分はどの食材をどれくらい使うか与えられるので最大で何人前の料理を作れるか答える問題。

はじめは幅優先探索でそれぞれ何人前作れるか探索してみたけど、サンプルケースの時点で時間がかかりすぎていた。なので別の解き方を考えることにした。片方の料理の作る数を固定すると、もう一方の料理がどれくらい作れるかは残りの食材のグラム数から簡単に求められる。なので、片方の料理は最大でいくつ作れるか計算して、0個から計算した最大値の範囲で、もう一方の料理がいくつ作れるかそれぞれに計算していき、最大何人前の料理が作れるのかを計算して求めた。

一方の料理は最大でどれくらい作れるのかは簡単に計算できることに気づいたので、片方は線形探索しつつ、もう一方は高速に算出していけば制約を考慮しても間に合いそうだなと思ったので上記の方針で解くことにした。

2024-01-06

AtCoder Beginner Contest 335（Sponsored by Mynavi）

AtCoder Beginner Contest 335（Sponsored by Mynavi）に参加しました。

結果

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

E問題は制約的にTLEしそうだなと思いつつ他には良さそうな方法を思いつかなかったのでとりあえずDFSで実装した。
案の定TLEして一部はREだった。

E問題まで安定して解けるようになりたいなあ。

A - 202<s>3</s>

2023で終わる文字列が与えられるので最後の3を4に変更して文字列全体を出力する問題。

色々解き方がありそうだけど、私は最後の文字以外を出力して、最後に4を出力するように実装した。

文字列の扱い方がわかっていれば解ける問題だと思う。

B - Tetrahedral Number

Nが与えられるので $x+y+z \leq N$ となるx,y,zの組み合わせを辞書順に出力する問題。

Nは最大でも21なので3重ループで全探索しても十分間に合う。なので全探索して条件を満たす場合のx,y,zを順番に出力するように実装して解いた。

多重ループが問題なく実装できれば解ける問題だと思う。

C - Loong Tracking

長さがNある龍が1マスずつ移動するので指定された部位がどの座標にあるのかを答える問題。

各部位は前の部位に追従するので、どのデータ構造を使ってどの部位の座標は今どこにあるのかをうまく管理するのかを考えるのがポイントな問題だと思う。

解説を見るとdequeを使えば良いってあったけどdequeの存在を知らなかったので、長さNの配列を用意しつつ、先頭の座標を保存した位置を指す変数を用意して、 1つずつ後ろにずらしながら新しい先頭の座標を管理していった。

長さNが5だったら、
頭　　　　　　　　　　　　　　最後尾
　頭、胴体、胴体、胴体、尻尾
　胴体、胴体、胴体、尻尾、頭
　胴体、胴体、尻尾、頭、胴体

みたいな感じで、どこを頭にするのかをずらして管理していくことで、頭は移動しつつほかは頭に追従するという関係を表現して座標を管理していった。

この部位の座標が欲しいとなったら、その時先頭となっている位置から数えて指定された部位に相当する場所を計算して該当部位の座標を出力した。

D - Loong and Takahashi

1辺のサイズが奇数の正方形のグリッドがある。中央にはTと書かれているので、残りのマス全部に一筆書きで１から $N ^ {2} -1$ までの数を順番に記入していき、グリッド全体の内容を出力する問題。

一筆書きなら何でも良さそうだけど、左上から渦巻き状に順番に数字を埋めていく方針で実装していった。

今どの方向に記入して行っていて、次に記入しようとしているマスはグリッドからはみ出ていないかとかまだ記入されていないかをもとに記入するか方向転換するかを判断して順番にグリッドを埋めていった。

渦巻き状に埋めていけば良さそうなのはサンプルケースを見ていれば気づけると思うので、あとはそのアイデアを正確に実装できるかどうかな問題だと思う。

E - Non-Decreasing Colorful Path

無向グラフがあって各頂点に数字が書かれているので、
頂点１から頂点Nまで、各数字が広義単調増加になるようにパスを作って、パス上の数字の種類数が得点になる。この時、得点の最大値を求める問題。

時間内には解けなかった。コンテスト中に考えたこととしては以下の通り。

頂点数の制約が結構大きいのでDFSとかBFSでパスを計算してもTLEになりそう
数字の種類数が得点になるのでパスは長いほうが嬉しい。だからダイクストラ法みたいな最短経路を求めるアルゴリズムだと答えは求められなさそう。

他に特に方法も思いつかなかったので、一旦DFSで実装してみた。探索を少しでも減らすために、広義単調増加とならない場合は辺が無いものとしてグラフを作って解いてみたけど、やっぱりTLEした。

その後いろいろ考えてみて、頂点に書かれている数字が同じものは同じ頂点としてマージしたり、 DPで解ければ解けそうな気がするなあと思った。思ったけど残り時間が５分くらいしかなくて実装が間に合わなかった。

2023-12-17

トヨタ自動車プログラミングコンテスト2023#8（AtCoder Beginner Contest 333）

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

結果

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

D問題が惜しいとこまで解けたけどACはできなかった。
前々からちょっと精進不足な気がしてたから、今やってる資格の勉強が終わったら競プロの精進をしばらくしようと思った。

A - Three Threes

1桁の整数がN入力されるので、 NをN回出力する問題。

ループと標準出力ができればACできる問題。

B - Pentagon

正五角形に2本対角線が引かれるから、対角線の長さが等しいかどうかを答える問題。

頂点はA,B,C,D,Eの5つなのでcharとして扱えば辺何本分離れているのかが簡単に求められる。

対角線の一方の頂点がAにあるとすると、もう一方の頂点がB,Eのどちらかにある場合、 C,Dのどちらかにある場合の2通りがあり得る。

なので、上記で求めた辺何本分離れているかからこの2通りのどちらのパターンなのかを判断して、 2本ある頂点両方が同じパターンかどうかを確認して答えを出力した。

C - Repunit Trio

すべての桁の数が1である整数（レピュニット）3つの和の整数のうち小さいものからN番目の数を答える問題。

どうすれば効率よく答えられるか考えてみたけど、結局333通り列挙して、 N番目に小さいものを答えて解いた。

色々考えてみて、規則性とかを確認するために試しにある程度の数を出力してみたら、300個くらいがあっという間に出力できた。なので、Nの最大値である333個以上を予め求めておいて、その中からN番目に小さい数を出力することにした。

D - Erase Leaves

もう少しというところまでは解けたけどACできなかった問題。

木が与えられるので葉を順番に取り除いて言って1を取り除くまでにいくつの頂点を削除するかを答える問題。

頂点1を根とする木として考えて、頂点1に隣接する頂点の下にいくつ頂点があるのかが分かれば答えられそうだなと思った。だからまずは、部分木の頂点数を求める方法を考えることにした。

木構造なのでUnion-Find木を使えば良いかなと思ったけど、標準的なUnion-Findなら頂点の親はわかるけど子はわからないし、子がわからないということは、任意の頂点にぶら下がっている頂点の数も変わらないということなのでちょっと使いづらいなあとなった。

次に思ったのが深さ優先探索で、葉から順番に自分の子孫の数を数えていけば任意の頂点にぶら下がっている頂点の数が簡単に求められるそうだなとなったので、深さ優先探索を使うことにした。

コンテスト中だと、頂点1を根とする木の任意の頂点の子孫の数を一通り求めることができた。あとは、頂点１の隣接している各頂点の子孫の数（部分木の要素数）をもとにどうにかすれば答えを求められるとは思ったけど、ちょっと考察が足りなくてうまく数が合わなかった。

解説を斜め読みするとNから部分木の要素数の最大値を引いたものが答えになるらしい。

2023-11-25

トヨタシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 330)

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

結果

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

C問題を難しく考えすぎてかなり時間を無駄にした。最近まずは全探索を考えるっていう基本を忘れがちだと思った。

A - Counting Passes

問題文の通り実装して答える問題。
N人の点数が入力されるのでL点以上を取った人数を答える。

標準入力と数値の大小判定ができれば答えられる問題。

B - Minimize Abs 1

なんか変数がいっぱい出てきてなんか面倒そうだなと思った問題。

長さNの数列が入力されるから条件を満たす長さNの数列Xを出力する問題。
Xの条件がちょっとややこしい。（Yとか言う変数が急に出てくるのが悪い）

ある範囲[L,R]が指定されるので、 $A _ {i}$ からの距離がこの範囲の任意の値(Y)の距離以下となるような $X _ {i}$ を求めて数列Xを答えるという問題。（ $|X _ {i} - A _ {i}| \leq |Y - A _ {i}|$ となるXを答える問題。）ただし $L \leq X _ {i} \leq R$

$A_{i}$ が $L \leq A _ {i} \leq R$ の時、 $X _ {i} = A _ {i}$ となる。そうじゃないと $Y = A _ {i}$ の時に条件を満たせなくなる。

$A _ {i}$ が $A _ {i} \lt L , R \lt A _ {i}$ のときは $X _ {i}$ は[tex:A{i}]に1番近いRかLになる。そうじゃないとYが[tex:A{i}]に1番近いRかLの時に条件を満たせなくなる。

要するに $X_{i}$ は $|Y - A _ {i}|$ を最小化するYに合わせれば良い。

よって、 $A _ {i}$ が $L \leq A _ {i} \leq R$ かどうかを判定して、 $X _ {i}$ は $A _ {i}$ かRかLのどれかを当てはめれば良い。

C - Minimize Abs 2

非負整数Dが与えられるので $|x ^ 2 + y ^ 2 - D|$ を最小化する問題。

Dの制約が $1 \leq D \leq 2 \times 10 ^ {12}$ となっているのでDはかなり大きくなる可能性がある。

いろいろ考えて迷走した結果かなり時間をロスしてしまった問題。

ACできる解法としては、xかyのどちらか一方を0から $\sqrt{D}$ の範囲で全探索して、他方は $\sqrt{x ^ {2} - D}$ で算出する。そうやって求めたx,yをもとに $| x ^ {2} + y ^ {2} - D |$ を計算していき最小値を答えとして出力する。

最初は、 Dがかなりでかいのと最小値を求める問題だったので二分探索で対応するのかなと思って解いていた。 xとかyを二分探索で探索して $|x ^ 2 + y ^ 2 - D|$ をどこまで小さくできるのかを探索すれば良いのかなと思って解いてた。
よくよく考えると二分探索は単調増加や単調減少する時に適応できる探索方法だけど、今回最小化しようとしている式は単調に変化するような式じゃないから使えない。解き方を考えるときに単調性まで考慮できていればそもそも二分探索は候補に挙がらないなあ…