yukicoder No.163 cAPSlOCK
問題
文字列の小文字は大文字に大文字は小文字にする。
感想
それぞれのxor 32をとると大文字・小文字が反対になる。
#include <bits/stdc++.h> using namespace std; int main(void) { string s; cin >> s; for(int i=0;i<s.size();i++){ s[i] = s[i]^32; } cout << s << endl; return 0; }
Twitterで見た
【今日の競プロ】
今日は3/2ですね。32といえば2^5と思う方が大半でしょう。実はアスキーコード表において、アルファベットの大文字と小文字のバイト値のXORを取ると32になります。全て大文字にせよ、などの簡単な文字列処理の問題でコード長を短縮するのに役立つかもしれません。
— 双葉 純 (@catupper) 2015, 3月 2yukicoder No.67 よくある棒を切る問題(1)
感想
長さを二分探索したけど、で回すと大きい数の時、無限ループしてしまいました。
なので適当に100回ぐらいで打ち切った。
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> P; typedef pair<int,pair<int,int>> PP; typedef long long ll; const double EPS = 1e-10; const int INF = 1e9; const int MOD = 1e9+7; int dy[] = {0,1,0,-1}; int dx[] = {1,0,-1,0}; struct edge{int to,cost,tm;}; bool func(double len,ll K,vector<int>&L){ ll cnt = 0; for(int i=0;i<L.size();i++){ cnt += L[i]/len; if(cnt >= K)return true; } return false; } int main(void) { ll N,K; cin >> N; vector<int> L(N); for(int i=0;i<N;i++){ cin >> L[i]; } cin >> K; double low=0,hi=1e9,mid=0; int t = 0; while(hi > low+EPS && t < 100){ mid = (low + hi)/2; if(func(mid,K,L)){ low = mid; }else{ hi = mid; } t++; } cout << fixed << setprecision(11) << low << endl; return 0; }
double値の二分探索初めてした気がする。
無限ループに陥らないように気をつけていきたいです。
yukicoder No.27 板の準備
感想
制約が小さいので全探索できそう。
A,B,Cのそれぞれの長さ、それぞれの使う枚数について回して30^6ぐらいだけど実際はもう少し小さいから間に合った。
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> P; typedef pair<int,pair<int,int>> PP; typedef long long ll; const double EPS = 1e-8; const int INF = 1e9; const int MOD = 1e9+7; int dy[] = {0,1,0,-1}; int dx[] = {1,0,-1,0}; int sub(int a,int b,int c,int n){ int ret = INF/2; for(int i=n/c;i>=0;i--){ for(int j=n/b;j>=0;j--){ for(int k=n/a;k>=0;k--){ if(c*i+b*j+a*k == n){ ret = min(ret,i+j+k); } } } } return ret; } int func(int a,int b,int c,vector<int>& v){ int ret = 0; for(int l=0;l<4;l++){ ret += sub(a,b,c,v[l]); } return ret; } int main(void) { vector<int> v(4); cin >> v[0] >> v[1] >> v[2] >> v[3]; sort(begin(v),end(v)); int ret = INF; for(int a=1;a<=30;a++){ for(int b=a+1;b<=30;b++){ for(int c=b+1;c<=30;c++){ ret = min(ret,func(a,b,c,v)); } } } cout << ret << endl; return 0; }
★3なのに全探索で通ってしまい不安。
DPで縮められるらしいので調べておきたい。
Codeforces #294(Div.2)
1575->1516(-59)
レートは下がっちゃったけど人が多いのは楽しいですね。
A,B:手間取った。
C:よくわからないので二分探索しようとしたけど、二分探索が書けなくて焦った。
D:累積和してどうするんだろう・・・
E:読めてない
二分探索きっちり書くの難しい。
int low=min,hi=max,mid=0; while(hi > low+1){ mid = (low + hi)/2; if(/*条件*/){ low = mid; }else{ hi = mid; } } cout << low << endl;
Rubyで形態素解析してマルコフ連鎖
はじめに
形態素解析とマルコフ連鎖で面白いことできそうと聞き、調べてみると既に色んな人がやっていました。
Rubyで何か書きたいと思っていたので、参考にしながら試してみました。
[参考リンク]
マルコフ連鎖でTwitter BOTを作る - FLYING
[プログラミング作法]マルコフ連鎖アルゴリズムをrubyで実装してみた - Qiita
やろうとしたこと
過去ツイートにある単語を適当に繋ぎあわせて新たに文章を作る
流れ
TwitterAPIを叩き自分の過去ツイートを最近から数千個読み込んでくる。それぞれのツイートをMecabで形態素解析して単語に分解し、辞書っぽいものをつくる。作成した辞書からマルコフ連鎖で適当に単語をつなぎあわせて文章にする。
（辞書的なものとマルコフ連鎖については上記リンクに詳しく書いてあるので省略。）
結果
実行結果："レポートのやる気が起きなくてほげ"
全体的にツイートが短いので、1つのツイートがそのまま出てきてしまったりしてあまりうまくいきませんでした。最初の単語を良い感じ指定すれば少しそれっぽくなるかな。
ツイートは微妙でしたが、同じような要領でニュース記事の要約っぽいことをしてみると、うまくいくことが多かったのでまぁ満足。
記事：http://news.tv-asahi.co.jp/news_international/articles/000044089.html
要約結果："韓国国防省によりますと、北朝鮮は来月初めに行われる米韓合同軍事演習の中止を繰り返し求めています。"
ソースコード
ほとんどコピペだし、めちゃくちゃだけど一応貼っときます。
yukicoder No.135 とりあえず1次元の問題
問題
N個の1次元の座標が与えられ、その中から同じ座標ではない2点を選ぶ。
最小距離を求めよ。
感想
星1だし制約を確認せずに全探索で大丈夫では思ったらTLE。
unique使ってみた！
#include <bits/stdc++.h> #define MOD 1000000007 using namespace std; typedef pair<int,int> P; typedef pair<int,pair<int,int>> PP; typedef long long LL; const double EPS = 1e-8; const int INF = 1e9; int dy[] = {0,1,0,-1}; int dx[] = {1,0,-1,0}; int main(void) { int N; int ret = INF; cin >> N; vector<int> x(N); for(int i=0;i<N;i++)cin >> x[i]; sort(x.begin(),x.end()); x.erase( unique(x.begin(),x.end()), x.end()); for(int i=0;i<x.size()-1;i++){ ret = min(x[i+1]-x[i],ret); } if(ret == INF)cout << 0 << endl; else cout << ret << endl; return 0; }
ブログのネタを探しています。
