0.はじめに
レギュラーコンテストは自分にしては調子よかったので
ABCもレートアップを目指して参戦。
なんとかDまでクリアしてレートアップをどきどきして待っていたら
なにやらレート計算に時間がかかるらしく、ドキドキしながら
しばらく待つこととなりました。
水曜日にやっとレートが更新され、+24の803と、緑に復帰できました。
1.A - A Healthy Breakfast
簡単なようで意外とすっと解けない問題でした。
時間かけるのも何なので、素直に、1文字目から見ていって、
Rがきたら、フラグを立てる
Mが来たときに、フラグが立ってればYesたってなければNoを
出力して終了でACでした。
https://atcoder.jp/contests/abc360/submissions/55048492
2.B - Vertical Reading
どう考えてもCより難しいよなーと思える問題。
問題文も理解しづらく、レート算出が遅れる原因ともなったとのこと・・・。
やっと読み解いた内容としては
文字列Sをw文字ごとに改行して作った文字の固まりを
縦列毎に見ていったときに、Tと一致するケースがあるか？
という問題でした。
今、改めて文にすると、すんなり問題文が理解できたなと思いつつ
コンテスト時の実装は以下のようにしました。
【実装】
1.S,Tをインプット
2.数値LSにSの長さを格納
3.～以下iを1からLS-1まで繰り返しで
Sをi文字で改行した場合のチェックをしていく
-1.リストL(i行で改行した1行毎を格納)を空で定義
-2.文字列l(i行で改行するまでの1行を格納)を空で定義
-3.数値ln(lに何文字入っているか)を0で定義
-4.以下jを0からLS-1まで繰り返してLにi行ごとに
改行した文字列を格納
-1.lにS[j]を追加
-2.lnに1を加算
-3.lnがiと同じな場合
-1.Lにtuple(l,ln)を追加
-2.lを空で初期化
-3.lnを0で初期化
(ループを抜けた時lに文字が残っていた場合の処置)
-5.lnが0以上の時
-1. Lにtuple(l,ln)を追加
-6.以下jを0からi-1まで繰り返してL内の文字列の先頭j文字目の文字列を求める
-1.文字列ansを空で初期化
-2.リストLから１ずつ値を取り出してlに格納し、繰り返し
-1.lnがjより大きかったら(問題文の”長さが c 以上の文字列の”を満たすための条件)
-2.ansにl[j]を追加
-3.ansとTが一致したら"Yes"を出力して終了
4.3を最後まで処理してTと一致する文字列が無かったら、"No"を出力して終了
制約がもっと厳しかったら、改行する文字数をTと同じ長さになる場合の長さのみにする等が必要があったかもですが
上記実装でACが頂けました。
https://atcoder.jp/contests/abc360/submissions/55064009
3.C - Move It
問題を読み解くと、複数の荷物が入った箱から、軽いもの順に
残りの荷物が1個になるまで荷物を取り出し、その取り出した
荷物の重さの合計が答えとなる。ということが分かりました。
以下実装
【実装】
1.N,A,Wを読み込む
2.リストL(AとWの組み合わせをタプルで保持)を空で作成
3.iを0～N-1まで回し、リストLに(A[i],W[i])を格納
4.Lを昇順ソート→箱番号/軽い順に並ぶ
5.回答用変数ansを0で、前状態タプルpreを(0,0)で定義
6.iを0～N-1まで回す
-1.pre[0]がL[i][0]と同じだったらansにpre[1]を加算
(L内で同じ箱が連続したら、前の方の荷物を取り出す=ansに重さを加算)
-2.preにL[i]をセット
7.ansを出力して終了
Bに比べて簡単に感じました。
https://atcoder.jp/contests/abc360/submissions/55069295
4.D - Ghost Ants
ぱっと見座標問題か・・・とあきらめて他の問題を見に行きましたが
E以降の方がさらに難しそうだったので取り組みました。
よく読めば、単純な直線状の1次元問題だったので安心して考察。
ダメもとでTLE覚悟の実装
【考え方１】
・蟻を右向き(R)と左向き(L)毎に分け、位置を格納したリストを作成。
・右向きの蟻(位置はR[i])毎に以下のチェック
・L[i]の値がR[i]以上R[i]+T×2(左右の蟻がT移動したらすれ違う位置)以下の場合変数ansに1加算
・最後にansを出力して終了
5分無駄にすると思いつつもワンチャンいけるかなと、試しましたがやっぱり26/28TLE
素直に2分探索方式に変えました。
【考え方２】
・蟻を右向き(R)と左向き(L)毎に分け、位置を格納したリストを作成。
・リストLを昇順ソート
・右向きの蟻(位置はR[i])毎に以下のチェック
・bisect_leftでリストLのR[i]の位置を取得して変数laに格納
・bisect_rightでリストLのR[i]+T×2の位置を取得して変数raに格納
・ansにra-laを加算
・最後にansを出力して終了
これでTLEなら、右左少ない方でループを回すとかかなと思いつつも無事ACとなりました。
https://atcoder.jp/contests/abc360/submissions/55085656
以上