パナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231)

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

結果

A,B,C,D問題の4問正解でパフォーマンスが1076でした。 D問題がいつもより簡単だった気がする。

A - Water Pressure

入力を100で割ったものを出力する。言語によっては割る数が整数だと計算結果から小数点以下が切り捨てられる場合があるので注意する。

B - Election

候補者名毎に投票数をカウントして、投票数が最大の候補者名を出力する。
最初はmapを使って候補者名をキーに投票数を数えて、投票数最大の候補者の名前を出力していたけど、なぜかWAになった...
ぱっと見バグってなさそうに見えてWAに原因がわからなかったので解き方を変えてACした。後でテストケースが公開されたら確認しておこう。

C - Counting 2

入力されたx以上のAが何個あるかを答える問題。制約を見ると、Nの大きさ的には二重ループはTLEしそう。
ソートしたAからx以上となる境目を探せれば良いので二分探索が使える。 二分探索を使っても二重ループよりは計算量が軽いのでTLEにはならずに済む。

D - Neighbors

問題文を読んでまずは、隣り合える上限は2人までというのが思いつく。
なので人Xの隣に並べないといけない人が何人いるかを数えて3人以上なら条件を満たせないとわかる。
あとはループがある時は横一列に並べられないので、人をノード、隣り合うときは辺でつながっているとみなして、そのグラフにループがないかを確認すれば条件を満たせるかどうかを判断できる。

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

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

結果

A,B,C問題の3問正解でパフォーマンスが855でした。
D問題があと10分くらいあればACできた...コンテスト後にデバッグして提出したらACだったのが悲しい...

A - On and Off

日付を跨る場合がちょっと面倒。 図でも書いて場合分けすればわかりやすいけど、毎日電気をつけて消してをしているのを見落として1WAだった。 日付を跨っているかどうかに注意して問題文の通りに実装すれば良い。

B - Takahashi's Secret

が秘密を知っているかどうかを確認して、知っていなければ次はが知っているかどうかを確認して・・・をひたすら繰り返す。秘密を知っていれば処理を打ち切る。 人数は程度で二重ループじゃなければ時間に間に合うので、処理を打ち切ったあとN人の内何人が秘密を知っているのかを数えて出力する。

C - Final Day

4日目の得点が自分だけ満点。他の全員は0点だとした場合に自分が何位になるのかを数えて、K位以内かどうかを判断すれば良い。
入力を受け取りつつ各生徒の3日目終了時点の合計得点を計算する。それと別に合計得点のリストを作ってソートしておく。生徒の合計点＋300点したときの値がリストのどの位置に入ることになるのかを探して何位になるのかを計算する。 リストのどの位置に入るのかを線形探索するとN人リストの長さでになってTLEになるのでこの部分を高速化する必要がある。ソート済みの配列で閾値を探すことになるので二分探索が使えるので、二分探索を使って高速化する。

D - Linear Probing

問題文がややこしくて内容を理解するのに結構時間がかかった。
要するに番目の要素から順番にが-1になる要素を探して、その要素をxに置き換える問題。※mod Nを取っているので0～を循環するのが注意する点。
h MOD Nをもとに高速に=-1となるiが求めたい。
はじめはsetを使って、処理した要素番号の集合から次はどこを処理すれば良いのか求めようとしたけど、上手くできそうになかったので考え直してUnionFindが使えそうだったので実装した。
提出してみるとWAが1ケースあってコーナーケースで躓いていそうだったので見直してたけどACできなかった。
コンテスト後にコードを見直して提出してみたらACしたのでちょっともったいない。

キーエンスプログラミングコンテスト2021-Nov. (AtCoder Beginner Contest 227)

キーエンスプログラミングコンテスト2021-Nov. (AtCoder Beginner Contest 227)に参加しました。

結果

A,B,C問題の3問正解でパフォーマンスが784でした。
全体的に難しかった気がする。

A - Last Card

簡単に言うと１～Nが循環する中でA+Kをすれば良い問題。剰余計算を使えば楽。もしくはAにループでK回+1しつつNを越えたら1に戻す。

B - KEYENCE building

