2020年 6月 5日
まえがき
1日ブログサボっちゃったね。
水曜日から今日まで、睡眠時間は10時間以上、布団にいる時間は15時間以上ではないか？みたいな日々が続いています。
原因は知りません。多分不治の病ですね。
健康管理
バグが取れないので恐らく栄養失調。
何した
具体的に
queueにpushされたpair型の要素をXとして、最初にpushしたものを{0,0}とするじゃないですか。 で、while(!queue.empty()) の中で、Xと次に追加する候補を比較しないといけないのに、{0,0}とXと次に追加する候補を比較していたため一生バグ素敵大三角形になっていました。
今日解いた問題
6月4日に解いた問題もここに書きます。
AGC031 B- Reversi
- [数列の操作,オセロ,数え上げ]
解説ACだが頭の中？？？です。 なんとなく、既に色Kが出てる時、次に色Kが出てきたら組み合わせが増える。みたいなのはソロプレイの段階で分かったんですが、うーん…。って感じです。 ただ、コツとして, 色の数列が {1,3,3,3,3,3,1}みたいになってたら、これは圧縮しちゃって{1,3,1}として取り扱っていいですね。(これは分かる) これ以上はちょっと頭パンクしちゃうのでパス。
ABC114 D- 756
- [約数の個数,数え上げ]
自力ACです。（やったね） まず、ax * by * czで表される数kについて、その数kの約数の個数は(x+1)(y+1)(z+1)ですね。
じゃぁ、約数の個数が75個って言うのはどういうことかって言うと、 75 = 3 * 5 * 5であることを考えて, (x,y,z) = (74,0,0),(24,2,0),(14,4,0),(4,4,2) の4つが考えられる…。
(14,4,0)の時を取り上げて、 k = a14 * b4 と表せるとき、kの約数の個数は75個だな〜…
このとき、aとしてかんがえられるものが何通りあるか、っていうのと、bとしてかんがえられるものが何通りあるか、って言うのをかんがえてあげれば、 a ^ 14 * b ^4 で表せる数っていうのは a * (b - 1)通りあるな。
(aとbで同じものは取り出せない。なんでかっていうと、その場合はk = a18になっちゃって、約数の個数が19個になっちゃう)
あと、これは俺が間違えたことなんだけど, a * (b - 1) と b * (a - 1)はチガウから注意しようね。
駄目だ、まとめて無いから綺麗な文章書けないのでもう終わり。
エイシング プログラミングコンテスト2019
- [幅優先探索,交互に移動]
もはやタグ付がﾃｷﾄｳなんだけど許して。
ある黒b1から白w1へ移動出来る
かつ、白w1から黒b2へ移動できて
黒b2から白w2へ移動出来るってとき。 黒b1から白w2へ移動することは出来る。
そんな感じで、なんか、b1からw1,w2,w3,w4は行ける。b2からw1は行ける。って時、
b2からw2,w3,w4には行けないよ。っていうのはありえない。みたいな感じなことを使って数え上げていく。
で、このb2からw1は行けるのに、b2からw2,w3,w4へは行けないのがありえない。っていうのはどうやって示そう。
数学の素養が虚無だからテキトウなこと言うけど、
b2からw1へ行けたってことは、w1からb1へ行くことが可能じゃん。すると,b1からw1,w2,w3,w4へ行けるんだから、一回b1を経由して上げればw2,w3,w4へ行けるってことは理解できそう。
で、幅優先探索で行ける島を見つけてあげて、島に含まれるblackとwhiteの数の積を答えに足す。っていうのをやってあげれば答えが求まる。
僕はこれに バグを埋め込んで一生泣いてた。
diverta2019 Programming Contest2 C- Seccessive Subtraction
- [数列の操作]
(天才が)考察をすると,N個の要素について、最低でも1つは+と-があって、他のものについては+にも-にも出来ると言う事が分かります。 N-1回の操作後の数字を最大化したいので、N個の要素のうち最も小さいものはﾏｲﾅｽ、最も大きいものはﾌﾟﾗｽにします。
残りの要素についてどうするかというと、値が負の要素はﾏｲﾅｽ、正の要素はプラス。というふうにしてやれば良い。
個人的にｵｵ~~!ってなった解説は、最初ある要素x,yを選んだ時、黒板に書かれる数字はx-yで、この段階でxとyは符号違いであるから、N個の要素全てに点いて+(もしくは-)にすることは出来ないというのがﾋﾞﾋﾞっときましたね。
そして、肝心な操作の順番ですが、ﾌﾟﾗｽにしたいものをa,b,c, マイナスにしたいものをd,e,fとすると f - c -> (f-c) - b -> a - (f-c-b) -> a - (f-c-b) - d -> a - (f-c-b) - d -> a - (f-c-b) - d - e = a + b + c -d -e -f って出来る（ｽｹﾞｰ)
イメージとしては、+にしたいやつは(aをのぞいて)2回 x,y のyとして選ぶことで正に戻す。みたいな感じかな。。
あとがき
一生寝てる。 さっきオムライス作って食べました
以下は毎回記事に貼っているテンプレート
基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)
