pyonta

pyonta

  • プログラミングコンテスト 練習記

    AtCoder, TopCoder, Codeforces などの プログラミングコンテスト の参加記・練習記を記述します。

  • オンラインコース 学習記録

    Couseraなどのオンラインコースの勉強記録です。

  • 英語勉強記

    英語の勉強記録

LeetCode で学んだ "整数列 nums=[...,...,...] から任意に選んで target=... に なる整数の組み合わせを見つけろ" (2Sum, 3Sum, 4Sum, Combination Sum II) で使う定石

TL;DR 大事なのは、1番目を配列のどこから取るか、2番目をどこからとるか、...を動かしていくことであって、配列の1番目の数を使うか使わないか、ではない。この方針でないと、同じ組み合わせを除外するのに苦労する。 ダメな例を改善してACすることもできたがコードが煩雑になるのでオススメできない。 ダメな例 (自分が最初にやってた。) class Solution { void helper(vector<int> &cands, int index, int tar

pyonta

    • AtCoder Beginners Contest 2019/08/18

      A-D問題: 問題なくAC. D問題で最大値をミスってREしてしまったのが痛かった。 E問題: 愚直にfindしたところ、TLE。TLE する 反例ケースとして、そもそも検索対象に含まれない文字を入れたままfindするの無駄だよなあ、と考えているところで time over. 解説を聞いたところ、部分列判定をするときには、文字の現れるindexを文字ごとに降順ソートして管理しておいて、場所 i 以降で 文字 c が現れる位置を検索、つまり upper_bound(low

      pyonta

      • Atcoder Beginners Contest 2019/08/10

        D問題: 良かった点: deadlineが近いバイトを優先して選択するところ。 ダメだった点(1): 選択した後でさらに sort する、という考え方が足りなかった。選択可能なものを最初に選ぶ(deadlineでsort)したあとに、選択したものの時給が高いものを選ぶ(選んだ後に給料でsort)するということ。 自分は、選択前にdeadlineでsortと給料とでsortを両方行ってしまった。これだと、deadline が近くて給料が安いものを取ってしまったことで、de

        pyonta

      LeetCode で学んだ "整数列 nums=[...,...,...] から任意に選んで target=... に なる整数の組み合わせを見つけろ" (2Sum, 3Sum, 4Sum, Combination Sum II) で使う定石

      pyonta

      マガジン

      • プログラミングコンテスト 練習記
        2本
      • オンラインコース 学習記録
        0本
      • 英語勉強記
        0本