satojkovic

satojkovic

Google Kickstart 2020 RoundA - Bundling問題の解説

Kickstart2020 RoundAのBundlingの問題です。 問題N個の文字列が与えられて、これをK個毎のグループに分ける場合（グループ数はN/K）、各グループのスコアをグループに属する全文字列のcommon longest prefix長とした時、最大となるスコアを求めるというものです。 スコアの計算は、例えば{RAINBOW, RANK, RANDOM, RANK}というグループであれば、RAがlongest prefix長なので2となります。 アルゴリズム

satojkovic

    • Google Kickstart 2020 RoundA - Allocation問題の解説

      Kickstart2020 RoundAのAllocationの問題です。 問題売り出し中のN軒の家の価格（i番目の価格は$A_i$）と、使用可能なバジェットBが与えられた時に、最大で何軒購入できるかを求める問題です。 $${1 \leq B \leq 10^5}$$、$${1 \leq A_i \leq 1000}$$で、またTest set1では$${1 \leq N \leq 100}$$、Test set2では$${1 \leq N \leq 10^5}$$という

      satojkovic

      • Google Kickstart 2020 RoundA -Workout問題の解説

        Workoutの問題について、公式の解説と、Youtubeで見つけた有志の方の解説動画を見て実装しました。 コードは、こちらに置いています。 問題問題文を要約すると、次のようなことです。 各要素がトレーニングセッションの時間（Mi）を表すN個のリストが与えられます。 このリストにおいて、隣り合う二つのセッション間の時間差のうち、最大のものを このトレーニングの「困難さ」として定義、セッション間に最大でK個までセッションを追加した時、最も小さい「困難さ」を求める。 またこの時

        ¥100
        satojkovic

        • Google Kickstart 2020のRoundA - Plates問題の解説

          Google Kickstart 2020 RoundAのPlatesの問題について、解説をしてみたいと思います。 実装したものは、こちらにあります。 問題の要約N個のスタックに、それぞれK個の皿があり、それぞれの皿には正の値（beauty value）が書かれている。ここからP個の皿を取り出した場合、その和に関して最大値を求めたいという問題です。 アルゴリズム1(TLE)N個のスタックから皿を取り出す全パターンを考えて、そのパターンのうち、取り出した数がP個である組み合

          ¥100
          satojkovic