鹿島建設プログラミングコンテスト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
名前の通りマンカラの石の動きを再現しつつ、最終的な状態を答える問題。
愚直に解く方法なら実装は難しくないけど、石を配る部分で時間がかかりすぎるので石を配る部分の高速化が必要だと思った。
どうにかして早くできないかなと考えたけど、石を配る時点で何個配るかわかっていないと処理が進められないし、各箱に石が何個あるかを計算するには必要なので配列を使っている内は同しようもないなと思った。
石を動かす箱の隣から
個となりの箱まで1個ずつ配っていくのでimos法でどうにかできないかなとか考えてみたけどダメそうだし、毎回任意の区間を一括で更新する必要があるのでセグメント木じゃないとどうしようもない気がした。
