思考のジャンプ幅が狭いなら,飛ぶ回数で補えばいいじゃない!!

非情報系30歳が競技プログラミングやWeb開発を始めるとどうなるか?

AtCoder いろはちゃんコンテスト Day2 C - 陽気な妖姫

はじめに

  • AtCoderの問題を復習しています.

  • 公式解説や上位陣による解説ブログを読んで,自分に足りなかった部分や得られた知見を自分なりに消化してアウトプットしようと思います.

想定読者

  • 筆者と同じくらいのレートの方:失敗談・回り道をみて,共感していただける部分もあるかもしれません.

  • コンテストのwriterの方:サンプル n=1ではありますが,レート茶色上位~緑下位の参加者がつまづく可能性があるポイントを知っていただく機会になるかもしれません.

記事の狙い

  • 丁寧でわかりやすい解説記事がたくさん公開されているため,解法そのものについての記述は少ないと思います.

  • ACに至るまでにどうしてそのような発想に至ったのか,考察や実装で試行錯誤した過程(=失敗談や回り道)を重視しています.

  • また,得られた前提知識や着眼点について,今後応用できるように抽象化・言語化していきます.

  • 間違いや勘違いなどがございましたら,ご指摘・ご指導いただけると幸いです(大歓迎です).


問題のリンク

C - 陽気な妖姫 (300点)

ACに至るまでの考察・実装のコツなど

  • 構築する整数列 Xの最大値は,元の数列 Hにおいて重複を除いた個数と一致する(要証明).
  • 重複を除いた数列 H^{'}を昇順に並べる.
  •  H^{'}が単調増加であることを利用して,数列 Hの各要素が H^{'}のどの位置にあるか,二分探索.計算量はソートがボトルネックとなって O(HlogH^{'})

提出コード

試行錯誤した過程

  • 最大公約数で各要素を除算する.

    • ローカル環境で試したサンプル2がWA.
    • 本文の「大小関係を維持したまま、出来るだけ小さい数に置き換えて覚えておきたい」という点を見落としていたことに気がつく.

  • 要素を昇順で並び替える.最初の要素について1で固定.ある要素に着目したとき,直前と異なる値のときは答えを1増やす.

    • またしても,サンプル2でWA.強めのサンプルでありがたい.
    • 元々の要素の順序を保持するのを忘れていた.

  • 上記の考察に加えて,元々の要素の順番を連想配列(辞書)に格納することに.

    • サンプルはすべてAC.
    • 提出すると,大量のWAが吐かれる.
    • 一旦,離席して水分を補給.

得られた知識・知見

  • 座標圧縮という用語・抽象表現(用語は聞いた程度です.それに近いことを再発明した気になっていました)
    • 各要素の大小関係を維持しながら,その値を小さくできる.計算量の大きな削減につながりそう.

感想

  • 上位陣はライブラリを事前に用意している方が多い印象でした.シンプルかつ最短コースで解法にたどり着いているのがよくわかりました.
  • 単調増加の性質を利用して,二分探索で効率よく探索するというところは以前の復習が生かされているはず.
  • 時間がかかったとはいえ,本番中になんとかACできた点は成長できたと思います.
  • 各ステップで反例がないかどうかを確認する習慣を身に着けたいです.

課題

  • 要証明部分を追記する.
  • 座標圧縮について学習する.

参考

記事を執筆された皆さまへ: 掲載不可の場合はお手数をお掛けしますが,@k_hiro1818までご一報ください.