久々の投稿です。先週は Asprova のマラソンコンテストと RTAinJapan を見漁る生活をしていました。
昨日までの3日間は高校の友人に会いに福島県に行っていて、今日は久々に競プロの日にしたいと思っています。
AOJ1328 - Find the Outlier
$x$ についての $d $ 次式 $f(x)$ が存在し、$f(x)$ に $x = 0 , 1 , \ldots , d + 2$ を代入した結果が与えられる。しかし、その代入した結果の1つが間違っているので、その番号を特定する問題。
間違っている番号を固定する。残っている $d + 1$ 個の値でラグランジュ補間をし、その多項式から同様の値が得られるかどうかで正誤判定をすれば良い。
AOJ2297 - Rectangular Stamps
愚直に盤面の情報を持とうとすると、まだ塗ってない or RGBのうちいずれか、と4通りの情報が必要で厳しい。だが、探索には今の色が正しいかどうかだけの01の情報だけで十分で、これで状態数は $2 ^ {16}$ にまで減らされる。
後は初期状態からBFSをして答えを求めれば良い。塗られる長方形の候補は高々 $\tbinom{16}{2}$ 通りなので前計算しておくと余裕を持ってAC出来た。
AOJ2380 - Bubble Puzzle
計算量分からないけどBFS書けば良さそう→通りました。
AOJ2200 - Mr. Rito Post Office
dp[i][j] := i 番目まで到達済みで j に船がある最小コスト
と定めてDPすることを考える。
遷移には陸路のみ、または海路のみを使った2点間の最小距離が分かれば良くて、これはワーシャルフロイドを用いて前計算しておけば良い。
AOJ1196 - 橋の撤去
以下の3つに分けて考える。
- 葉の頂点を結ぶ辺は通る必要が無いため、1回分のコストで良い。
- その他の頂点は往復分と撤去で3回分のコストが必要。
- ただし始点と終点を結ぶパスに関しては1回しか通らないので、2回分のコストで良い。
ここまで来ると直径を3つ目で述べたパスに対応させるのが最適と分かる。
AOJ2224 - Save your cats
柵をグラフとして考えると、最終的な状態は木(森)になる。
なので辺の重みでソートして、クラスカル法と同様のようにできる。
おまけ・旅
2021.08.17
行きは東北本線で北上し福島駅へ。
— かっつ (@_KKT89) 2021年8月16日
— かっつ (@_KKT89) 2021年8月17日
前回の遠出でモバイルバッテリーを忘れてしまったが、今回は反省を生かして家出る前に確認してきたんですよね〜とギリギリまでスマホを弄ってたら、今度はライトニングケーブルを忘れたことに気が付き、涙…。
このままだと連絡が付かないので福島駅の NewDays で購入した。痛い出費に。
友人と合流。同年代の友達が運転する車に乗るの思えば初めてだなと思った。
昼は魚べいというチェーンの寿司屋に行った。店内に流れてるテーマ曲がやたらと耳に残って草です。
午後は無計画旅行特有の微妙な時間を過ごした。
風呂は折角なので飯坂温泉の方まで行って温泉に入ろうという話に。
福島 飯坂 日帰り温泉 いいざか 花ももの湯 - ホテル聚楽
— かっつ (@_KKT89) 2021年8月17日
ここに行きました。夜はタオル貸出付きで850円で入浴出来て良かったです。
(最初俺だけ1380円取られてオタクキモすぎ税取られた？と言ってたんですが、普通にミスだった(ミスじゃなかったら心に来るが)。でも友達と一緒に流れで受付してて他は何とも無かったので謎。)
久々の温泉気持ち良すぎる。畳の無料休憩所が開放されてたんですが、広くて、人もあまりいなくて快適でした。
夜はピザと酒を囲んで野球中継を見ていて最高でした。ビール初めて飲んだけど、まだ旨さがよく分かりませんでした！
2021.08.18
朝7時から某ラーメン系youtuberの動画が部屋で再生されていて、麺ゲージが高まった3人で朝ラーメンをキメた。
I'm at 椿ラーメンショップ 二本松店 in 二本松市, 福島県 https://t.co/UNL95err1f
— かっつ (@_KKT89) 2021年8月17日
昼はその場の思い付きで磐梯吾妻スカイラインに向かった(俺は話聞いてなかったので車に乗ってから行先を知った)。景色が良くて気持ち良かったです。
その後は浄土平のレストハウスで昼ご飯ということに。ソースカツ丼に心が惹かれていたが、お腹と財布に相談した結果ソフトクリームのみの注文になった。
峠道の運転難しそ〜と傍目で見ながら軽く車酔いをして下山。
福島駅周辺を散策し、昨日と同じく飯坂温泉に向かって温泉に入りました。
夜は焼肉食べ放題の店へ。最高。
飲酒して、寝た。
2021.08.19
折角18切符で来たのに普通に帰るのもつまらないな〜と思い新潟経由で東京に戻った。昨日は途中で目が覚めて4時間ぐらいしか寝れなかったので、最後危うく寝過ごしかけた。
会津若松から新潟へは快速あがのに乗車。所要時間は2時間40分ほどでも、体感ではそんなに遅く感じず、想像以上に快適な乗り心地だった。風景も綺麗だしね。
新潟駅は大きめの改修が行われているようで、画像等で印象に残っていた駅舎とは異なっていた。
1時間程しか滞在できない+金欠で駅周辺を散策するぐらいしか出来なかったが、また今度新潟に行ってゆっくり観光してみたい。
22時半過ぎに帰宅し、爆睡。
