2024-04-21

AtCoder Beginner Contest 350（Promotion of AtCoderJobs）

AtCoder Beginner Contest 350（Promotion of AtCoderJobs）に参加しました。

結果

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

個人的にはC問題が面白いなと思った。自分でソートを実装してどことどこを入れ替えるかを答えるというのは、ソートの種類ごとの計算量とかを把握していないと実装はできてもTLEしたり交換はN-1回以内とかの制約に引っかかると思う。バブルソートなんて実装したらとてもじゃないけど通せない。

A - Past ABCs

ABCXXXのようにABC＋数字3桁の6文字が与えられるので、それはこれまでに開催されたコンテストの略称かどうかを答える問題。開催されたコンテストはABC001からABC349の範囲でABC316だけは誤答になるのでそこだけは例外的に処理が必要。

単純に処理するなら文字列の大小比較するだけで解けると思う。 ABC001以上かつABC349以下であり、ABC316ではない時はYesと出力して違うときはNoと出力するだけの問題。

プログミング言語的に文字列の大小比較がただの演算子でできるなら特に困らない問題だと思う。

最初の3文字はABCで固定なので後ろの三文字を取り出してどうにかして数値に変換して・・・と処理しても良いけど面倒くさい。

B - Dentist Aoki

最初はN本の歯があってQ回治療を行う。 $T_{i}$ 番目の歯があるなら歯を抜いて、歯がないなら歯を生やす(生やす!?）。最終的に生えている歯の本数を答える問題。

$T_{i}$ が出てきた回数が奇数か偶数かで、その歯は最後抜かれたのか生やされたのかが判断できる。配列でどの歯を何回治療したのか管理して、最後に治療回数が偶数回の歯の本数を数えて出力すればよい。

C - Sort

数列が与えられるのでN-1回以内のスワップでソートする問題。どの位置の数字とどの位置の数字を入れ替えるかを順番に出力して答える。

ソートのやり方はいろいろなアルゴリズムがあるのでまずはその中からどれを実装するか決めて、スワップするときにどことどこを入れ替えたのかを記録していけば解けると思う。
ソートアルゴリズムの計算量を把握して置かないと $O(N^{2})$ とかのアルゴリズムで実装するとTLEになるので注意が必要。

はじめはクイックソートを実装しようとしたけどテストケースのいくつかがWAになった。サンプルは問題ないから微妙なパターンでバグがあったのかなあ。クイックソートがダメだったので選択ソートをベースにしつつ連想配列でどの値がどの位置にあるのかを管理して、未ソートの中の最小値がどこにいるのかをすぐに分かるようにして実装した。

D - New Friends

N人の人がいて、友達の友達は友達と言う考えで友達を増やしていった場合、ユーザー全体では今の状態から最大何人友達を増やせるかを答える問題。

サンプルを手計算しながら考えてみると、以下のことに気づいた。

人のつながりの状況によってはいくつかグループができる。
グループ内だと全員と友達になれる。（友達の友達は友達になれて、その新しい友だちの友達とも友達になれるので、結局グループ内の全員と友達となれる。トポロジー的にはフルメッシュになる。）

なので解く方法としては、人と人とのつながりを元にグループ分けする。グループ内では未設定の友達関係が何組あるのかを数える。

グループ分けする方法は深さ優先探索や幅優先探索、Union-Find木を使うなどいろいろやり方がある。

グループ内で新規に友達となれる組がどれくらいあるのかはグループ内に誰がいるのかと現状何組の友達がいるのかを元に数えていく必要がある。けど、グループごとに配列を用意してまとめて、二重ループでこの組は今友達なのかどうかを確認して、数えてとやってみたらTLEとかWAとかMLEとかになった...
よくよく考えると知りたいのは新規に友達となれる組数だけで、誰と誰が友達になれるのかはあまり重要じゃない。グループごとの人数と、グループ内の友達の組数だけわかれば、最大何組の友達関係が構築できる中で、今この組数しか構築できていない。よって新規に何組が友達になれるかが計算できる。なのでこの組み合わせは友達かどうか確認するのをやめて計算して友だちになれる組数を全グループ分求めて答えることにした。

2024-04-14

AtCoder Beginner Contest 349

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

結果

A,B,Cの3問正解でした。 D問題が解けそうな気がして頑張ってみたけど解ききれなかった。

A - Zero Sum Game

1対1で勝負して勝つとポイントが＋１、負けるとポイントが-1するゲームでN-1人のポイントが教えられるのでN人目のポイントを答える問題。

何試合してもN人全体のポイントの合計は0のままなので、そこに気づけていたら簡単に解ける問題。 N-1人のポイントを合計して、正負を反転させた値を出力すれば解ける。

B - Commencement

文字列が与えられるのでどの文字が何回出てくるか数えて、i回出てくる文字が0種類か2種類だけになっているかを判定する問題。

i回出てくる文字がそれぞれ何種類あるか知りたいので、まずはどの文字が何回出てくるかを数える。次にi回出てきた文字が何種類あるかを数えていき回答を出力する。

連想配列を2つ使えば簡単に解ける問題。 1つ目の配列で文字をキーに出現回数をカウントし、 2つ目の配列で出現回数をキーにその回数出てきた文字の種類数をカウントする。

最後に2つ目の配列の各キーに紐づく値が0か2だけになっているかどうかを確認して回答を出力する。

C - Airport Code

長さ3以上の文字列S（英小文字）と長さ3の文字列T（英大文字）が与えられるので、大文字小文字を無視して、TがSの空港コードとなっているかどうかを判定する問題。

前処理として文字列SとTの大文字小文字をどちらかに統一してから処理する。

あとはSを先頭から見つつ、Tの文字列が順番に出てくるかを確認して回答を出力する。

2024-04-06

トヨタ自動車プログラミングコンテスト2024#4（AtCoder Beginner Contest 348）

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

結果

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

D問題は、これで解けるだろうと思ったアルゴリズムを実装してもTLEが出て最後まで解決できなかった。解説を斜め読みした感じだと、思っていたアルゴリズムだとダメだったみたい。

A - Penalty Kick

問題文のとおりに処理して答えるだけの問題。

１～Nまでの整数のうち３の倍数ではない数の個数を答える問題。剰余演算で１個ずつ３の倍数かどうかを確認して数えれば良い。

ループ処理と剰余演算ができれば解ける問題。

B - Farthest Point

N個の点の座標が与えられるので全組み合わせで２点間の距離を計算して、各点から１番遠い点の番号を順番に答える問題。

指定されている距離の定義はユークリッド距離だけど、ルートが出てくるので距離は小数点以下の値が出てくることになる。小数点以下に値があるということは誤差が出てくるかもしれないので、できるだけ整数の範囲で解きたい。問題をよく読んでみると、答えには求めた距離を出力する必要はなく値の大小関係だけが必要なので、わざわざルートを取る必要はない。

なので２重ループで全組み合わせを試しつつ、ユークリッド距離の２乗を元に各点から１番遠い点の番号を求めて、順番に出力していった。

C - Colorful Beans

色と美味しさがセットになった情報がN個あるので、色でグルーピングしつつ、各グループの美味しさの最小値を求めてから、最小値の中の最大値を出力する問題。

色ごとに美味しさの最小値を管理したいので連想配列を使って色ごとにグループを作る。あとはグループごとの最小値を集めて、その中の最大値を求めて出力すれば良い。

連想配列が扱えるかどうかな問題だと思う。

D - Medicines on Grid

グリッドの一部に障害物があってエネルギーを１消費して隣接するマスへ移動できる。一部のマスには薬があって、使えばエネルギーを指定の値に変更できる。
この時指定されたスタートからゴールへ移動できるかどうかを答える問題。

ただの指定されたスタートからゴールへ移動可能かどうかを答える問題なら深さ優先探索とかで解けば良い、よくある問題。それに対して今回はエネルギーという設定があるのがちょっと違う部分。

だと思って各マスに到達できる最大のエネルギー残量を更新しながら幅優先探索で解いてみたらTLEになった。そのあといろいろ試行錯誤してたけど全然解消できなかった。

2024-03-30

AtCoder Beginner Contest 347

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

結果

A、Bの2問正解でした。

C問題がわからなかった。考えれば考えるほど、この解き方だとこのパターンをうまく落とせないとか、解けはするけどTLEになるなあとか出てきてダメだった。

C問題だけど一旦飛ばしてD問題とかを解きに行ってたほうが良かったのかも。（C問題が解けないなんて思ってもいなかったけど。）

A - Divisible

指示通りに処理する問題。

大体の言語だと%を使えば倍数かどうかの判定ができるので、知っていれば特に困らない問題。標準の入出力と数値計算ができれば解ける問題。

B - Substring

文字列が与えられるので部分文字列の種類数を答える問題。

種類数を答える問題なので重複を除去して答えの候補となる部分文字列を管理したい。なのでsetを使いたい。
setさえ使えれば、部分文字列をsetに入れていき最後にsetのサイズを出力するだけで済む。

C - Ideal Holidays

1週間が休日A日間、平日B日間ある世界で、N個の予定がそれぞれ今から $D _ {i}$ 日後にある。今日が1週間のいつなのかわからないけど、予定全てが休日の可能性があるかどうかを答える問題。

考えれば考えるほど難しいなあと思った問題。

とりあえず何日後と言う情報はそれほど重要じゃなく、何曜日かが重要なので、 $D _ {i}$ をA+Bで割ったあまりに置き換えて、何曜日に予定があるかどうかで考えることにした。ついでに、その曜日に1度でも予定が入っていればそこの曜日は休日になって欲しい曜日候補になるので、 setに $D _ {i}$ をA+Bで割ったあまりの情報を入れて重複を除去することで扱うデータ量を減らすことにした。ここからが全然うまくいかなかった。

愚直に解くなら x番目の曜日を休日の始まりとしてそこからA日間で全ての予定が収まるかどうか　を $0 \leq x \leq A+B$ で確認して1度でも予定が全部休日に収まるxがあれば計算終了で、解答できる。
でもこの方法だと $1 \leq A,B \leq 10 ^ {9}$ の制約的にTLEするパターンがあり得る。

他の方法もいくつか考えてみたけどTLEするパターンしか思いつかなかった。

予定のある曜日と曜日の間が何日空いているかを元になんとかならないかなとも思ったけどうまくいきそうな方法が思いつかなかった。

2024-03-23

ユニークビジョンプログラミングコンテスト2024 春（AtCoder Beginner Contest 346）

ユニークビジョンプログラミングコンテスト2024 春（AtCoder Beginner Contest 346）に参加しました。

結果

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

D問題以降が全然解けなかった。
D問題は問題を読んだ感じだとDPっぽいと思いつつ条件を満たすのはどうすればいいんだろうなあと悩んで解けなかった。 E問題は全然わからなかった。2次元のセグメント木でも実装できれば簡単に処理できそうだなあと思った。

A - Adjacent Product

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

N個数値を受け取るのでi番目とi+1番目の積を順番に出力する。
標準入力と数値計算と標準出力ができれば解ける問題。

B - Piano

鍵盤が無限に長いピアノの白鍵と黒鍵をwとbで表した時、白鍵と黒鍵の数(W,B)が指定された数になる区間があるかどうかを答える問題。

鍵盤1周期が12文字で表されるので数える時の開始位置を12通り試しながら、開始位置からW+B個分の鍵盤の色を数えていき指定した数と一致するかどうかで確認できる。

文字列に0-インデックスでランダムアクセスできるなら、文字列[index]のindexを鍵盤の長さで割った時のあまりに置き換えることでindexを+1し続けても、参照する位置が文字列の最後から先頭へループしてくれるので色を確認してカウントする作業に専念できる。

C - Σ

正整数Kと数列が与えられるので、 K以下の整数のうち数列に含まれない整数の総和を求める問題。

K以下の総和は $(K+1) \times K /2$ で計算できる。そこから、数列に含まれるK以下の数を各種1回ずつ引いていけば答えが求められる。

数列には同じ値が複数存在する可能性があるので数列の中身をsetに入れて重複する値を除去すれば、各数値を1回だけ処理することができる。

2024-03-09

トヨタ自動車プログラミングコンテスト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と参照を更新した。

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

2024-03-02

AtCoder Beginner Contest 343

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

結果

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

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

A - Wrong Answer

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

0~9のうちA+Bと等しくないものを１つ出力すればよいので、 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番目に大きい数を数えていけば答えられると思った。

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