2023-01-07

AtCoder Beginner Contest 284

競技プログラミング

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

結果

A,B,C,Dの4問正解でした。 E問題ももう少し時間があれば解けそうな気がした。ぱっと解き方を思いつかなかったから先にF問題解いてみたのが失敗だったな。

A - Sequence of Strings

問題文の通り処理する。

配列に文字列を登録してから逆順に表示すれば良い。
文字列はN個とわかっているのでインデックスをNから1まで順番に減らしていけば良い。

配列の扱い方がわかっているかどうかな問題だと思う。

B - Multi Test Cases

これも問題文の通り処理すれば良い。

具体的には以下の処理をT回繰り返せば良い。

Nを受け取る。
奇数の数をリセットする。
N個のAを受け取り奇数か偶数かを判定する。
奇数ならカウントする。
カウントした奇数の数を出力する。

A問題くらいの難易度の問題をT回解くコードを書けば良い。

C - Count Connected Components

グラフが与えられるので連結成分の数を答える問題。

連結成分の数という点でUnion-Findを使って解くことにした。具体的には、ある頂点同士が辺でつながっているという情報からある頂点をもう一方の頂点のグループに追加していった。
最後に、rootが何種類あるのかをsetを使って数える。 setのサイズ＝連結成分の数になるので、これで答えが求められる。

D - Happy New Year 2023

すごく単純に言うと、合成数Nが与えられるから元になる素数を答える問題。

情報として、素数は2種類だけで $N = p ^ {2} q$ となることがわかっている。

Nは $1 \leq N \leq 9 \times 10 ^ {18}$ とかなり大きいけど、答えとなる素数うち小さい方は $\sqrt[3]{N}$ 以下になる。（もし小さい方の素数さえも $\sqrt[3]{N}$ より大きいなら、 $その素数^{2} \times もっと大きい素数 > その素数^{3} \geq N$ になるから）
なので $\sqrt[3]{N}$ より小さい素数を洗い出してから順番に割り切れるかどうかを確かめる。
割り切れる素数を見つけられたら同じ素数でもう1度割り切れるかどうかを確認する。割り切れないなら $N/割り切れる素数 = p^{2}$ になるのでNを素数で割った後の値の平方根をとる。割り切れるなら同じ素数でさらに割った答えが $q$ となる。

計算量を考えても $O( \sqrt[3]{N} + TM)$ くらいになると思うのでTLEしないで解ける。（Mは $\sqrt[3]{N}$ 以下の素数の数。Nと比べると十分に小さい値になる。）
1番大きいところで $\sqrt[3]{N}$ 以下の素数を探すところだけど、どの値が素数かはNに関わらず一定なのでT個あるテストケースの内最大のNに合わせて素数を列挙しておいて後はテストケースごとに線形探索で素数を1つ見つければ良い。

2022-12-18

HHKBプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 282)

競技プログラミング

HHKBプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 282)に参加しました。

結果

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

D問題がちょっと詰まったけど、少し考え込んでちゃんとACできたのが嬉しかった。

E問題はちょっと考えたけど解き方がちょっと思いつかなかった。

A - Generalized ABC

問題文の通り処理する。

C++なら'A'へ1ずつ加算しながら出力すれば良い。あるいはA~Zまで連結した文字列を用意して先頭からK文字を表示させるのでも良さそう。

B - Let's Get a Perfect Score

N人の中から条件を満たすペア数を出力する問題。

制約を見ると人数は十分小さいし、条件の判定に用いる文字列も十分短い。だから、全通りのペアを順番に条件を満たすか確認していけば良い。

C - String Delimiter

"で括られた文字列か、そうじゃないかを判断しながら、を.に置き換える問題。

文字列の長さはそこそこ長いので $O(文字列の長さ)$ くらいで解けるアルゴリズムじゃないとTLEになりそう。

簡単そうなのは、”で括られている最中なのか”で括られていない部分なのかをフラグで管理しながら線形探索で文字列を見ていく。途中で,が見つかったときに”で括られている最中ではない場合は,を.に置き換える。

最後に編集後の文字列を出力する。

D - Make Bipartite 2

二部グラフかどうかを判定して、二部グラフだったら条件を満たすノードのペア数を答える問題。

二部グラフの判定は、グラフに対して幅優先探索とか深さ優先探索しながらノードを色分けしていき、今注目しているノードの色と隣接しているノードの色が被らないなら二部グラフと判断できる。

二部グラフであることを確認して色分けした後は、辺を追加しても二部グラフのままになるノードペアの数を数えて出力する。ただ、二重ループなどで全ペアを確認していればTLEになるので全通りの数え上げ意外の方法でペア数の計算が必要。

ここで少し躓いたから少し考えた。最終的に欲しいのは、2色に色分けした後で色が異なるノード同士の組み合わせから最初にある辺を除いた数だから、 1色目と2色目のノードの数をそれぞれ数えれば計算して求められることに気づいた。
ノードのペア数はN(N-1)/2で、1色目のノード数がｘ個、2色目のノード数がy個なら
両端が異なる色となるペアの数は　N(N-1)/2　-　｛（x(x-1)）｝/2　-　｛y（y-1）｝/2　になる。ここから最初にある辺の内両端の色が異なる辺が何本あるか数えて上記の計算結果から引けば良い。これならO(1)で算出できるのでTLEしなくなる。