の最大値が1000で計算式には4abの項があるのでa,bの探索範囲は１～250くらいで良さそう。これくらいならa,bの全組み合わせを計算しても時間は十分間に合う。
なのでまずはa,b全通りを計算して算出可能な面積を全通り求めて、算出不可能なの値が何個あるのかを数える。

C - ABC conjecture

制約的を見るととあるのでA,B,Cの3重ループで全通りの計算は時間がかかりすぎる。
こんなときはA,Bの2重ループにしつつ、Cは計算して値を求めるのがよくあるやり方なので2重ループで処理をする。
かつなのでAの探索範囲は1～Nの立方根までで良くて（それ以上はABCがNを超える）、Bの探索範囲はA～で良い（がN以下になるように）。 この範囲でA、Bを全探索しつつ、B~までCが答えとしてありえるので数えていく。

D - Project Planning

解けなかった…
作れるプロジェクト数の最大値を二分探索で探せば良さそうなのは思いついた。ただX個のプロジェクトを作れるかどうかを判断する方法がわからなかった。

UNICORNプログラミングコンテスト2021(AtCoder Beginner Contest 225)

UNICORNプログラミングコンテスト2021(AtCoder Beginner Contest 225)に参加しました。

結果

A,B,D問題の3問正解でパフォーマンスが833でした。
C問題がACできなかったのが悔しい。思いついたコーナーケースは潰したけどWAが1つだけ残ってわからなかった…

A - Distinct Strings

何種類の文字があるかで作れる文字のパターン数が決まるので、setに1文字づつ入れてそのサイズを取得すれば良い。 もしくはnext_permutationで全通り文字列を作ってそれが何通りなのかを数える。

B - Star or Not

木がスターかどうかを確かめる問題。
各頂点の次数を数えて、1つだけ次数がN-1、他はすべて次数が1となっていればスター。そうじゃなかったらスターじゃない。

D - Play Train

問題を読んでいるとUnionFindTreeを使えば楽そうと思いつつ、出力するデータは連結の前から後ろまで順番にってあるのでUnionFindTreeよりは双方子に参照できる連結リストのほうが良さそうって思った。各電車の前後には1台ずつしか電車はつながらないので各電車の前と後ろだけを管理して処理をした。
出力時の処理は制約的に1重ループでも間に合いそうなので愚直に実装して処理した。

AtCoder Beginner Contest224

AtCoder Beginner Contest224に参加しました。

結果

A,B,C問題の3問正解でパフォーマンスが732でした。 C問題が思いの外時間がかかった。最初に選んだ方針が悪かったみたい。
D、E問題はさっぱりわからず、F問題はTLEになるだろうかなと思いつつ解いてみたけどACはできなかった…

A - Tires

文字列の最後かerかistかを見て文字列を出力する。
最後から2文字と3文字の部分文字列を取得して、それがer,istと一致するかどうかを判断する。

B - Mongeness

H,Wは制約的に全探索できる程度の大きさなので全探索する。 全探索のループをちゃんと書ければ解ける問題。

C - Triangle?

N個の点から３つ選ぶ場合の計算量はなのを踏まえて制約を見るとなのでNが最大の場合でもTLEにはならなさそう。 点を3つ選ぶのは問題なくできそうで、次は点3つが三角形になるかどうかをどう判断するのかを考える。
最初は3点から3辺の長さを計算して、三角不等式が成り立つかどうかで判断しようとしてたけどサンプルの解とちょっと違った。他に判断方法がないかなと調べてたらベクトルの外積で面積を求めて判断する方法があったのでその方法で解いてみた。こっちの場合は上手くいきそうだったので提出したら無事ACできた。
最初のほうだと平方根の計算が必要でそのときに小数点以下の部分で誤差が出てたのかなあ。

エクサウィザーズプログラミングコンテスト2021（AtCoder Beginner Contest 222）

エクサウィザーズプログラミングコンテスト2021に参加しました。

結果

A,B,C,Dの4問正解でパフォーマンスが987でした。 最近D問題が解けてて、パフォーマンスが緑～水色あたりだからレーティングが少しずつ上っていって嬉しい。

A - Four Digits

