0.はじめに
まだまだ仕事に慣れない今日この頃。
今回はAで躓き時間を食い
その上Cまでしか解けず終了。
レートは+13の784と後退しました・・・。
1. A - 16:9
２つの数字の比が16：9かを判定する問題
Xを16でYを9で割った値が一致するかを判定。
と、しましたが、割り算を切り捨てにしてしまったため
WAに。
XとYが0のケースがまちがっているのか！？とおもって
修正してもWA（問題の制約上0はありえない）
割合の問題なので、逆にXに9、Yに16を掛けて比較して
やっとACとなりました。
最初の割る判定の際切り捨てにしなければACだったと気づいたのは
翌日になってからでした・・・。
https://atcoder.jp/contests/abc463/submissions/76821168
2.B - Train Reservation
空席情報のSを読み込み、列毎の空席数をカウント。
最後にX列の空席数が残っていればYes、残ってなければNoを出力して
終了として、ACでした。
https://atcoder.jp/contests/abc463/submissions/76813975
3.C - Tallest at the Moment
タイミング毎に残っている人で最高身長の人を答える問題。
【考え方】
最高身長の人から見ていき、最高身長の人が去る時間までは
最高身長の人が最高身長、それ以降
2番目身長の人が去る時間が、最高身長の人が去った以降の時間であれば
その時間までは2番目身長が参考身長
上記時刻ごとの最高身長を保持し、クエリーごとに2分探索で検索すれば
TLEにならずに時刻ごとの最高身長を求められる。
【実装】
1.Nを読み込む
2.身長、去る時間のタプルを格納するリストPを空で定義
3.以下N回繰り返し
-1.H,Lを読み込む
-2.タプル(L,H)をLに追加
4.Pを降順にソートする
5.リストHL（身長の高い順の人リスト)を空で定義
6.リストLL(身長の高い順の人リストに対応する去る時間リスト)を空で定義
7.変数pre(前の人が去った時間)を0で準備
8.以下Ｐを先頭から1つずつh,lに取り出して処理
-1.lがpreより大きい時
-1.HLにｌ-1を追加(基準とする時刻は+1/2するため)
-2.ＬＬにｈを追加
-3.preにlをセット
→時刻 l+1/2 時点で一番大きい人の身長のリストが、 l の昇順で作成される
9.QとリストTを読み込む
10.以下iを0～Q-1まで増加させながら繰り返し
-1.pos_lにHLからT[i]をbisect_leftで探してセット
-2.LL[pos_l]を出力
上記プログラムでACとなりました。
https://atcoder.jp/contests/abc463/submissions/76831932
4.D - Maximize the Gap
問題を読みdpで最適な配置を考えるか・・・と思いましたが
あまり軸になる項目が思い浮かばずそちらはないと切り捨て。
よくある2分探索で最適値をさがすタイプと
思い定め解いていきました。
2分探索の肝である、布の間がXでK枚選択出来るかの判定を
無駄に短くしようと2分探索で組んでしまい、WAとなってしまいました。
方向性を修正する間もなく時間切れとなり終了。
コンテスト後解説を見て、判定は端から見る貪欲方でも十分間に合うと知り
修正して提出するとACとなりました。
問題の規模も考え、アルゴリズムを適切に選択していく必要があることが分かりました。
https://atcoder.jp/contests/abc463/submissions/76860852
以上