れとろのメモ置場

とあるSEのメモ置場

AtCoder Beginner Contest 252

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

結果

A,B,Cの3問正解でパフォーマンスが823でした。

C問題が少し苦戦した。解き方が何通りもあってどれをどう実装しようと悩んだ…
ぱっと思いついたアイディアを実装に落とし込むまでの思考が発散して逆に混乱した。

D問題は余事象考えて全通りから引けば良さそうなところまではすぐに思いついたけど、余事象を数える部分がうまくできなかった…

A - ASCII code

ASCIIコードの値が渡されるから対応する文字を表示させる問題。

C++だとchar型の中身がASCIIコードなので、受け取った数値をchar型として表示させれば良い。
入力をキャストして出力されるだけなので瞬殺だった。 コンテスト始まって1分以内で提出までできてて、たぶんこれまでの中での最速ACだと思う。

B - Takahashi's Failure

おいしさ最大の食品群のなかに嫌いな食品が含まれるかどうかを判定する問題。

おいしさ別にiのリストを作成して、おいしさ最大のリストの中にB _ {i}を含んでいるかどうかを確認して答える。

C - Slot Strategy

0から9それぞれを揃えようとしたときの時間のうち最小のものを答えれば良い。
N個あるリールのうち揃えようとしている文字がそれぞれ何文字目かを調べて最大値を取れば全部揃えるときの時間になる。
例外として複数のリールで同じ箇所に揃えようとした文字が被っている場合で、そのときは被っているうち2つ目以降のリールは1周分ずつ余計に時間が必要になる。

D - Distinct Trio

解けそうな気がしたけど解けなかった。
計算時間を気にしないなら愚直に3重ループで一応答えは求められるけどTLEになる。

求めたいことの余事象はA _ {i},A _ {j},A _ {k}の中で被りがあるi,j,kの組み合わせになるから、余事象の数を求めて全組み合わせ数から引けば良さそうなのは思いついた。
結局余事象の数え上げがうまく実装できなかったので解けなかった。

パナソニックグループプログラミングコンテスト2022(AtCoder Beginner Contest 251)

パナソニックグループプログラミングコンテスト2022(AtCoder Beginner Contest 251)に参加しました。

結果

A,B,Cの3問ACで、パフォーマンスが1082でした。

D問題は問題を読んで難しそうなので一旦E問題を読んで、解きやすそうなE問題を先に解いてみた。 提出者数とか正解者数を比べるとD問題よりE問題の方が多いのでみんなD問題を飛ばしてE問題を先に解こうとしたみたい。

C問題までは10分少々でACできてコンテスト中の殆どの時間を使ってD問題以降を解こうとしたけど1問も解けなかった…
最近あんまり精進していないから解ける問題のレパートリーが増えてなくて、今までの蓄積+地力で解ける問題しか対応できてない。

A - Six Characters

問題文の通り文字列を表示させる。

文字列を何回か繰り返し連結して先頭から6文字の部分文字列を出力させたり、 for分とかのループで i%(文字列の長さ)番目の文字を6回表示させたり、解き方は色々ある。

B - At Most 3 (Judge ver.)

全通り探索すれば解ける問題。

選ぶ重りは3個以下なので1個、2個、3個の場合それぞれをループで探索して確認すれば良い。 重りの数Nもたかだか300程度なので3重ループで探索してもTLEにはならない。

C - Poem Online Judge

重複があるかもしれない文字列集合の中から、初めて登場した文字列を対象に文字列に紐づく点数の最高点は何番目の文字列かを探索して答える問題。

マップで文字列が出てきたかどうかのフラグを管理して、確認した中での最高点とその時の提出番号を控えつつ
初めて登場した文字列の場合は、マップのフラグを更新。点数を確認して最高点が変わる場合は最高点と提出番号を更新する。 最後に控えていた提出番号を表示させた。

文字列が既出かどうかの判定はマップを使う以外でもできそう。例えばsetに確認済みの文字列を保存していき、今から確認しようとしている文字列をsetに入れる前後でsetのサイズが変わるかどうかで その文字列が新規か既出か判断できそう。

E - Tahakashi and Animals

もう少しで解けそうで解けなかった…

問題自体はDPを使えば解けそう。DP[i番目の行動を][する・しない]=費用の最小値 でi=1から順番に更新していけば答えが求められそう。 問題は行動1と行動Nで動物1に餌をやることが被るのでその部分がややこしいなと思った。

解説を読んでみると行動1を行う場合・行わない場合を固定して解いてそれぞれの結果をマージすれば良いっぽい。
このパターンはこういう解き方をするっていうのが決まっている典型パターンの1つみたい。

モノグサプログラミングコンテスト2022(AtCoder Beginner Contest 249)

