本の森

SRM492DIV2の問題

今日はTopCoderのSRM492DIV2の問題を解きました。

コンテストに参加しないでも問題を解けて、頭のいい人たちのプログラムを見ることができるのもTopCoderのいいところですね。

【問題】
ワインセラーを持っているゴーゴさんがタイムマシンを発明しました。タイムマシンを使って数個のワインセラーを未来の状態にすることができるのですが、数個のワインセラーを成熟させるとそれ以外の中の数個のワインセラーは成長しなくなってしまいます。ゴーゴさんはどの組み合わせでワインセラーを成熟させると最も利益が出るでしょう？という問題です。

引数が利益の出る値の配列と戻さないといけないセラーの数の配列です。
戻り値は最大の利益を返します。

【解法】
この問題で注目すべき点は利益と損失の差が最大になる組み合わせを探すことと、同じワインセラーを成長させたり、退化させたりできないという点だけですね。2重ループのfor文などを使って組み合わせを探していきます。

【フローチャート】
ワインセラーの数を知る。hairetu.lengthを使う。
↓
for文の2重ループで利益と損失の差を求めていく。
このとき、同じワインセラーは調べない
↓
差が最大になった値(最大の利益を)戻り値として返す

【プログラム例】
import java.util.*;

public class TimeTravellingCellar{
  public int determineProfit(int[] profit, int[] decay){
    int N = profit.length;
    int ans = Integer.MIN_VALUE;  //最大値を探すので最小の値を入れておく
    for(int i = 0; i < N; i++){
      for(int j = 0; j < N; j++){
        if(i != j)ans = Math.max(ans, profit[i] - decay[j]);  //2つの値を比べて最大の方を返す
      }
    }
    return ans;
  }
}

【感想】
英文がちゃんと理解できたらなんてことのない問題でした。ですが高得点をとれるような高率のよいきれいなプログラムというのがいまだよくわかりません。しばらくは頭のいい人たちの真似をして技を盗んでいきたいと思います。

今日の戦績

今日のTopCoderの戦績は見事ゼロ点でした。Challengeで例のごとく撃ち落とされました。

問題をしっかり理解できていなかったというのもあるけどやっぱり力不足ですね。

ということで今日の問題の復習です。

【問題】
数種類のキュウリがあって、その中からK個のキュウリを買います。予算はbuget円です。K個のキュウリの組み合わせのうち、1つでも予算を超える場合は買うことができません。買い物ができる場合は”YES”、できない場合は”NO”を返すメソッドを作ってください。というような問題です。

引数・・・cum(int price[], int budget, int k)
戻り値・・・YES　or　NO

【解法】
この問題を解くには問題文を解釈しなおさないといけなかったようです。

キュウリの組み合わせのうち一つでも予算を超える場合は買うことができない。

ということからすべての組み合わせを試さないといけないのかと思ったのですがそんなことはなく、

値段が最大になるときに買うことができるかどうかを調べればよかっただけでした。

この辺の解釈がまだ苦手です。

【フローチャート】
配列を並び替える。Arrays.sort()を使って昇順に並べ替える。
↓
配列の要素を後ろから順にキュウリを買う数だけ足す。
↓
予算を超えているか調べる

【プログラム例】
import java.util.Arrays;

public class CucumberMarket{
  public String check(int[] price, int buget, int k){
    Arrays.sort(price);
    int sum = 0;
    for(int i = price.length-1; i >= price.length-k; i--){
        sum += price[i];
    }
    if(budget >= sum)return "YES";
    else return"NO"
  }
}

【感想】
睡眠時間が少なかったとは言え、他の人のプログラムを見てなんでできなかったのだろうと悔やまれます。

今回の結果は成績に反映されないらしいのでこれ以上Ratingが下がらずラッキーでしたが、

そろそろ点が取れるようになりたいものです。

文字列の便利テクニック

【文字列の問題を解くのに便利なメソッドまとめ(Java編)】

・toChartArray() 
　文字列を文字配列に変換するメソッド

 　String newStr[] = "abcde".toChartArray();
  
　のように使うと"abcde"という文字列が{"a","b","c","d","e"}という文字配列に変換することができます。

・Arrays.sort()
　
　文字配列を昇順に並び替えてくれます。

　java.util.* をインポートする必要があります。

　クイックソートで並び替えています。

・a.equals(b)
　
　文字列を比較するときの==に相当します。

　aという文字列がbに等しいときにtrueを返します。

　文字列を比較する際は==を使うことはできません。
　

アルゴリズムの勉強

最近プログラミングのアルゴリズムの勉強のために、TopCoderというプログラミングコンテストに参加しています。

DIV1とDIV2の2つのレベルがあってそれぞれ3問を90分かけて問題を解くという形式となっています。

インターネットで参加できるので自分のようなプログラミング初心者にも参加しやすいコンテストとなっています。

おとといの問題は以下のようなものでした。

【250点問題】
旅行に関する問題で、引数として旅行可能な日数とそれぞれの都市を旅行するとかかる日数が配列で与えられます。

その条件で、できるだけ多くの都市を巡ると何個の都市を巡ることができるか？という問題でした。

解き方としては

1．都市を旅行する日数の少ない順に並び替え
Arrays.sort(配列[]); を使う。・・・自動的にクイックソートで小さい順に配列を並びぁ得てくれる。

2．旅行可能な日数を超えないように小さい順から日数を足していく。

3．何回足したか(何個の都市を旅行したか)を戻り値として返す。

と1問目は比較的簡単な問題でした。

ただ、２問目は問題の英文が長すぎて理解できないという悲しい状況になりました。

プログラミングの勉強もそうですが、英語の勉強をもっとしなきゃと思う今日この頃です。