2020年 6月 2日
まえがき
今日は我が家の次男の誕生日です。(マジ)
お誕生日おめでとうございます。
((ありがとうございます))
突然ですが皆さん、幸せになりたくないですか?
幸せに成田空港ですね。
健康管理
何した
人と話したりゲームしたりした。
おれ、FPSの撃ち合いつええや。
具体的に
ApeX
今日解いた問題
AGC 032 B- Balanced Neigbors
[グラフ,グラフの構築]
解けなかったけど、なんかグラフ関連の問題なんてまだ累計50問も解いてないだろうし、そもそも考える方法が分かっていないみたいな節ある。
ただ、今回の問題だと完全グラフをまず構築してみる。とかそういう物を頂いたので収穫はありかと思われます!!!
完全グラフ(頂点i,j(i != j) の2頂点について、どのi,jの組み合わせも辺がある)を考えて、その時の各頂点の隣接している頂点の和を見てみる((1~Nの和) - (見ている頂点番号)) 。 そこから考えていくととても良い!! へーかっけえ おれもこんな問題が解ける天才になりてえな
ABC097 D- Equals
[UnionFind, 連結,好きな回数操作]
a <-> b <-> cって感じでaとbの入れ替え、bとcの入れ替えが出来るなら、abcの順列(abc, acb, bac, bca, cab, cba)はどれでも作ることが出来る。
つまり、(1 <= k <= n) の k が最初入っていた場所と、kが本来ある場所が関節的にでも繋がっていればkは目的の場所へ移動することが出来る。
自力AC,やったぜ。
連結なら全部目的の場所に行ける、っていうのは、なんかまぁ、バブルソートでどんな数列でも昇順に出来るし、見たいなノリで考えるとタシカニな〜みたいなうっすらとした感覚がある。
(この、swap操作って、バブルソートみたいなもんじゃね(Sirankedo)
M-SOLUTIONS プロコンオープン D- Maximum Sum of Minimum
葉には一番小さい要素を入れる。というふうにしてみたのですが駄目でした。解説ACでぷ。 深さ優先探索を書いてみようと思ったらバグ梅小宮で解けなかったのでおとなしく幅優先探索を。
この問題名でググると他の方の解説記事あって、それとても良いと思ったから俺の記事なんか読むよりそっち見てみて。
c1 >= c2 >= ... >= cn とすると、ci( 1 <= i <= n) は最大でも(i-1)回しか足せない。
ってことが分かるので、 可能かどうかは分からないが、最大でも c2+...+cn が答え。(まぁ、可能)
どっかを木の根として、根から幅優先探索でも深さ優先探索でも良いが、Cの大きいものから入れて行くと良いとのこと。
ちなみに解説の森が云々っていうのはわからんかった(元気もりもり森鴎外なら知ってる)
CODE FESTIVAL 2017 Final
[時計,円,場合分け,実装重い,bit全探索(的な)]
s = 0 〜12としたときに、達成出来るかで全探索しようと思ってpriority_queueを使って実装したのですが9WA出して諦めました。(なんだろう、こういう時原因を突き詰めるまでやったほうが良いとは思うが体力が)
そもそもN=50を見た段階で「あ〜、250は全探索出来ねえなあ」って思っちゃったのです。 その後、Di=Dj=Dk(i!=j!=k)がでてきたらs=0だな。っていういうのも分かったけど、まさかこんな実装がめんどくさい問題が出るとは思わなくて;;(甘えるな)
はい、ごめんなさい。
まぁ、とりあえずやることは、Diが与えられた時、高橋君がいる地域を0時として、i番目の人のとしはDi時か(24-Di)時なので、どっちかで全探索ってことですね。なるほどね。(Di = Dj (i!=j)となるi,jの組が存在するなら、Di時も24-Di時もいるので場合分けは発生しないので bit全探索は211か) これいつかまたやらなきゃなって感じがするけど、一度解いた問題2度と復習しなくない?
あとがき
普段から何かを考えているのに、いざ自分の考えを聞かれるとうまく話せないの悲しくなっちゃいますね。
話してる途中で何について話してるのかわからなくなったり。 順序立てて話すの無理。 だからブログも書きなぐってる
ああああああああああああああああああああ
ちなみに今日(6/3は3:00に寝て9:00に起きてしまったので6/2の分の日記を6/3の10:00に書いてます)
以下は毎回記事に貼っているテンプレート
基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)