ABC341 振り返り

感想

とりあえず、茶色は維持できたので良かった。とはいえ、今回の問題はなかなか厳しくてうわぁ…という感じ。

A 341

やるだけ。 10 * N + ‘1’ を print しただけ

B 換金みたいなの

例文がミスリーディングを誘ってくるという問題。なぜか2123と処理しているが、123と順に後ろに寄せていけばいいだけ。問題文の意味が理解できなくて、15分くらい悩んだ。

C 初期位置を求めろ的なの

500x500 マスのマップの中で初期位置になりうる場所の数を求めろという問題。
移動の指示は500個まで。なので 500x500x500 = 125000000 の計算量の可能性。

とはいえ、マップ端は必ず海という制約があるのと途中でありえないことがわかって中断できるので割りと間に合うと踏んで素直にシミュレーションした。

CPythonだとTLEだったがPyPyに切り替えたら余裕だった。

解きかたは、マップの全マス(ただし海マスは除く)からスタートして愚直にやっただけ。
10^9 前後の計算量なので不安だったが大丈夫だった。 あと、この問題は制限時間が3秒だった。

D 数学問題

残り30分くらいでここまで来たが全くわからず…
法則性があるのかなにかだろうとは思ったものの、解説を読んでもなおわかっていない。

E 良い文字列

残り10分くらいで見て、あれ?これは解けるのでは?と思って解いてみた。
間に合わなかったけど。 割と愚直に書いてみたところ… TLEした。

解説をみたら、

  • 0,1 を反転しても良い文字列かどうかは反転しない
  • 境界部分だけ再判定すればいい
  • 良くない文字列があるところにマークをつけておいて、それが含まれるかどうかで判定可能

愚直はさすがにダメだった。とはいえ、なるほどダメなところにマークというアイデアはなかった。素直じゃダメなら逆(今回だと良くない文字列)から見るというのは覚えておく

最終更新 2024/02/18 16:35:00 JST
Yakumo Saki
Hugo で構築されています。
テーマ StackJimmy によって設計されています。