れとろのメモ置場

とあるSEのメモ置場

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回繰り返せば良い。

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

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つ見つければ良い。

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色目のノード数がx個、2色目のノード数がy個なら
両端が異なる色となるペアの数は N
(N-1)/2 - {(x(x-1))}/2 - {y(y-1)}/2 になる。 ここから最初にある辺の内両端の色が異なる辺が何本あるか数えて上記の計算結果から引けば良い。 これならO(1)で算出できるのでTLEしなくなる。

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

AtCoder Beginner Contest 281

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

結果

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

コンテスト始めてから気がついたけど、キーボードの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 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(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がなかなか答えが一致しなくて延々とデバッグしていた。

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

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のサイズを出力していった。

大和証券プログラミングコンテスト2022 Autumn (AtCoder Beginner Contest 277)

大和証券プログラミングコンテスト2022 Autumn (AtCoder Beginner Contest 277)に参加しました。

結果

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

D問題は問題文を読んで難しそうだったから後回しにした。E問題を終わらしてから解き始めたけど最初に思っていたよりは難しくなさそう。

A - ^{-1}

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

与えられた数列Pのうち指定されたXとなる項番を出力する問題。
ループで先頭から順番に値がXとなる項を探していけば良い。数列の長さも最大で100程度なので線形探索で十分間に合う。
項数が大きいと何かしらの工夫が必要になってくる。

B - Playing Cards Validation

これも問題文の通りに実装するだけの問題。

3つの条件を愚直に実装すればいいけどちょっと手間がかかる。 1つ目と2つ目の条件に関わる文字を連結して文字列にしておいて、チェックしたい文字がその文字列に含まれるかどうかを検索すれば判定は楽にできそう。(コンテスト後に気づいたから本当に解けるかの確認はしていないけど)

C - Ladder Takahashi

1階層をノード、はしごを辺とみなすと、
ノード数が極端に多いけど辺の数はそれほど多くないグラフでどれだけノード番号が大きいノードにまでたどり着けるかを答える問題と見なせる。

深さ優先探索幅優先探索で探索すれば十分だと思う。(ノード数が多すぎるので線形探索だと10 ^ {9}階まで探索する前にTLEになる。そもそも線形探索だとどうやって解くのかすぐには思いつかないけど…)
工夫すべき点としては以下かなと思う。

  • 辺のないノードの方が圧倒的に多いので辺を持つノードだけを対象にして、辺を持たないノードは存在しないものとして扱う。

今回は連想配列を使って辺を持つノードだけ隣接ノードを管理した。 あとは普通の幅優先配列でどれだけ上の階層へ行けるのかを更新しながら処理をしていった。

D - Takahashi's Solitaire

問題文にmodとか出てきてなんか面倒そうな印象を受けた問題。
問題文をよく読むとそれほど難しくなかった。結局、手札から好きな数字のカードを1枚出して、以降はそれと同じか1大きな数字のカードを出し続ける。数字の最大値はM-1でその次に出せるカードは0といった具合に大小関係が循環している。

最終的に手札のカードの数字の合計をどれだけ小さくできるのかを答える問題。

まだACはできていないけど問題文を読んで考えた方針としては以下の通り。

  • 手札Aはソートしても問題を解く上では問題ない。
  • 数字がXのカードを出したとして、手札にXがある限りXを出し続け、XがなくなってからX+1のカードを出す。
  • はじめに手札の数字の和を求めておいて、捨てるカードにかかれている数字をまとめて引く。
  • XとX+1が連結していると考えて、尺取法あたりで連結部分のカードに書かれている数字の和を求めて、1番和が大きい部分を手札から捨てることにする

コンテスト後の時間も使って上記を実装してみたら一部がWAだった。コーナーケースかなあ。

E - Crystal Switches

ちょっと変わった最短経路の距離を求める問題だと思った。

変わっていると思った部分は、以下の通り。

  • スイッチの状態に応じて辺の通れるかどうかが変化する。
  • 一部のノードでは辺の通れる・通れないの状態を一斉に反転させられる

通常のダイクストラ法に状態管理の要素を加えれば良さそうだと思ったので、ダイクストラ法をベースとして解いていった。 大きくは以下の変更をした。

  • 辺の情報に初期状態で通れるかどうかを追加する。
  • ノードの情報にスイッチを持っているかどうかを追加する。
  • 優先度付きキューで管理する情報にスイッチのON/OFFの状態を追加する。
  • 距離を管理する配列の次元を1つ増やしてスイッチがONのときの最短距離、スイッチがOFFの時の最短距離を管理する。

あとは距離情報を比較・更新する処理でスイッチの状態を考慮するようにした。

実装にちょっと時間がかかったけど一通り実装したら大きな問題もなくACできた。