2020年 6月 7日 消費期限が切れていない牛乳
今、消費期限が切れていない牛乳の集合をかんがえます。
このとき、消費期限が切れていない、という条件から、消費期限が切れていない牛乳の集合には、存在しない牛乳も含まれていることになる。
しかし、牛乳は消費期限が切れていないうちに飲んだほうが良い、というのが通説である。
ここで、消費期限が切れていない牛乳の集合の外にある牛乳を考える。
やっぱかんがえない。
まえがき
ブログのタイトルが変わりました。
しもネタ的な意図は一切無いです（マジ）
にぼしのメモ、とか、にぼしの日記、とかにぼしの日常って、なんともひねりがなくてかぶりがちでとても悲しいので、布団に入りながらどうしようかとかんがえていました。
結局ゲームの友達がパッと出した「今日のおにぎり」に決まりました。
テキトウな言い訳を作ると、「おにぎりっていうのはいろんな具材があって、さまざまな味がある…（以下(ry) って感じで、日々変わりゆくものを綴る場所だよ。みたいなニュアンスです。エモいね
健康管理
健康です。 大学のやるべきこと全てやったふりをして生きていくのはとても楽しいですね。
何した
子供を泣かせました。
具体的に
俺は悪くない。先に手出してきたのはあいつだし。 *1 <- 6/18追記
今日解いた問題
ABC128 D- equeue
- [全探索(的な?),最大化]
この問題のポイントは以下に挙げる100000007つです。 1. 操作の回数はK回以下 2. 宝石を筒に戻す操作は最後に行えば良い。 3. 左からと右から、何個ずつ取り出すかで場合分け.
1のK回以下という制約によって、右から取り出して右に入れて右から取り出して右に入れる。という操作(4回)を、右から取り出した後、戻すという2回の操作に出来ます。
2について。筒から取り出している作業の途中で筒に宝石を戻すと、めんどくさいです。
例えば、左からXを取り出した後、Xを左に詰めると、その後またXを取り出すかどうか…みたいになってだるいっす。戻すなら最後に戻せばいいじゃん。
（戻すのは後にしておけば、筒から取り出せるモノの数が増える)
(選択肢が増える)
3はポイントと言うか解法ですね。
左からi個取り出す, 右からj個取り出すと決めました( i + j <= k) このとき、i+j回取り出した後で、k - (i + j)回、まだ操作を行うことが出来ます。
よって、取り出した(i+j)個のうち、価値が負のものについては筒に戻しちゃいましょう。
ただし、宝石の数を超えたり手持ちが0個未満にならないように気をつけましょう。
この問題は、iとjの組み合わせがN2、iとjを決めたとき、(i + j)個取り出す -> (k - (i + j))個戻すか決める。ってことで計算量はいくつだ？KN2かな？
解けて嬉しいです。
ABC134 E- Sequence Decomposing
- [deque,最小化,LIS,LDS]
なんですかこれ、難しい。なんとなく、要素を左から見ていって、見ている要素を何と同じ色にするか、ってとき、出来るだけ大きい数字のものと一緒にすればいいっていうのは分かった。
push_frontをするために、dequeを用いたらしい。ふぅむ
LDSでも解けるらしい。 う〜ん、理解の及ばぬ解説ACですね。
ABC138 E- Strings of Impurity
- [部分列,超巨大文字列, 二分探索,]
うーん、なんとも…
超巨大文字列s'の何文字目を使うかっていうのを保持するのではなくて、sの何文字目を使うかでやっていくらしい。
なるほどなぁ・・・で、そのためにsを2つくっつけたもので見ていくと。
解説シャキョウACだけどちょっと理解は進んだよ。
あ〜少しずつ分かってきた。面白い問題だね。k
Tenka1 Programmer Beginner Contest
- [構築,数式イジイジ,楽しい日曜日]
N = 3 の時はYesなのか…（Sample1)
N = 4 のときはNoなのか…（Sample2)
N = 5 は!?!?! (Sample無) 手元動かす→ダメそう…
以下ッ考察。
1~Nは、どれもちょうど2つの集合に含まれるということから、1が2個、2が2個…Nが2個ということで、S1からSnまでに含まれる要素の個数は全部で2 * N 個有りますね。
次に、構築する集合がk個の時、S1~Skのk個の集合を構築してあげます。
ここで次に、もう一つの条件を見ます。
S 1 , S 2 , . . . , S k のうちどの 2 つの集合をとっても、それらに共通して含まれる要素はちょうど 1 つである 。つまり、S1はS2と共通してa1を共通して持つ、S1はS3と共通してa2を持つ…S1はSkと共通してa(k-1)を持つ。という風になります。
よって、S1は要素を(k-1)個もちます。 他の集合S2~Skに対しても同様のことが言えるのでS1,S2,...,Skは全て(k-1)個の要素をもちます。
そして、S1からSkがそれぞれ(k-1)個の要素を持つ時、
S1の要素の個数 + S2の要素の個数 + ... + Skの要素の個数 = k * (k-1)
これが2 * N と一致していれば、そのような集合は作れます（証明:AC)
だから、構築出来るかどうかの判定は,K = 1 から試してやっても良いですよね。（K=1からNまで試したって105回しかねえんだし)
はい、で、構築できるってことが分かりました。
じゃぁ、こっからどうやって集合作っていこうか？っていうのを天才にぼちゃんが図解してあげよう。
N=6のときを例に持ってくるね。
N = 6 の時、集合の個数を4個、集合の中身を3個としてあげるとうまく構築することができるよ!! (各集合に対して、自身を除いて集合は3個あるから、要素の数の1個ずつが、別の集合に対する共通する要素として生きているね。)
それでは図を。
構築の仕方としては,頭の中に
for(int i = 0; i < n; i++){ for(int j = i+1; j < n; j++){ } }
という二重for文が浮かんだので、そんなイメージを持ってやりました。
なんか、こういう感じのにじゅうfor文と似てるな〜って思った。
vector<vector<int>> ans(100010); int mother = 0; int child = 1; for(int i = 1; i <= n; i++){ ans[mother].push_back(i); ans[child].push_back(i); if(ans[mother].size() == k - 1){ mother ++; child = mother + 1; } else { child ++; } }
これが構築の部分ですね。
CODE FESTIVAL 2017 Final A-AKIBA
- [if文]
分からんかったので力で通しました。
int main() { string s; cin >> s; if(s=="AKIHBR") cout << "YES" << endl; else if(s=="KIHABR") cout << "YES" << endl; else if(s=="AKIHABR") cout << "YES" << endl; else if(s=="KIHBAR") cout << "YES" << endl; else if(s=="AKIHBAR") cout << "YES" << endl; else if(s=="KIHABAR") cout << "YES" << endl; else if(s=="AKIHABAR") cout << "YES" << endl; else if(s=="KIHBRA") cout << "YES" << endl; else if(s=="AKIHBRA") cout << "YES" << endl; else if(s=="KIHABRA") cout << "YES" << endl; else if(s=="AKIHABRA") cout << "YES" << endl; else if(s=="KIHBARA") cout << "YES" << endl; else if(s=="AKIHBARA") cout << "YES" << endl; else if(s=="KIHABARA") cout << "YES" << endl; else if(s=="AKIHABARA") cout << "YES" << endl; else if(s=="KIHBR") cout << "YES" << endl; else cout << "NO" << endl; }
あとがき
今日の晩ごはんはカップラーメンです。
野菜をとらないとまずい事態になりそうですね…
以下は毎回記事に貼っているテンプレート
基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)
*1:うそだよ
