0.はじめに
茶色へランクダウンが見えてきた今日この頃参加。
A~Cは順調にいくも、Dでブレーキ。
自分的には行けると思いましたが、ちょっとだめで
TLE18個で終わりでした。
レートも-14の810と、いよいよ崖っぷちです。
1.A - Who Ate the Cake?
原理は単純だけど、実装はなかなか考える問題。
【考え方】
・容疑者フラグを3つ用意し1をセット
・A・Bの証言で、犯人でないと分かった人の
容疑者フラグを0に変更
・容疑者フラグの合計が2なら犯人は絞れず-1を出力
・容疑者フラグの合計が1ならフラグが立っている人を出力
上記考えで実装し、ACでした。
https://atcoder.jp/contests/abc355/submissions/53831705
2.B - Piano 2
ちょっと前にでたpiano問題とは若干違った感じの問題。
【考え方】
・リストAとリストBをリストCに登録。
その際、リストAは(値,0)のタプル、リストBは(値,1)のタプルで登録
・リストCを昇順ソート
・リストCをインデックスiで先頭から見ていき、
C[i][1]が0のレコードが続いたらYesを出力して終了
・最後まで見ても0のレコードが続かなかったらNoを出力して終了
上記でACとなりました。
https://atcoder.jp/contests/abc355/submissions/53839877
3.C - Bingo 2
素直にマス目を作ってチェックしていくだけだと
TLEになるんだろうなという問題。
行列斜め毎にマスを塗った数を集計し
塗ったタイミングで塗った数がNになったら終了とすれば
TLE回避できるかなと実装しました。
【実装】
・行ごとにN個、番号が呼ばれた数を集計するリストXを作成
・列ごとにN個、番号が呼ばれた数を集計するリストYを作成
・斜め用に2個、番号が呼ばれた数を集計するリストZを作成
・リストAを先頭から見ていき以下の判断
-行チェック
・A[i]をNで割った値をxに格納
→A[i]がNで割り切れる場合は、xから1マイナス
・X[x]に1加算
→加算後X[x]がNになったらi+1を出力して終了
-列チェック
・A[i]をNで割った余り-1をyに格納
→A[i]がNで割り切れる場合は、yにN-1をセット
・Y[y]に1加算
→加算後Y[y]がNになったらi+1を出力して終了
-ななめチェック(左上から右下)
・xとyが同じ場合
→Z[0]に1加算
→Z[0]がNになったらi+1を出力して終了
-ななめチェック(右上から左下)
・xとN-y-1が同じ場合
→Z[1]に1加算
→Z[1]がNになったらi+1を出力して終了
・リストAを最後までみてもビンゴがそろわなかったら-1を出力して終了
最初適当に組んでみましたが意外とすーっとACとなりました。
https://atcoder.jp/contests/abc355/submissions/53863100
以上