後は、ノードが全部で1つの木（連結成分）になるとは限らないのですべての連結成分に対して上記の処理を行っていく。
全部の連結成分を処理する部分のうまい実装方法が思いつかなかったので、グラフを2色に色分けしているときにやっている探索でチェック済みかどうかを判断するフラグを流用した。具体的には、フラグを確認しながらまだチェックしていないノードを探し、見つかったらそのノードを根として二部グラフの判定から処理を行っていく。一連の処理が終われば次の未チェックノードの探索を再開して、全部のノードがチェック済みになるまで繰り返していく。全部のノードがチェック済になったら計算した結果を集計して答えを出力する。

2022-12-10

AtCoder Beginner Contest 281

競技プログラミング

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

結果

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

コンテスト始めてから気がついたけど、キーボードのvの反応がかなり悪くてペーストが全然できなくなってた。サンプルでテストしたり、コードを提出する時に支障が出まくった．．．

A - Count Down

問題文の通り処理する。

受け取ったNから0までを順番に出力する。ループがちゃんと使えれば特に困らない問題。

B - Sandwich Number

これも問題文の通り処理する。

3つある条件を順番に確認していけば良い。
先頭と最後が文字かどうかの確認は簡単にできると思う。

2番目の条件だけがちょっと面倒くさい。
簡単に言うと、最初と最後の文字を除いた文字列が6文字であることを確認し、先頭から順番に数値を表す文字であることを確認しながら数値に変換していけば良い。変換した後の値が100000 以上 999999なら条件を満たしていると判断する。

C - Circular Playlist

C問題にしては割りと簡単な気がする問題。

まずはN曲の全部の再生時間を求めて、Tをその合計で割った余りを求める。あとは線形探索で何曲目の何秒目になるのかを求める。

D - Max Multiple

解けそうで解けなかった問題。

問題自体は簡単な内容で、非負整数列Aの中から任意のK個の項を選ぶ合計を求めた時どれだけ大きなDの倍数を作れるかを求める問題。

DPかなと思ったけどDP[iまで見た][j個選んだ]＝和の最大値　で考えてみるとちょっと答えは求められなさそうだなと思って別の解き方を考えてみてた。
解説を見るとやっぱりDPだったのでもう少しDPで行けないか考えてみれば良かったなあ。

2022-12-03

デンソークリエイトプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 280)

競技プログラミング

デンソークリエイトプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 280)に参加しました。

結果

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

C問題までは相変わらず楽勝だったけど、D問題が解けそうで解けなくてもどかしかった。

A - Pawn on a Grid

与えられた複数の文字列の中から指定された文字が全部で何文字あるかを数えて答える問題。

文字列の数や、各文字列のサイズが対して大きくないので全探索で十分間に合う。

文字列の扱い方を知っているかどうか確認する問題かな。

B - Inverse Prefix Sum

とある数列を求めて答える問題。

与えられる数列Sは答えるべき数列の和となっている。 $S _ {1} = A _ {1}, S _ {2} = A _ {1} + A_ {2} ,・・・$

なので求めたい $A _ {i}$ は $S _ {i}$ と $S _ {i-1}$ の差となる $S _ {i} - S _ {i-1} = ( A _ {1} + A_ {2}+・・・+ A _ {i} ) - ( A _ {1} + A _ {2}++ A _ {i-1} ) = A _ {i}$

よって $A _ {1}$ から順番に計算して出力すれば良い。

C - Extra Character

文字列SとSのどこかに1文字追加した文字列Tが与えられるので、Tの何文字目が追加された文字なのかを答える問題。

文字列のサイズ的に線形探索してもTLEにはならないのでSとTを先頭から順番に見ていって、初めて不一致となる文字が何文字目なのかを答える。 Sの文字数分確認して不一致となる文字がなかった場合はTの最後の文字が追加された文字となる。

D - Factorial and Multiple

ある整数Kが与えられるので $N!$ がKの倍数となる最小のNを答える問題。

問題文を読むとKを素因数分解するか約数列挙してどうにかすれば良さそうと言うのは考えたけど、その後どうすればどんなパターンでも統一的に解けるのか思いつかなかった。

考察としては以下くらいは思いついた。

$2 \leq K \leq10 ^ {12}$ なのでO( $\sqrt{N}$ )くらいで解かないとTLEになりそう。
Kの倍数になると言うことはKで割った余りが0になる。（ $N !$ mod K =0）

2022-11-26

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

競技プログラミング

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

結果

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

D問題のデバッグにすごく時間が掛かった… 解き方の方針自体は問題文を読んで直ぐに思いついたけど、サンプルケースの答えとなかなか一致しなくて延々とデバッグをしていた。

三分探索すれば良いのは直ぐわかっていたから、最終手段として蟻本とか鉄則本でコードのサンプルを探そうとして索引を見てみたけどまさか扱っていなかったとは…

