SRM621 div2 反省会

easyもmediumも問題文読めたし、方針も立った。
「お、これ2完じゃね」とか言ってたら0完太陽生えたので、今のうちに解き直しておきます。

easy

問題

50文字以下の文字列を、50個以下含む配列stringListが与えられる。
これらの並び順が

• 昇順の辞書順(例:"car" < "carriage" < "cats" < "doggies")にソートされていれば「"lexicographically"」
• 昇順の文字列長順(例:"car" < "cats" < "doggies" < "carriage")にソートされていれば「"lengths"」
• 両方にあてはまれば「"both"」
• どちらにもあてはまらなければ「"none"」

を返す。

解き方

o(n)で比較するだけ
「コピーとって、ソートしたものと元配列を比べる」みたいな人のほうが多かった
なお「"lengths"」を「"lentghs"」と記述したため落ちた模様

#include <string>
#include <vector>

using namespace std;
typedef long long ll;

class TwoWaysSorting{
public:
	bool checkDic(vector<string> a){
		for(int i=0;i<a.size()-1;i++){
			if(a[i]>a[i+1])return false;
		}
		return true;
	}
	
	bool checkLen(vector<string> a){
		for(int i=0;i<a.size()-1;i++){
			string x=a[i],y=a[i+1];
			if(x.size()>y.size())return false;
		}
		return true;
	}

	string sortingMethod(vector <string> stringList){
		bool a=checkDic(stringList);
		bool b=checkLen(stringList);
		if(a && b)return "both";
		else if(a && !b)return "lexicographically";
		else if(!a && b)return "lengths";
		else if(!a && !b)return "none";
		return "none";
	}
};

medium

問題

10^6 以下の非負整数を20個以下含んだ配列Sが与えられる。
この配列に含まれる整数を組み合わせて作ることが出来ない、最小の値を出力する。(例: S={1,2,3}　とすると、出力は 7)

解き方

要素数が20個ほどなのでdfsで全列挙しておき、出現していない値を下から探した
なお全列挙の結果保存用配列のサイズを (10^6 + 1) しかとっておらず、次の日に (20*10^6 + 1)に変えたら通った。
よくよく見直すとちゃんとセグフォってたし、どう考えても気づくべきだった。

#include <vector>
using namespace std;

class NumbersChallenge{
public:
vector<int> str;
bool num[2000001];

	bool dfs(int i,int sum){
		num[sum]=true;

		if(i==str.size()){return false;}
		
		if(dfs(i+1,sum)){return true;}
		
		if(dfs(i+1,sum+str[i])){return true;}
		
		return false;
	}
	

	int MinNumber(vector <int> S){
		str=S;
		bool trash=dfs(0,0);	//返り値ｓは再起時のみ利用

		for(int i=0;100001;i++){
			if(num[i]==0)return i;
		}
		return 0;
	}
};

おまけ

midiumをDPで解いている人も多かったのでDPでも解いてみた

#include<vector>

using namespace std;
bool dp[2000001]={};

class NumbersChallenge{
public:
	int MinNumber(vector<int> S){
		dp[0]=true;
		for(int i=S.size()-1;i>=0;i--){
			for(int j=2000000;j>=0;j--){	//値の2重使用対策
				if(j-S[i] >=0 && dp[j-S[i]]){
					dp[j]=true;
				}
			}
		}
		for(int i=0;i<2000001;i++){
			if(dp[i]==false)return i;
		}
		return 0;
	}
};

まとめ

• 雑魚のくせに早解きしようとするからミスる、確認はしっかりしよう。
• 返す文字列など、指定されているもののtypoは致命傷(トラウマだし次から全部コピペしようかな...)。
• 値の制約、必要な配列のサイズをよく考えてからコードを書き始めよう。
• 本を参考にしないとdfsすらまともに書けないのそろそろなんとかする。