2022-06-18

東京海上日動プログラミングコンテスト2022（AtCoder Beginner Contest 256）

競技プログラミング

東京海上日動プログラミングコンテスト2022（AtCoder Beginner Contest 256）に参加しました。

結果

A,B,C,D問題の4問ACでした。
普段に比べてD問題が簡単な気がした。その代わりE問題が難しかった。

A - 2^N

$2 ^ {N}$ を出力するだけの問題。

言語に用意されている指数計算する関数を使うか、N回ループして計算すれば良さそう。

解説を見るとビットシフトで2乗の計算していて賢いなあと思った。 2の乗算ならたしかにシフト演算で計算できる。

B - Batters

野球の点数計算をする問題。
全員が同じ数だけ塁を進めるって言う設定で、進める塁の数が与えられるから最終的に何点取れたかを計算する問題。

制約はそれほど厳しいものではないので素直にシミュレートして答えれば十分間に合う速度で解ける。

C - Filling 3x3 array

$3 \times 3$ のマス目に自然数を書き込んだ時に、各行・各列の和が指定された値にする場合のパターン数を答える問題。

ある行にだけ注目すると3重ループでその行のパターンを全通り確認できる。ただこうするとO( $N ^ {3}$ )になるので3行分処理すると最終的にはO( $N ^ {9}$ )になる。指定される和の上限は30なので各マスに1~30のどれかを書き込むとすると最大で $30 ^ {9}$ だけ処理が発生する。これ全部を処理すると時間がかかりすぎてTLEになるので、愚直に全通りを確認するのは筋が悪い。

ある行の和を $h _ {i}$ にしたいので2つ値が決まれば、残りの1つは1通り決まる。
なので3重ループのところを2重ループに節約すれば最終的にはO( $N ^ {4}$ )になる。これだと処理量の最大は $30 ^ {4}$ なのでなんとか間に合いそう。
解説だとこの解き方だった。

私は3重ループを2重ループに節約するテクニックを使いつつ、
各行毎に条件を満たす値の組み合わせを探して解いた。
組み合わせを探した後は、3重ループでさっき探した組み合わせを全通り試す。この処理は3重ループになるけど、合計の処理量は $N ^ 3$ よりは十分小さいはず。（3つの値の和がある値になる組み合わせは $30 ^ {3}$ 通りのうちの一部だけなので） 3重ループで全通り試しつつ、行・列ともに条件を満たす組み合わせの数を数えて出力させた。

D - Union of Interval

半開区間の和集合を計算して答える問題。

各値は何個の区間に含まれているのかを計算して、1個以上の区間に含まれている範囲の最初と最後を順番に出力させた。具体的にはimos法を使って1~ $R _ {i}$ の最大までの範囲で各値が何個の区間に含まれているのかを計算し、その後に尺取法を使って、半開区間に含まれている数が１以上となっている範囲を探して、見つかった区間の最初と最後を出力させた。

2022-06-12

エイシングプログラミングコンテスト2022（AtCoder Beginner Contest 255）

競技プログラミング

エイシングプログラミングコンテスト2022（AtCoder Beginner Contest 255）に参加しました。

結果

A,B,Cの3問正解でした。最近D問題からがうまく解けないことが多くてレーティングがちょっとずつ溶けていっている…

B問題の考察が甘くて1WAしたのが痛かった。 C問題は考察自体は正しいと思いつつ何故かWAになったので愚直に解くようにして無理やりACした。解説読んだけどやっぱり考察自体はあっていた。どこかでバグがあったのかなあ。
D問題はちょっと考えが足りなかった…

A - You should output ARC, though this is ABC.

2 $\times$ 2の配列を用意して、指定された要素の値を出力する問題。
配列の扱い方を知っているかどうかな問題だと思う。

配列の参照が0からなのか1からなのかで指定された要素番号を1ずらす処理が必要。
もしくは配列の参照が0始まりの言語の場合は3 $\times$ 3の配列を用意して1-1から2-2までの要素だけを使えば、指定された要素番号をそのまま答えれば良くなる。

B - Light It Up

問題文を読むとはじめは難しそうと思ったけど、結局、明かりを持っていない人と1番近い明かりを持っている人との距離の最大値を求めるという割りと簡単そうな問題だった。

明かりに照らされるためには、少なくとも明かりを持っていない人と明かりを持っている人との距離以上の明かりの強さが必要。最小値を求めるので明るさは距離と同じであればいい。
NやKは高々1000程度なので2重ループでも十分高速に解ける。

明かりを持っていない人毎に明かりを持っている人との距離の最小値を求める。 N-K人分の求めた距離の内、最大値を計算して答えれば良い。要するに計算した最小値の中から最大値を答えれば良い。

C - ±1 Operation 1

XとXに一番近い等比数列の項との距離を答える問題。

