れとろのメモ置場

とあるSEのメモ置場

トヨタ自動車プログラミングコンテスト2024#3(AtCoder Beginner Contest 344)

トヨタ自動車プログラミングコンテスト2024#3(AtCoder Beginner Contest 344)に参加しました。

結果

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

久々に5問正解できた。
F問題は見てみたらDPっぽいなあと思いつつどうやって解くか詰めていたら時間切れになった。

コンテストのパフォーマンスが1200超えてた!これが毎回できれば水色に上がれるのかあ。

A - Spoiler

|が2つ混じった英字の文字列が与えられるので|と|に囲まれた部分を除去した文字列を出力する問題。

問題文の通り処理すれば解ける問題。

Pythonならsplitを使って|で文字列を分割して最初と最後の要素だけ出力すれば解けそう。

C++にはsplit関数はないので、文字を解答として出力するかどうかのフラグを用意して、|が出てくるたびにフラグを反転させて文字を出力するかどうかを制御した。こうすることで|で括られている部分はフラグにより出力しないので、 出力結果は欲しい文字列になる。

A問題にしては普段に比べてちょっと難しい気がする。

B - Delimiter

最終項が0で要素数が不明な数列が与えられるので数列を逆順に出力する問題。

問題文の通り処理して出力すれば解ける問題。

最終項が0なのはわかっているので、0が出てくるまで入力を受け付け続ける。 0を受け付けたら、数列を逆順に全部出力した。

C - A+B+C

数列が3つ与えられるので各数列から数字を1つずつ選んで指定された値が作れるかどうかをQ回答える問題。

制約を見るとQは1 \leq Q \leq 2 \times 10 ^ {5}なので各質問はO(1)で答えられないとTLEしそう。
各数列のサイズは 1 \leq サイズ \leq 100なので全通り計算すると最大 10 ^ {6}回計算が必要になる。 これはTLEしないで処理できる量なので1回だけなら全通りの計算ができる。
なので、あらかじめ全通り計算して作り出せる値をすべて求めておきO(1)で回答することにした。

計算した結果を連想配列を使って管理して、数値を引数にしてその数が作れるかどうかを判断できるようにした。

D - String Bags

問題文を読んでDPで解く問題っぽいなと思いながら考察していった問題。

袋がいくつかあって、各袋の中にそれぞれいくつかの文字列が入っている。順番に各袋の中の文字列を選択したりしなかったりして、指定された文字列を作れる場合の最小コストを答える問題。(コスト=文字列を選んだ個数)

袋の数は最大で100あって、各袋の中に文字列は最大10個あるので、全通り計算するには10 ^ {100}通りの計算が必要になるので試すまでもなくTLEになりそう。

ということで全通りの探索は諦めてDPで解くことにした。
DP[袋iまで選択][j文字目まで作った]=最小コスト

としてDPで処理していくことにした。

E - Insert or Erase

与えられた数列に対していくつかクエリを実行して最終結果を出力する問題。

クエリの種類が、指定されたある値の後ろに別途指定された値を追加するか、指定された値を削除するかの2種類。
色々考えたけど、双方向リストみたいに自分の値の前後の値を管理すれば解けそうだなと思ったので頑張って実装した。 具体的にはUnion-Findみたいな発想で、ある値の前の値と後ろの値をそれぞれ連想配列を使って管理した。
 a → x  → A にyを追加するなら a → x → y → Aと参照を更新して、 削除するなら a → Aと参照を更新した。

双方向リストを知っていれば、どう実装すればよいかの考え方を持っているので実装方針は悩まずに時始められると思う問題。

-

AtCoder Beginner Contest 343

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

結果

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

E問題が訳わからなすぎたのでF問題を解こうとしてみた。 多分セグメント木を使って解く問題なんだろうなと思ったけど、セグメント木のソースを用意していないし、 アルゴリズムもよくわかっていないのでぶっつけ本番で実装するのは無理だった。
1時間くらいは時間があったからセグメント木のアルゴリズムとか説明しているサイトを見ながら実装しようとはしたんだけど…

A - Wrong Answer

問題文の通り処理する問題。

0~9のうちA+Bと等しくないものを1つ出力すればよいので、 A+Bが0かどうか確認して、0じゃないなら0を0なら1を出力するくらいの実装でACできる。

B - Adjacency Matrix

接続行列が与えられるので、各頂点に接続している頂点を昇順に出力する問題。

頂点1から順番に処理しつつ、
頂点1から順番に今処理している頂点に接続しているかどうかを確認して、接続していればその頂点番号を出力していけば良い。

ループ処理をうまく使えば2重ループで簡単に処理できる。

C - 343

N以下の整数のうち立方数かつ回文となっている整数の最大値を出力する問題。