A - wwwvvvvvv

文字列中のvの数とwの数を数えてvの数+2*wの数を出力する問題。
文字列の扱い方の練習みたいな問題。

B - LOOKUP

TがSの部分文字列になっているかどうか判断する問題。文字列ライブラリの検索処理を使えば直ぐに判断できる。

もしくはSを線形探索してTと同じ文字列部分があるかどうかを順番に見ていけば良さそう。文字列の長さ的に愚直に線形探索しても間に合いそう。

C - RANDOM

同じサイズの2種類の格子が与えられるので、一方の列を並び替えてもう一方の格子が作れるかどうかを判断する問題。 2重ループとソートで解ける。

まず2種類の格子それぞれの列成分の配列を作る。（格子を行列をみなした時に転置行列を求める）あとはそれぞれの配列をソートして、各要素の文字列が一致しているかどうかを確認する

例
ABCD
EFGH
IJKL
と言った具合に格子があれば
S1=ABCD
S2=EFGH
S3=IJKL
と変数では保存しているので、（入力を受け取る関係で大体の言語だとこう管理するよね…）
S'1＝AEI
S'2=BFJ
S'3=CGK
S'4=DHL
と変換したものを配列で管理して、その配列をソートする。

元の格子の列を並び替えて一致させられるなら、2つの格子の転置をソートすると全く同じ並びになるはず。

D - Freefall

下に凸な関数の最小値を求める問題。

問題文を読むと求める答えは下に凸な関数の最小値っぽいと気が付いた。凸関数の最大値、最小値なら3分探索で求めることができるのでサクッとコードを書いた。
でも微妙にバグってたせいでサンプルケース3がなかなか答えが一致しなくて延々とデバッグしていた。

時間ギリギリでなんとか解けたけどすごく時間がかかった。

2022-11-19

AtCoder Beginner Contest 278

競技プログラミング

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

結果

A,B,C,D,Eの5問正解でした。時間内にAからEまでの5完できたのは初めてな気がする。
F問題みたいなゲームっぽい内容の問題は解き慣れていないので考え方がわからないや。解く練習しておかないとなあ。

A - Shift

いろいろな解き方ができそうな問題。

答えるだけならK+1個目からの末までの要素を出力しつつ、0をK個出力すれば良さそう。
問題文のとおりに処理するならキューで実装すれば指示通りの内容を再現できる。

B - Misjudge the Time

問題文の通りに判定しつつ、線形探索して解いた問題。

入力を文字列として受け取るか数値として受け取るかちょっと迷った。線形探索するなら数値のほうが加算しやすいのと、各桁の値は割り算や除算で取得できるので入力は数値として受け取って処理していった。

まずは時と分に対して 10で割ったり、10の余りを求めたりして各桁の値を取得した。次に指定された条件を満たすのかを確認し、条件を満たさなかったら分を加算しつつ時を繰り上げたりした上で、24や60の余りで更新して24時を超えても困らず処理できるようにしていった。

C - FF

連想配列を使えばあまり困らずに解ける問題。

個人的にはC++の連想配列はちょっと遅いと思っているから要素数が多くなってくるとTLEにならないか心配になる。

解き方は、2次元の配列などで誰が誰をフォローしているのかを管理しつつ、チェックするときには双方向でフォローされれているのかを確認して答える。

D - All Assign Point Add

クエリを受け取って、数列全部を指定した値に一括更新したり、指定した要素の値を加算したり、指定した要素の値を出力する問題。
ちょっとどうやって解くか悩んだ。セグメントツリーを使えば一括更新とか楽そうだなと思った。

指定した要素の値の加算や、指定した要素の値の出力は困らずできると思う。問題は数列の要素すべてを指定した値に更新する部分だと思う。
配列で管理していれば一括更新する度に $O(N)$ で処理することになるのでクエリの最大サイズも考慮するとTLEしそうだなと思った。

最終的に、最後に一括更新した値と、最後に一括更新して以降どの要素にどれだけ加算されているのかを管理して、指定した要素を出力するときは一括更新の値＋指定要素に加算した値を出力した。
指定要素にどれだけ加算されているかは連想配列を使った。もしも普通の配列を使ったら一括更新のたびに全部0に更新する処理が必要になって毎回 $O(N)$ だけ処理が発生するからたぶんTLEになる。連想配列ならクリアするだけで済むのでそんなに処理はいらない。

E - Grid Filling

格子の一部をマスクするからマスクされていない部分の情報を出力する問題。マスクされていない部分にある整数の種類を答えるのが少し厄介だと思う。

マスクする領域は少しづつ動くのでマスクされなくなったマスと新たにマスクされるマスの情報をもとに現状の情報を更新していけば、毎回全マスを確認して答える必要はなくなる。
どの値が何個あるかは連想配列を使って管理した。マスク部分をずらしてからの情報更新が完了したらforeach文を使ってマスクされていない部分に1以上ある値を列挙し、その数値をsetに入れていった。最終的にsetのサイズが数値の種類数になるのでsetのサイズを出力していった。