問題文のとおりに出力する。
解説を見てからだと自分の回答はめんどくさい解き方してるなと思う解き方をしてた。 数字を文字列として受け取りリバースする。その後0000を後ろに追加して、先頭から4文字の部分文字列を取得する。最後に取得した部分文字列を再度リバースして出力する。

出力時に先頭0埋めでいいなら%04dだけでよかった。 先頭0埋めの文字列をその後加工するなら今回提出した処理の方が良いんだけど、出力するだけだからなあ…

B - Failing Grade

問題文の通りに出力する。
P点未満の点数がいくつあるかを数えて出力するだけ。

C - Swiss-System Tournament

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

誰が何回勝ったかを数えておく。ソート関数で使う用に、数えている記録を元に2人の順位の上下をboolで返す関数を作成した。 こうすると各ラウンドで全員がじゃんけんした後に、自作した順位判断基準の関数を利用して１～2Nをソートすると順位通りに並ぶようになる。 Mラウンド分　じゃんけん→ソート　を繰り返した後に１～２Nのソート結果を先頭から順に出力すればOK。

D - Between Two Arrays

DPを使って解く問題だった。
DP[i][j]を　をjとする場合に作成可能な数列の個数　とすると、 の時は DP[i][j] = DP[i-1][j] 　要するにD[i-1][0]からD[i-1][j]までの累積和になる。じゃない時はDP[i][j]=0になる。 後はこれをi=1から順番に計算していけば良い。
ただ、毎回累積和を計算するのは制約的にTELになりそうなのでO(1)くらいで求められるようにしておく。 私はDPを計算する際に合わせて累積和も計算していた。j=0から順番にDPを処理しているからj-1までの累積和にDP[i][j]を足すだけでjの時の累積和が計算できる。これをj=3000までやるとj=0~3000すべての累積和が計算できている。

AtCoder Beginner Contest221

AtCoder Beginner Contest221に参加しました。

結果

A,B,C,D問題の4問正解でパフォーマンスが1308でした。 D問題が割と早く解けたおかげでパフォーマンスが良かった！ E問題はあと少し時間があればAC解けそうな気がした。後でできなかった部分を実装して提出しておこう。

A - Seismic magnitude scales

問題文のとおりに計算する。 AとBの差をxとするとを計算するだけ。

B - typo

色々やり方はありそうな問題。

SとTを先頭からチェックしていき一致していない場所が何箇所あるかを数えて、 0のときYes。1のときNo。3以上のときNo。として処理終了。 2のときは、最初に一致していない場所をxとしたときS[i]とT[i+1],S[i+1]とT[i]が一致することを確認する。 一致するならYes,一致しないならNoを出力させる。

C - Select Mul

制約を見るとNは以下なので9桁程度の整数。つまり最大で9つの整数を2つに分けて数字を作って積の最大値を求めれば良い。
bit全探索とかでNの数字を2つに分けて、各グループの中でソートとかグループ内の数字だけで作れる最大の整数を作る。その後、作った2つの数の積を計算して最大値を更新していく。

D - Online games

ログインユーザーの累積和を計算して、各kに対してログイン人数がk人の日が何日あるかを数えて出力する。

最初は累積和をimos法で計算しようとしたけど、A,Bの最大値がなのでimos法で各日にちに対して線形に処理しているとTLEする気がしたので解き方を考え直した。

プレイヤー数Nに対してA、Bが十分大きいのでもしもの配列で累積和を計算したとしてもほとんど値の変化がなくて無駄が多そう。なので日に人が増えた、に人が減ったというイベントドリブンでシミュレートすることにした。何人の状態が何日間続いたかをイベントの度に計算して記録していき、最後に各k毎に出力する。

E - LEQ

もう少し時間があれば解けそうな問題だった。
に何番目のAを持ってくるのかを決めればA'に含められるAの候補が何個あるのか決められる。Aの候補がx個あったとすると通りのA'が作れることになるので、がの場合からの場合まで順番に計算すれば解けそう。がの時A'に含められるAが何個あるのかを事前に計算しておくとかして簡単に取得できるようにすれば、たぶんTLEせずに解けると思う。