Nは10 ^ {18}以下の正整数なので線形探索するには流石に無理がある。
N以下の立方数だけを対象に回文かどうかを判断して条件にあう数を探すことにした。

こんな具合にforでループさせるとN以下の立方数(i*i*i)だけを対象に探索ができる。

for(long long i=1;i*i*i<=N;i++)

ある数が回文になっているかどうかは1桁ずつ分解して先頭からi番目と後ろからi番目が同じ数字になっているかどうかで確認した。

D - Diversity of Scores

コンテスト中、誰がどのタイミングで何点取るかがわかるので、毎秒選手たちの得点は何種類の値があるかを答える問題。

どうやって値を管理しようか悩んだけど愚直に解くことにした。 選手の得点を管理する変数と、連想配列で何点の選手が何人いるか管理する配列、今得点には何種類の値があるかを管理する値の3つを組み合わせて答えた。

ある時点で選手が得点すると、もともと何点で得点後は何点かをもとに、何点の選手が何人いるかの変数をメンテして、 その結果ある点数の人数が0になったりある点数の人数が0人から1人になったりをもとに、今得点には何種類の値があるのかの変数をメンテしていった。

F - Second Largest Query

数列が与えられるので指定した要素の値を更新したり、指定された区間で2番目に大きい数は何個あるかを答えたりする問題。

配列の一部の要素を更新しつつ、指定区間で条件を満たすものを答える系の問題なのでセグメント木を使って解く問題だと思った。

セグメント木はアルゴリズムを理解して自分用にコードを作ろうと思いつつ後回しにしていたので細かいアルゴリズムはわからず解くのは諦め気味だった。

セグメント木のアルゴリズムとかを説明しているサイトを見つつ即席で実装を始めてみたけどちょっと間に合わなかった。

考えた解き方としては2つセグメント木を用意して、一方では指定された区間の1番大きい数、2番目に大きい数のペアを管理して、もう一方の木で指定区間で2番目に大きい数を数えていけば答えられると思った。

最近セグメント木を使う問題の頻度が高い気がするから早めにソースを用意しておきたい…

トヨタ自動車プログラミングコンテスト2024#2(AtCoder Beginner Contest 341)

トヨタ自動車プログラミングコンテスト2024#2(AtCoder Beginner Contest 341)に参加しました。

結果

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

D問題が難しかった。コンテスト後に解説を読むと割と惜しいところまでは考察があってたっぽい。

A - Print 341

101010・・・101のように0をN個と1をN+1個交互に出力する問題。

特に悩む要素はなくN個10を出力してから1を出力すれば良いだけの問題。

B - Foreign Exchange

N種類の通貨があって、通貨i Si単位をを通貨i+1 Ti単位に両替できる。このとき通貨Nは最大いくつ取得できるかを答える問題。

通貨はiからはi+1にだけ両替できるので、通貨1から順番に両替できるだけ両替していけば 通貨N-1を通貨Nに両替できるだけ両替すれば通貨Nの量を最大にできるようになる。

C - Takahashi Gets Lost

グリッドがあって、各マスは海か陸のどちらかでできている。陸だけを移動した時の上下左右の移動情報が与えられるので初期位置の候補数を答える問題。

ある位置が初期状態としてあり得るかどうかは、そこから移動情報通りに移動させたときに1度も海の上を通過しないかどうかでしか判断できないので、全通り確認して判断した。

制約を見ても全通り確認するのは処理時間的に十分余裕があるので、 初期位置を渡すと候補としてあり得るかどうかを検証して結果を返す関数を作ってから 全通りの確認を実装することにした。

D - Only one of two

NとMの倍数のうち、公倍数を除いたものの小さい方からK番目のものを出力する問題。

あれこれ考えて実装してみたけど制約ギリギリの場合だとTLEになるばかりで全然解けなかった。

最小公倍数以下だと条件を満たす数がいくつあるか数えつつ、K番目の数は公倍数何倍分+αなのか計算して α分をどうにかして求めようとして解いてた。

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

鹿島建設プログラミングコンテスト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法でどうにかできないかなとか考えてみたけどダメそうだし、毎回任意の区間を一括で更新する必要があるのでセグメント木じゃないとどうしようもない気がした。

日本レジストリサービス(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

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

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

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個から計算した最大値の範囲で、 もう一方の料理がいくつ作れるかそれぞれに計算していき、最大何人前の料理が作れるのかを計算して求めた。

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

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と書かれているので、 残りのマス全部に一筆書きで1からN ^ {2} -1までの数を順番に記入していき、グリッド全体の内容を出力する問題。

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

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

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

E - Non-Decreasing Colorful Path

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

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

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

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

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