モノグサプログラミングコンテスト2022(AtCoder Beginner Contest 249)に参加しました。

結果

A,B,C,Dの4問ACでした。 C問題で何を答えれば良いのかを理解するのに時間がかかった…問題文がややこしくてよく意味がわからなかった…
たまにこんな風に何を言っているのかよくわからない問題があるけど、これは自分の読解力が足りないのか?
D問題はデータ型をlong longじゃなくてintにしたところがあったのが原因で1WA。5分くらい無駄にした。

A - Jogging

A問題にしては難しい問題だと思う。愚直にシミュレートして答えるしかなさそう。

まずは、歩く時間+休む時間を1セットとして考えてX秒で何セット繰り返すかを計算する。 セット数\times歩く速さ+1セットを満たさず余った時間で進む距離 がX秒で進む距離になる。

これを二人分計算して距離の大小比較をして長い距離を進んでいる方を答える。

B - Perfect String

3つの条件を全部を満たすかどうかを確認して答える問題。 文字数の制約を見るとせいぜい100文字程度なので1文字づつ確認していけば時間は余裕で間に合う。

C++だと文字は数値で扱われるので'a' \leq S _ {i} \leq 'z'みたいに比較演算子で判定できる。 大文字が出てくる、小文字がでてくるはフラグで管理した。 全ての文字が相異なると言うのは、1文字づつsetに入れた後のsetのサイズと文字列のサイズが一致しているかどうかで判断した。

C - Just K

問題文の意味がよくわからなかった。

とりあえず簡潔に言い換えると以下になると理解して問題を解いていった。

  1. 好きな数の文字列を選択する
  2. どの文字が何回出てくるか数える
  3. 出現回数がK回の文字が何個あるか数える
  4. 3の個数の最大値を答える。

1の部分はbit全探索で対応した。Nは最大でも15で2 ^ {15}は32768で10 ^ {4}程度なのでbit全探索部分だけでTLEすることはない。

2の部分は事前に文字列毎にどの文字が何回出てくるかを集計しておき、選択した文字列分の集計結果を合計すれば良い。

3の部分は、2の計算結果がKとなっている文字の数を数えた。

4の部分は、bit全探索内で3の結果の最大値を更新し続けて最終的な最大値を答える。

問題文がよくわからなかっただけで、ACするためのアルゴリズム自体はそこまで難しくないと思う。bit全探索を知っている・実装できるなら解ける問題だと思う。

D - Index Trio

問題文を読むと最初は、ちょっと難しそうな問題だと思った。
問題文を読んでの考察としては

  • 制約的にはNに関する二重以上のループで解こうとするとTLEになるのでNに関しては1重のループで解けないとACできなさそう。
  • 愚直に解こうとするとO(N ^ {3})でTLEする。
  • こういったパターンの問題はi,j,kのうちi,jが決まればkが確定する事が多くO(N ^ {2})までは計算量を削減できる場合がある。
  • \frac{A _ {i}}{A _ {j}} = A _ {k}のままだと割り算の部分で誤差が出てWAになりそうなので式変形してA _ {i} = A _ {j} \times A _ {k}で考えたほうが良さそう。
  • A _ {i}A _ {j}の倍数
  • 整数列Aの順番はそれほど大事じゃないのでソートしても問題ない。

これくらいのことを考えつつ、素数判定でよく出てくるエラトステネスの篩を連想して、

  1. A _ {j}の倍数のうちA _ {i}となるものがあるかどうかを確認する。
  2. A _ {i}となるA _ {j}の倍数があったときA _ {j}に掛けた数がA _ {k}になる。

これで条件を満たすA _ {i}、A _ {j}、A _ {k}が1パターン求められた。
この方法だとNに関するループは1重で、ループの中でもそれほど計算量はなさそうなのでTLEしなさそう。(ループの中は多分O(logN)くらい。エラトステネスの篩でもそれくらいだったと思うから。)

後は、事前に数列Aではどの値が何回出てくるかを数えておけば、A _ {i}の個数 \times A _ {j}の個数 \times A _ {k}の個数でこのA _ {i}、A _ {j}、A _ {k}のパターンの組数が計算できる。

これらをうまく実装できればACできる。

数列Aではどの値が何回出てくるかの管理をintでやっていてオーバーフローしたせいで1WAした。ちょっともったいない…

E - RLE

難しくて解けなかった。 問題を読んで動的計画法だと解けそうな問題だと思った。ただ、どんなふうにデータを管理すればうまくいくのか考えがまとまらなかった。

ユニークビジョンプログラミングコンテスト2022(AtCoder Beginner Contest 248)

ユニークビジョンプログラミングコンテスト2022(AtCoder Beginner Contest 248)に参加しました。

結果

