yukicoder No.118 門松列(2)
問題
N本の竹がありそれぞれの高さはAiで与えられる。
門松列とは、選んだ「3つの竹の長さの降順で2番目が、左または右側になっているもの」、「3つの長さはすべて異なる」という条件も満たすものである。
門松列になるような竹の選び方の数を求めよ。
（竹の並び順が違っても、同じ竹の組み合わせなら同じものとする。それぞれの竹は番号が振ってあるので区別できる。）
感想
N本の竹の中から3つ選ぶ組み合わせは個あり、同じ高さの竹が選ばれると門松列にはならないのでその数だけ引く。
同じ高さの竹がM本ある時
同じ高さの竹から2本選ばれる場合
同じ高さの竹M本の中から2本選び,その他の高さの竹(N-M)本から1本選ぶので、個。
同じ高さの竹から3本選ばれる場合
同じ高さの竹M本の中から3本選ぶので、個。
したがって、ある高さが同じ竹が選ばれる数は個。
それぞれの高さについて門松列にならない数を計算し全体から引いていく。
#include <iostream> #include <string> #include <cmath> #include <vector> #include <cstring> #include <climits> #include <map> #include <queue> #include <algorithm> #include <utility> #define INF INT_MAX / 2 #define MOD 1000000007 using namespace std; typedef pair<int, int> P; typedef long long ll; long long combi3(int n){ return (long long)n*(n-1)*(n-2)/6; } long long combi2(int n){ return (long long)n*(n-1)/2; } long long func(int n,int m){ if(m==2)return n-2; else{ return combi2(m)*(n-m)+combi3(m); } } int main(void) { int n; cin >> n; vector<int> a(n); for(int i=0;i<n;i++){ cin >> a[i]; } map<int,int>counter; for(int i=0;i<n;i++){ counter[a[i]]++; } long long tmp = 0; auto it = counter.begin(); for(;it!=counter.end();it++){ if(it->second > 1){ tmp += func(n,it->second); } } long long ans = combi3(n) - tmp; cout << ans%MOD << endl; }
難しかった。
yukicoder No.102 トランプを奪え
問題
2人でゲームをする。まず、一組トランプの中から何枚かをマークごとに分けて重ね山札にして置く。
2人交互に以下の操作を繰り返す。
・4つ(♡♧♤♢)の山札から1つの山札を選びそこから1〜3枚カード引き手札に加える。
・カード引いた時、そのマークの山札がなくなったら相手の手札の半分を自分の手札にすることができる。
・パスはできず必ず1枚は引かなければならない。
全ての山札がなくなったら終了。最終的に手札が多い方の勝ち。
両方が常に最善手を取った場合勝つのは先攻(Taro)か後攻(Jiro)か求める。
感想
山札がなくなった時相手の手札を半分奪えるので、最後の一枚を取った方が勝つ。
それぞれの山札の枚数でメモ化。
#include <iostream> #include <string> #include <cmath> #include <vector> #include <cstring> #include <climits> #include <queue> #include <utility> #define INF INT_MAX / 2 using namespace std; typedef pair<int, int> P; typedef long long ll; int memo[2][14][14][14][14]; bool dfs(int t,int n1,int n2,int n3,int n4){ if(memo[t%2][n1][n2][n3][n4] != 0){ if(memo[t%2][n1][n2][n3][n4] == 1)return true; else return false; } if(n1+n2+n3+n4==0)return t%2==0?false:true; bool ret; if(t%2==0){ ret = false; for(int i=1;i<=3;i++){ if(n1-i>=0)ret |= dfs(t+1,n1-i,n2,n3,n4); if(n2-i>=0)ret |= dfs(t+1,n1,n2-i,n3,n4); if(n3-i>=0)ret |= dfs(t+1,n1,n2,n3-i,n4); if(n4-i>=0)ret |= dfs(t+1,n1,n2,n3,n4-i); } } else{ ret = true; for(int i=1;i<=3;i++){ if(n1-i>=0)ret &= dfs(t+1,n1-i,n2,n3,n4); if(n2-i>=0)ret &= dfs(t+1,n1,n2-i,n3,n4); if(n3-i>=0)ret &= dfs(t+1,n1,n2,n3-i,n4); if(n4-i>=0)ret &= dfs(t+1,n1,n2,n3,n4-i); } } if(ret)memo[t%2][n1][n2][n3][n4] = 1; else memo[t%2][n1][n2][n3][n4] = -1; return ret; } int main(void) { int n1,n2,n3,n4; cin >> n1 >> n2 >> n3 >> n4; if(dfs(0,n1,n2,n3,n4))cout << "Taro" << endl; else cout << "Jiro" << endl; }
yukicoderの☆3解いていて心地良い問題が多くて好き。
yukicoder No.23 技の選択
問題
体力Hの敵を必ず当たる通常攻撃と2/3の確率で当たる必殺技で倒したい。攻撃力は、通常攻撃はA、必殺技はDであたえられる。敵を倒すまでにかかる攻撃回数の期待値を求めよ。
感想
有効な手が出るまでの回数の期待値は、その有効な手が出る確率の逆数ってことを最近知ったので解けた！
・必殺技が出る(有効な手が出る)確率=2/3
・それが出るまでの回数の期待値=(2/3)^-1
DPは苦手なのでメモ化再帰で
#include <iostream> #include <cmath> #include <vector> #include <utility> #include <queue> #include <map> #include <string> #include <cstring> #include <list> #include <algorithm> #define INF 114514 using namespace std; typedef pair<double,double> P; typedef long long ll; int a,d; double memo[100001]; double dfs(int h){ if(h <= 0)return 0; if(memo[h] != -1)return memo[h]; return memo[h] = min(dfs(h-a) + 1 ,dfs(h-d) + 1.5); } int main(void) { int h; for(int i=0;i<100001;i++)memo[i] = -1; cin >> h >> a >> d; printf("%.10f\n",dfs(h)); }
（解説ではない）
2014年振り返り
競技プログラミング
・Code Formula(63位)
・CODE FESTIVAL(138位)
・CODE RUNNER(65位)
規模が大きかったおかげでオンサイトのコンテストに3つ出れた。結果は実力通りぐらい。競プロerの方々と知りあえてとても楽しいし、やる気が出た。来年も大規模のコンテストは本戦参加できるぐらいの実力は維持していきたい。
・TopCoderSRMレート(942->888)
TopCoderのSRMは全く成長がなかった。Medがまだ完璧に安定していないのが痛い。あと、深夜にある回はスルーするか寝る時間をずらすかした方が良いと思った。
バイト
今年の春まで個別指導の塾でやっていた。1年弱ぐらいしかやってなかったが、思った以上に子供が苦手とか、金貰って人に物教えるのが嫌とか、少しだけ自分の適正が分かった気がする。
たぶん辞めてなかったらコンテスト本戦とか出れてなかったから、辞めた時期もベストだったと思う。
大学
教育プログラムみたいなやつで春休みにマレーシアに2週間程行った。5万ぐらいしか大学から出してもらえないからほぼ自費だったし、宿泊先に洗濯機がなくて、毎日手洗いするのが非常に辛かった。シンガポールに行きたかった。
大学前期の成績で特待生だった。15万貰えたから嬉しい。講義中に競プロの問題解いてたりしたから、後期はあきらめ気味。
サークルとか部活とかやってないのもあって友達と関わることが少なかった気がしたのでその辺は反省。
ラブライブ
神田明神とかトークライブ行ったりして、これのおかげでかなり充実したと思う。μ'sの声優さん9人中3人は生で見ることができた。BiBiの新曲をまだ買ってないので年内に買っておきたい。
MySQLでENUM型が通らなかった話
dotinstallのMySQLをやっていてしょーもないところで躓いた。
MySQL入門 (全19回) - プログラミングならドットインストール
レコードの挿入時にENUM型の部分でエラーが出ました。
ERROR 1064(42000): You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near 'users' at line 1
入力は合ってるはずと悩むこと小一時間。
Macのテキストエディットで書いたものをコマンドラインに貼っていたのですが、シングルクォート'が‘になってる・・・
‘ → '
解決。
C言語で全角スペース埋め込んで悩んだことを思い出しました。
SRM642 Div2
Easy(250)
数字をある桁で2分割した和の最小値を求める。
stoi書く必要なかったっぽい。
Middle(500)
N個ライトとスイッチがあり、i番目のスイッチは、iの倍数の番号のライトに対応している。全てのライトをOFFにする最低何回スイッチを押さないといけないか。
小さい方から順番に消していく。
Hard(1000)
N個の都市があり、都市には0~N-1の番号が付いている。また、都市間にN*(N-1)/2本以下の道路があり、それぞれの道路には高さ制限が設けられている。予算Bが与えられ、予算を用いてそれぞれの道路の高さ制限を一度だけ上げることができる(k上げるのにk^2掛かる)。0からN-1の都市に行くことができる最大の高さを求めたい。
2分探索だなぁとは思ったけど時間内には解法は思いつかず。その後、二分探索で高さ決めて、残りの予算をキーにした優先度付きキューで幅優先したらできた。
次で緑にあげられるように頑張る!
