れとろのメモ置場

とあるSEのメモ置場

Toyota Programming Contest 2023 Spring Qual A(AtCoder Beginner Contest 288)

Toyota Programming Contest 2023 Spring Qual A(AtCoder Beginner Contest 288)に参加しました。

結果

A,B,Cの3問正解でした。
D問題がやけに難しかった。一旦おいておいてE問題を解いたほうが良かったかも。 E問題はさっと問題文を読んだ所感だとDPで溶けそうな問題だと思った。

A - Many A+B Problems

問題文の通り処理する。

標準入力でちゃんと数値を2つ受け取れれば困らない程度の難易度のいつも通りのA問題。

B - Qualification Contest

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

N個の文字列を受け取りつつ、前からKだけ保存してからソート後に順番に出力する。

ソートがわからないならsetに入れてソートはプログラム側に任せておいてsetの先頭から順番に出力させるのでも良いと思う。

C - Don’t be cycle

グラフの閉路を検出する問題だと思う。

閉路をなくすために辺を削除するけど最少で何本の辺を削除すれば良いかを答える問題。 閉路が1つあったときに閉路じゃなくすには辺を1本削除すれば良いと思ったので、削除する辺の最小値=閉路の数と考えた。

閉路の検出は深さ優先探索かUnion-FindでできるのでUnion-Findで処理した。 具体的にはノードを2つ併合するときにそれぞれの親が一致していれば閉路ができると判断した。

D - Range Add Query

思ってたよりも難しい問題だった。そこそこ時間を使ったけど結局解けなかった。

数列Aが与えられるのでQ回条件を満たすかどうかを答える問題。
条件は数列Aの一部の区間が指定されるのでその区間の部分数列に対して、 連続するK個の要素に任意の値cを足す という処理を0回以上行い部分数列の全要素を0にできるかどうか。

ちょっと面倒な問題をQ回解くとみなして考えてみていた。
気がついたこととしては

  • 各処理は独立して行われるので処理の順番は入れ替わっても問題ない。
  • 連続するK個の要素の内先頭の項番をiとすると、何回でもiを選択していいけど毎回の処理は独立しているので各iは1回だけ選択すれば十分
  • 全部0にできるかと言うのは全部0の状態からその状態へ遷移できるかと同義なので全部0の状態から考えたほうが良い事が多い

ということで考えていくとi=1から順番に処理していくとして考えていったほうが考えやすそうと思った。

次にcはどうやって決めていくかを考えてみたけど、i番目の項の値はK-1個前から1個前までのcの値の和に影響すると気づいた。 なんとなくフィボナッチ数列っぽなあと思ってcを求める処理を実装してみた。

iの範囲が1~n-K+1なのでn-K+1番目の項までは確実に0にできるので、n-K番目~n番目の後までが0にできるのかどうかを確認してYes,Noを出力させるように実装してみた。 でも結局コンテスト時間には間に合わなかったし、提出してみるとTLEになって散々な結果だった。