A,B,C問題のの3問ACでした。 C問題まではサクッと解けたけどD問題は全然分からなかった…

A - Lacked Number

問題文の通り解けば良い。
0~9まで出てきたかどうかをフラグ管理して、出てきていないものを表示させれば良い。 C++なら文字を数値に変換するのは数値を表す文字から'0'を引けば良い。
例:'9'-'0'

B - Slimes

問題文の通りに解けば良い。

ループ文でスライムの数がB以上になるまでK倍し続けて、何回K倍にしたのかを答える。
A=1、B=10 ^ {9}、K=2の場合でも答えが30程度なので愚直に解くのでも十分間に合う。

C - Dice Sum

DP[x][ \sum\limits_{i=1}^{x} A_i ]=何通り としてDPで解けば良い。

\sum\limits_{i=1}^{x} A_iの最大値でも2500程度なのでメモリ不足とか配列が確保できないとかにはならない。

D - Range Count Query

ACできる解き方が全く思いつかなかった…

任意の区間で条件を満たす物の数を答えると考えれば尺取り法が使えそうな気がした。
あとはクエリを処理する系の問題なので、いくつかのクエリをまとめて処理するとか、最後から処理していくとかがよくある解き方だから使えそうか考えたけど、今回は使えなさそう。

次に制約を見てわかることとしては、
数列の長さは最大で2\times10^{5}でクエリの数も最大で2\times10^{5}なので各クエリでLからRまで線形探索をするとTLEになりそう。
なので各クエリでO(logN)くらいで解きたい。あるいは事前に何らかの処理をしておいて各クエリにはO(1)で答えたい。

なので1~iまでで何が何個出てきているのかを管理しつつ各クエリにはO(1)で答えるという方針で解いてみたけど、”1~iまでで何が何個出てきているのかを管理する”の部分が遅くてTLEだったりREだったりした。

AtCoder Beginner Contest 247

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

結果

A,B,C,D問題の4問正解でした。 E問題は問題文を読んで多分尺取り法だとは思ったけどうまく実装できなかった。尺取り法で解く問題の練習不足だった。

A - Move Right

問題文の通りに実装する。文字列の扱い方がわかっているかどうかに関する問題かな。

解き方はいろいろあると思うけど要するに、与えられた文字列の左端に"0"を付け足して、先頭から4文字を表示させればいい。1文字目の0は確定なので直接表示させても良さそう。

B - Unique Nicknames

問題文を理解するのに時間がかかった... 要するにほかの人の姓名を被らないように姓か名を選べるかどうかを判定すればいい。

制約を見るとNが小さいので二重ループで確認していくので十分間に合う。

C - 1 2 1 3 1 2 1

Nが小さいので事前にS _ {i}を計算して入力されたNに対応するS _ {n}を表示させればいい。 S _ {i}は S _ {i-1}がわかっていればすぐに作れるのでS _ {1}から順番に作っていけば特に苦労することもなく用意できる。

D - Cylinder

問題文を読むと、配列の後ろに要素を追加しつつ、先頭から要素を順番に取り出しせれば良さそうなのでキューが適してそうに思う。次に制約を確認すると1度に10 ^ {9}個を出し入れする可能性もあるのでc個の要素を出し入れする際に1個ずつ処理していたらTLEになりそうだと予想できる。
どうにかして要素の出し入れで処理の省略が必要そう。簡単に思いつくのは、どの要素が何個続くのかをペアにしてキューに入れる。その場合ペア1個分で必要以上に要素を取り出す場合があるので(ペア1個でc _ {i}個分を表現しているから)、取り出したペアを更新してキューの先頭に戻す必要が出てくる。
ここまで考えて、双方向キューを使いつつ要素には数xがc個連続していることを表すペアを使うことにして解いていった。
実際に実装してみると、キューを取り出したあとcを更新してキューに戻す部分が少しややこしくなったけど無事ACできた。

E - Max Min

問題文を読むと、数列から条件を満たす区間の数え上げ問題とみなせる。二重ループで解けば一応答えは出せるけど、制約を確認すると数列の要素数が最大で10 ^ {5}個になるので二重ループだとTLEになる。TLEにならないようにするにはO(N)くらいのアルゴリズムで解く必要がある。
O(N)で条件を満たす区間の数え上げだと尺取り法で解けそうだと考えた。

あとは実装するだけだったけど、区間の伸ばす条件がわからなくて実装できなかった…
尺取り法の問題の練習不足だった。尺取り法自体は理解していてコードも何回か前のABCで何度も書いたんだけどなあ。

AtCoder Beginner Contest 246

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

結果

A,Cの2問正解でした。
B問題は解説を読めばただの数学だったけど大学卒業して久しくこういった数学らしい数学の問題に触れていなかったので解き方が思いつかなかった…2分探索の力技で解いてみたけどwaが取れなかった…

