2020年 6月 1日
まえがき
6月になりましたね。 6月を英語でなんていうか知っていますか?
ところで月は英語で太陽です。
LISメモ
健康管理
最近めっちゃ寝てる
ふとんでれね〜〜
何した
授業受けて競プロ。
俺は水色になるぞ。
具体的に
大学の講義は論理回路と情報倫理についてのお勉強
競技プログラミングについては 下見て。
今日解いた問題
ABC 096 D- Five, Five Everywhere
[面白い,素数,合成数]
解説ACなのですが、感動しました。
ある数の倍数であれば、その数自身でない限り合成数担っている。
どの5個を選んでも5の倍数になるようにする。
では、5個選んで5の倍数になるような5個の組み合わせっていうのはどういう組み合わせですか?
5k , 5(k+1), 5(k+2), 5(k+3) 5(k+4)の5つの和は5の倍数だ。
{5k+1, 5(k+1)+1, 5(k+2)+1, 5(k+4)+1, 5(k+10100101)+1} この5個の和も5の倍数
つまり、5で割った余りが等しい物5つの和は5の倍数だという…
なるほど!!!!!!!!!!!!
{x1, x2, x3, x4, x5} のxiがそれぞれ5 * k + a (aが5で割った余り)という形で表されるとき x1 ~ x5 までの和は 5 * hoge + 5 * a なので5の倍数だね!!フフン
ABC092 C- 2D Plane 2N Points
[ペア作成、貪欲(的),最適な選び方]
こういう問題よくあるよね。好きだよ。好きだよ。
青より左下に赤があれば仲良くなれるよ!!(あかこーだーが謙遜して青より実力無いように振る舞っていたら俺は嫌だけどな。)
どういうペアを作るのが今後のために最適か…
左にある青色の玉を順に見ていきます。(x座標が小さい青色の玉)これを仮にK番目の玉と呼ぶことにしましょう。
そのとき、M個の赤い玉はK番目の青い玉よりもX座標が小さい(イコールもふくむ)とします。
まぁ、図示するとこんな感じです(ちなみに、実際に図示するのはめんどくさいので僕の頭の中に今図を描きました)
さて、このとき,K+1番目の青い玉を考えましょう(すなわち、K番目の青よりも右にある玉ってことです)
先程言った、K番目の青玉より左にあるM個の赤い玉は、そのM個全てがK+1番目の青玉よりも左にあるでしょうか??
はい。 あります。
つまり、K番目の青玉とペアになれる可能性があるM個の玉(この時点で,y座標については見ていないので可能性があるとしか言っていない)は、K+1番目の青玉ともペアになれる可能性があるなあ。
って考えたときに、K+1番目の玉がペアを作れるように、K番目の青玉は最適な行動をしなきゃいけない。
ってなったらどうすればいいと思いますか?
はい、そうですね、一番キッツイ赤玉を取ってあげればいいですね。
あれです、クイズ番組で10人が問題を解く。難易度は1〜10までで10個ある。って時、自分が解けるなかで一番難しい物解いてあげよう。っていうやつだよ。
まぁ、ぶっちゃけこれ説明じゃなくてテキトウに書いてるだけだから、youtube動画見たほうがイイヨ
AGC024 B- BAckfront
[操作の最小回数,数列並び替え]
最長増加部分列とか最長現象部分列とかが脳裏に浮かんで、実装してみたけどだめでした
?2?3??4??5? みたいになっている時、(この文字列は9文字)2345以外の?に操作を加えることで 1 2345 6789っていう風にすることが出来る。!!!!つまり、与えられた数列の中で、 k (k+1) (k+2) (k+m) っていう順に並んでいるモノの最大値を求めて上げればいいって。
これ自力でときたかったな〜〜〜〜
ところで最長増加部分列、2,3週間前にお勉強しました。でも、それの簡単な問題が LISメモ ぐらいしかないからにゃ〜…(あんまり自力で出来ていない)
ちなみに、最長増加部分列についてはこの方の記事がわかりやすかったです。(蟻本を読んで分からん、の後にこの方の記事を読むことで少し理解が進みました)
あとがき
美味しいお菓子食べたいな
以下は毎回記事に貼っているテンプレート
基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)