Xが数列の1番小さい数値より小さい（1番大きい数値より大きい）場合は、1番小さい値との距離（1番大きい値との距離）を計算して答えればいい。
Xが数列の最大値と最小値の間にある時がちょっと難しい。

公差がDということは数列の値はAだけずらすとDの倍数になる（等比数列の後の値はA＋Dx）。
なので、XをAだけずらしてD割った余りを計算して、余りがDか0になるまで「操作」を行えば、行った回数が答えになる。

と言う考察をして実装したけど一部がWAになって困った。Dの範囲は $10 ^ {6}$ とO(N)でもなんとかTLEしなさそうなので、Xが数列の最大値と最小値の間にある時は愚直に確認してみることにした。それでなんとかACできたけど、C問題の割に時間がかかってWAもちょっと多かった。

D - ±1 Operation 2

数列の各項とXとの距離の合計を答える問題。
愚直に解こうとするとO(NQ)になって、数列の長さ(N)と質問の数(Q)が $2 \times 10 ^ {5}$ なのでTLEしそう。
質問の数的に各質問をO(1)とかO(logN)くらいで答えられないとTLEしそう。あと、数列Aの順番は重要じゃないのでソートしておいたほうが都合が良さそう。

愚直に計算するのはダメそうなので、Xの値によって答えの推移になにか規則性があるのかと思って規則性の考察ばかりしてた。XがAの最小値や最大値の外側だと規則性があるけど数列Aの最大値・最小値に挟まれる場合は不規則に変わっていくので規則性を探して数式化してっていうのは結局無理そう。

解説をみたけど、結局は愚直に解きつつ式変形と累積和の事前計算で答える問題だったっぽい。
そもそも解く方針が間違ってたみたい。

2022-06-04

AtCoder Beginner Contest 254

競技プログラミング

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

結果

A,B,Cの3問正解でした。 C問題が難しかった。なので解けそうなD問題を先に解いてみたけど失敗だった。
結局D問題は解けずC問題に戻ってきて力技で解いてみたらACできた。でもC問題をACする時間が遅かったから順位が低くなた。

A - Last Two Digits

入力された数字の下2桁を出力する問題。
数値として受け取って100で割った余りを先頭0埋めの2桁表示させたり、文字列として受け取って下2桁を表示させたり解き方は色々ある。

入力される数値は3桁だけだから文字列として受け取って決め打ちで2,3文字目を表示させれば1番楽そう。

B - Practical Computing

数式がややこしいけど結局二項係数を出力すれば良い。

$_{n} C _ {r}$ を計算する関数を作っておけば後はループでn,rを全通り当てはめて計算すれば良い。
mod計算に関して勉強した時にライブラリを自作しておいたのでコピペしてループを書いて終わりだった。

C - K Swap

幅が固定されたコームソートで昇順にソート可能かどうかを判定する問題。

難しかった… K=1のときはバブルソートなので必ず昇順にソートできるのでK>1の時に関して考える。

時間制限を気にしないなら幅Kで入れ替えが起こらないまでコームソートをして、その結果が正しく昇順になっているかどうかを確認すればいいけど、 ”入れ替えが起こらないまで”がどれだけ時間がかかるかわからないけど最悪 $O(N ^ {2})$ になるので実際にはTLEになる。

説明するのがややこしい力技な解き方をしたらなんとかACできたから良かった。

D - Together Square

そもそも平方数って何ってなった。ググった結果 $x ^ {2}$ の数のことらしい。

計算時間を気にしないなら１～Nまでの $N ^ {2}$ を計算して、それぞれの約数を列挙してN以下の約数の組み合わせを数えていけば答えは求められる。
実際にやってみるとTLEになった。

手計算で1,4,9,16,・・・の約数を手計算して条件を満たす組み合わせを数えてみると、Nがある程度の以上になると条件を満たす組み合わせが1にしかならなくなるっぽいことがわかった。ある程度までは組み合わせを数え上げて、ある程度以上は1になるとしてまとめてカウントすればTLEにならないくらいの時間で答えが出せそう。結局ある程度のギリギリがわからないし、適当な値でやってみたらTLEやWAになったので解き方の方針がそもそも間違っていそう。

2022-05-22

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-05-14

パナソニックグループプログラミングコンテスト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から順番に更新していけば答えが求められそう。問題は行動１と行動Nで動物1に餌をやることが被るのでその部分がややこしいなと思った。

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

2022-04-23

モノグサプログラミングコンテスト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

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

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

好きな数の文字列を選択する
どの文字が何回出てくるか数える
出現回数がK回の文字が何個あるか数える
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の順番はそれほど大事じゃないのでソートしても問題ない。

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

$A _ {j}$ の倍数のうち $A _ {i}$ となるものがあるかどうかを確認する。
$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-04-17

ユニークビジョンプログラミングコンテスト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だったりした。