A - Four Points

長方形のうち3点が与えられるので4点目の座標を答える問題。
4点目は与えられた3点のうちx座標とy座標それぞれ1回しか出てきていない値の組み合わせになるので、どうにかして仲間はずれの座標をxとyに関してそれぞれ探してあげればいい。言い換えればx1,x2,x3とy1,y2,y3それぞれで値が同じ になる組み合わせを探して、余り物を答えとして採用する。

B - Get Closer

傾きA/Bの原点を通る直線上で原点からの距離が1となる座標を答える問題。と解釈して考えてみた。 x座標がわかればy座標はA/B*xになるのでx座標を求めれば良い→2分探索でx座標を求めて、y座標は算出しよう。と考えて2分探索で解こうとした。
結局何かが悪くてずっと3WAだった。コンテストが終わるまでずっと解決できなかった…

C++だと小数の精度には限界があって、その限界のせいで正解と微妙に誤差があるのかもしれないと考えて、割りと大きな桁数でも扱えるpythonで書き直してみたけど今度はランタイムエラーだった。

次にyの値を計算するときにA/B*xと割り算をしているのでそこで誤差が出来ている可能性を考えて、x ^ {2} + y ^ {2} = 1から割り算を使わないよう変形した式で評価するようにしてみたりもした。ダメだったけど。

後は、原点からの距離が1という点から答えの座標は中心が原点、半径が1の円周上の点と考えてx座標はcos\theta、y座標はsin\thetaになるからどうにかして\thetaがわかれば答えられそうと考えた。 結局\thetaを求める方法がわからなかったのでその方針で解くのは諦めた。よくよく考えたらtan\theta = A/Bだからtan ^ {-1} \frac{A}{B} = \thetaなのか…

C - Coupon

似たような問題が過去問にあった気がする。(定額割引じゃなくて、半額になるって問題が)
クーポン1枚を使えば商品の値段をX円割引ける(最小は0円)としてクーポンK枚で最小の支払い金額を答える問題。
愚直に解くなら、金額の高い商品から優先的にクーポンを使っていけば良い。しかしKの最大値が10 ^ {9}なので愚直に解くとTLEする。
じゃあどうすれば処理を省略できるかなと考えると、どの商品にクーポンを使ったとしてもX円引きなのでまとめて値引きすればかなり処理を省略できると考えた。 具体的には、0円にならない範囲で各商品にクーポンを何枚使えるのか(A _ {i}/X)とそれだけクーポンを使ったら残りはいくらになるのか(A _ {i} mod X)を計算する。A _ {i}/Xの合計がK枚以上ならクーポンを全部使っても0円になる商品はない(X円引きれずに無駄になるクーポンが無い)のでA _ {i}の合計からXKを引いた値が答えになる。
A _ {i}/Xの合計がK枚以下なら一部の商品は0円になる。A _ {i} mod Xが大きいものから順番に0円にすれば支払う金額は最小にできるのでA _ {i} mod Xの大きいものK-(A _ {i}/X)個を除いてA _ {i} mod Xの合計を計算すれば答えが求まる。

AtCoder Beginner Contest 245

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

結果

A,B,Cの3問正解でした。 今日は疲れていたのか頭の回転がすごく鈍かった。 コンテスト中に全然頭が回らないと自覚できるくらいには酷かった。

A - Good morning

2人分の起床時間をもとにどっちが早起きかを答える問題。
時を比較して同じだったら分を比較すれば良い。

ちょっと変わった解き方としては、分割して与えられる時と分を先頭0埋めの2桁の文字列にした上で結合すると文字列的に時分になるのでそこから大小を比較してより小さい方を答えれば良い。
解けはするけど愚直に時と分をそれぞれ比較したほうが楽そう。

B - Mex

Aに含まれない最小の整数を答える問題。
Aは0~2000とそれほど大きくないのでサイズが2001のboolの配列を用意してAに含まれるインデックスのものはtrueにする等で区別できるようにしつつ0から順番にAに含まれない整数を探していけばいい。

C - Choose Elements

結論から言うとDPで解く問題。
深さ優先探索とかでも解けはするけど数列の要素数が大きすぎるのでTLEになる。

改めて考えると素直にDPで解けばよかったのに、深さ優先で解けそうと思って深さ優先探索を書こうとしてみたり、 深さ優先なら再帰を使って書こうかな、それともスタック使って書こうかなと考えたりとそこそこ迷走してた。 いざ深さ優先探索でコードを書くにしても普段なら特に悩まずスラスラ書けるのに、今日はどう書こうかなとちょっと悩んでいてかなり頭の回転が鈍いなあと自覚した。

最終的にはDPで書いて問題なくACした。