【16日目】良問100選の続き

今日は6~9を。昨日の分よりはやや難易度が上がったが、この程度ならまだまだいける。

ただもう少し早くできたら理想かな、という気もする。結構添字とかで「あれここはa[i]だっけ？a[i+1]だっけ？」とかなってタイムロスをしている感。あとはループの範囲とかでも同様。対策としては、以前書いた「半開区間を基本とする」というのもそうだし、あとはやはり慣れなのか。

以下一問ごとの感想。

6　三井住友信託銀行プログラミングコンテスト 2019 D - Lucky PIN

「Sからどの3つを選ぶか」から「000~999の各値について、Sから作れるか」という視点に切り替えることがポイント。この手の切り替え結構苦手なんだよな…。このくらいだとできるけど。

7　JOI 2007 本選 3 - 最古の遺跡

正方形は、隣接する2頂点さえ選べば2つにまで絞れるということがポイント。数学的な考察なので割とできた。あとこの問題を解くに当たって特定の座標の点が存在するかを高速に検索する必要があったので、operator<, ==を使える座標保持クラスPtを用意した。これ結構汎用的に使えそうなので取っておく。早速9でも使った。

8　Square869120Contest #6 B - AtCoder Markets

これ面白かったな。コード書く前の考察が大事になってくる系の問題は割と好き。これの場合、ルートなどというものはいちいち考えなくとも、入口とマスAの距離、出口とマスBの距離さえ考えれば良いということ、さらに、移動時間の合計は一次関数の絶対値の和で表されるということがポイント。つまり絶対値記号の中身の符号が変わるポイント(入口、出口がA,Bと重なるポイント)のみ考えれば良いわけだ。面白い。

9　JOI 2008 予選 4 - 星座探し

7番とよく似ている。というか7できればこれはできる。特筆事項なし。

明日はbit全探索から。