ぱらつり記

No description

学内ミニプロコン2

問題

  • 問題文はこちら
  • 参加者ごとの出力結果を用いて順位付けが行われました。

自分の解答

  • やったこと
    • 最大の入力を上限とした数列をエラトステネスの篩にかける。
    • x方向y方向の帳尻を合わせる。
    • おしまい。

結果

ケース 入力 結果
1 -1 -1 AC
2 わすれた AC(トップ)
3 -20000000 -2 AC
4 5088825 987613243 MLE
5 82621 9282332 AC(トップ)

メモ

  • ケース3

    • 提出は早かったものの、愚直かつ貪欲な実装だったので、先輩によって最適解が提出されました。
      • 20000000 = 19999999 + 3 - 2 (自分の解答)
      • 20000000 = 19999981 + 19 (最適解)
    • 実装力が欲しい……
  • ケース4

    • 篩にかける用の配列が確保できませんでした。ち~ん(笑)
    • -1010 <= x, y <= 1010という制約がおかしいのでは??(八つ当たり
    • これ以上改善できなさそうだったので諦め

まとめ

終了後のコードレビューで、先輩方が「(弱い)ゴールドバッハの予想」など用いていたので「んあー」ってなりながら聞いていましたね。 数学こわい

あと平方根が絡むときの計算手法。

  • i <= Math.Sqrt(n) -> i * i <= n
  • 負担は軽くしていこうな

先週の記事の終わりで WebClientの初動受信が遅いんじゃないかと疑いましたが、適当にYahooのロゴを読ませてから処理させてやると早くなった気がしました。(要検証)