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

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

NIKKEI Programming Contest 2019 復習

はじめに

  • AtCoderで解けなかった問題(AtCoder Beginner ContestのC問題、D問題が中心になると思います)を復習しています.

  • AtCoderのレートでは,茶色上位~緑最下位を行ったり来たりしています.

  • コンテスト本番で解けなかった問題を,どのように考察・実装すればよかったのか?

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

  • 間違いや勘違いなどがございましたら、ご指摘・ご指導いただけると幸いです.


C - Different Strokes (400点)

コンテスト本番における筆者の到達度

  •  A_{i} -  B_{i}を取る  +αで一般化を図ればいいと思い込んだまま,無限に時間を溶かしました.
  •  A_{i} +  B_{i}の発想に至らず.

解説ブログの証明を読んだ感想

  • 公式解説 1を見てある程度納得したものの,自分がコンテスト本番で気がつけるかというのは全くの別問題だと感じました.

証明例1 2 3

  • 数式を読んで納得しました.
  •  Xの右辺において,異符号で打ち消しあう部分(第3項と第4項)をどのように思いつくのがポイントだったのではないか,と思っています.

    • 第3項:高橋君が料理 iを選択することで,青木さんが料理 iを取れなくなる→高橋君の幸福度の加算分
    • 第4項:青木さんが料理 iを選択することで,高橋君が料理 iを取れなくなる→高橋君の幸福度の減算分
    • と解釈しました.

感想

  • 考察の妥当性を明示できるため,数式を積極的に使っていこうと思います
  • コンテスト本番で,自分にとってはどのように思いつくのが(発想の飛躍が必要な場合もあり)難しいケースもあるかもしれません

証明例2 4

  • もっともシンプルな条件(この場合は,2つの要素の比較)から一般化を図る

感想

  • 考察のとっかかりとしてイメージしやすかったです
  • 一般化を図るときに,自分の数学力では嘘解法かどうかのチェックが難しいケースもあるかもしれません

実装のポイント

  •  A_{i} B_{i} A_{i} +  B_{i}の大きい順にソート
  • 方法1:tupleで  A_{i} B_{i},  A_{i} +  B_{i}を管理
  • 方法2:sorted()関数のkeyにlambda式で条件 A_{i} +  B_{i}を指定

ソースコードの一例

  • 解説ACに賛否両論あるかと思いますが,自分で実装できたほうが理解が深まると考えています
  • Python3で実装してみました
  • tuple版
  • sorted()関数版

得られた知見

  • 数式で定式化してみることはできてないか?
  • もっともシンプルな条件から一般化を図れないか?

感想

  • 標準ライブラリの便利さ・コードを簡潔に記述できるという点から,これまで以上に使っていこうと思います.
  • lambda式の理解が浅かったことを痛感しました(今も十分とは言っていないです)
  • コンテスト上位者は,思考に寄り道がない・少なく,実装もシンプル.だからこそ,短時間でACできるのだということを再確認しました.
  • 記事を執筆されている方々には,感謝してもしきれないです.

つまづきポイント(○印が該当を表す)

問題 解けず 理解 発想 方針 実装
D

各項目の意味

  • 解けず:自力で解けたどうか
  • 理解:解法を理解するのに時間を要した問題
  • 発想:発想が難しい(思いつけば簡単)な問題
  • 方針:方針を見出すのが難しい問題
  • 実装:実装に手間取った問題

参考

 5: http://cocodrips.hateblo.jp/entry/2017/04/11/032000

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