探索の考え方の間違っているところ

Question

前提・実現したいこと

この問題を解きたいです.
https://beta.atcoder.jp/contests/arc096/tasks/arc096_a
ピザcをk枚買うと決めてかかったコードです.

発生している問題・エラーメッセージ

コンパイルエラーはありません。
いくつかのテストケースで間違いだと言われました。

該当のソースコード

import java.util.*;
import java.io.*;

public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    int a = scan.nextInt();
    int b = scan.nextInt();
    int c = scan.nextInt();
    int x = scan.nextInt();
    int y = scan.nextInt();

    long ans = Long.MAX_VALUE;

//x,y<=10^5なので、最悪k=2*10^5
    for(int k = 0; k <= 200000; k++){
      long sum = c*2*k + a*Math.max(x-k, 0) + b*Math.max(y-k, 0);
      ans = Math.min(ans, sum);
    }

    System.out.println(ans);
  }
}

試したこと

ピザa, bを固定すると変数が2つになって、つまりfor二重でO(N^2)になるので
ピザcを決めることでO(N)にしたこと.（TLEからWAになっただけでした)

補足情報（FW/ツールのバージョンなど）

Atcoderにおける提出言語 : Java8 (OpenJDK 1.8.0)

Answer 1

試してないですが、単純に気になった点を。

• クラス名がMainになってないです。
• k <= 200000ではなくk <= 100000では？

Comments

[退会済みユーザー]

回答ありがとうございます.
atcoderの他の方のコードを見ても仰せのように100000だったのですが
どうして200000でなくてそうなのか教えていただきたいです.
x = 10^5, y = 10^5のときに全てピザcで賄おうと思うと、その2倍の2*10^5 = 200000枚
必要ではないですか?
あと, クラス名修正いたしました. ご指摘ありがとうございます!

[dice142]

> どうして200000でなくてそうなのか教えていただきたいです.
金額の計算のところで2倍しているからではないでしょうか。

[退会済みユーザー]

大変たすかりました.
ありがとうございました.