0.はじめに
暑さが一瞬だけ和らいだ今日この頃臨んだコンテスト
A、Bは普通に解けましたが、Cが異様にむずかしい・・・。
結局TLE１つが解消できずに時間切れ。
レートは-24の767とまた緑がとおのきつつ
くしくも回文数だなと思いました。
それはそうと、またコンテストのテストページや提出後の挙動が
重くなっているような気がしていますが、また攻撃を受けているのか
私の環境がわるいだけか・・・。
1. A - Streamer Takahashi
Aにしては難しめの問題。
とはいえ、RやYが火をまたぐケースはないので
単純にLRとXYをそれぞれ比較し
条件に合っていればカウントして最後に出力で
ACとなりました。
https://atcoder.jp/contests/abc414/submissions/67511786
2.B - String Too Long
B問題の割にMTEとかを気にしないといけない問題。
まず単純にCとLから文字列を一旦作って
長さを判定して出力と作りましたが
例題２でMTE。
そこで、レコード長は別に管理し、レコード長が超えたら
即終了で超えなかったら回答用文字列を作る形にして
ACとなりました。
https://atcoder.jp/contests/abc414/submissions/67521362
3.C - Palindromic in Both Bases
てこずりすぎて結局時間切れになった問題。
処理時間を減らすための試行錯誤を色々試しましたが
あと一歩及びませんでした。
【基本機能】
１）10進法の回文数作成
２）回文数をA進数に変換
３）回文数判定
【考え方１】
構成：１）で作成した回文数リストを２）でA進数に
変換し、３）で回文数かを判定しカウントして出力
手法：
１）単純に１～Nの数字をそれぞれ３）の方法で判定しリスト化
２）再帰関数を使った変換
３）数字を文字列に変換し、その文字列と逆にした文字列を比較し一致したら回文数と判定
→１）の段階で時間がかかりすぎて例題すらTLEに。
【考え方２】以下変更点
手法：
１）X以下の回文数リストを作成する関数を作りリスト化
３）ロジックを使い、数字を2つに分けて高速に判定
例）X＝123456の時
1.分割用変数Rを0で定義
2.以下XがRより大きい間繰り返し
-1.RにR×10＋Xmod10をセット
-2.Xを10で割る（切り捨て）
→例の場合
ループ１．X：12345 R:6
ループ２．X：1234 R:65
ループ３．X：123 R:654
3.XとRが一致またはXとR//10(桁数が奇数の時のためのロジック)が一致の場合回文数と判断
→大幅に速度が改善され、TLEが２つに
【考え方３】以下変更点
手法：
２）を再帰関数ではなくループする形に変更
→TLEが１つに
ここであえなく時間切れ。
解説を読んでも方向性的には間違っていなかったので
他の方の回答を見て、構成の部分で、10進数の回文数をリスト化せずに
その数をそのままA進数に変換し判定してカウントしてACとなっている方がいたので
たしかに、リスト化は無駄だなとそちらを参考にしてみたところ
ACとなりました。
リスト化せずに判断するのは少し頭に浮かびかけた改善点だったので
そこら辺をさっと試せるようにスキルアップが必要と感じました。
https://atcoder.jp/contests/abc414/submissions/67562130
4.D - Transmission Mission
Cでいきづまりちらっとみて、行けそうな気もするけど
Cが解ける確率よりDが解ける確率は低そうだなとスルー。
コンテスト後解説を見てロジックは簡単でしたが
そこに至る考察は私には難しかったろうな・・・と思いました。
以下、解説をぱっと読んだだけではすぐに理解できなかったので
私なりの理解まとめ
【考え方】
・立ててよい基地局が1個の場合、左端の家と右端の家の中間地点に
右端の家の位置-左端の家の位置の強度の基地局を立てれば
最小電波強度となる
・立ててよい基地局がＮ個(家の数と同じ)の場合、各家の位置に
電波強度0基地局をＮ個たてれば最小電波強度(0)となる
・立ててよい基地局が２個の場合、家を2つのグループに分ければよい
その場合電波強度を最小にするためには家の間の距離が
最長の家の間で分ければよい。同様に立ててよい基地局が３個以上の
場合も、家の間が離れている所からをグループ分けの基準とすれば
最小電波強度となる
・上記考えをもとに、グループ分けの基準：各家間の総間隔から使用しない間隔数を
引けば求める答えとなる（各家間の間隔はＮ－１個）
・使用しない間隔数は
-Ｍが1個の時は0個の間隔（すべて使う）
-Ｍが2個の時は1個の間隔
・
・
・
-ＭがＮの時はＮ－１個の間隔（すべて使わない）
となるため、使用しない間隔数は、Ｍ－１個
・なので使用する間隔数はＮ－１－（Ｍ－１）個
→Ｎ－Ｍ個となる
こんな感じで1個1個身に着けていければよいですが最近は一個覚えると
2個位忘れるような気がしています・・・。
https://atcoder.jp/contests/abc414/submissions/67563414
以上