2020年 5月 29日
まえがき
今日は5月29日です。 つまり、...?
健康管理
健康だと思われます。 別にあんたのために健康になってるわけじゃないんだから…ッ!!
何した
応用数学、フランス語,離散数学を消化しました。 競プロもしてるよ!!!
具体的に
大学の授業を受けるという作業を19:30まで行っていました(ツカレタ)
それから2hくらいゲームして、仮眠とって0:30ぐらいに起きて今に至る〜〜〜〜〜
競技プログラミングはおとなしくRecommendationsを解くようにしました。
ちなみに僕が競プロのやる気だいぶなくなった原因は、Recommendations消化で解ける問題が無くなったことに苛ついてやる気が無くなってました。 また、解いた問題ちゃんと(ちゃんと??) 2☆の解いた問題たちに書いていくようにしようと思うニャン!(わん!)
今日解いた問題
ABC166 E- This Message Eill Self-Destruct in 5s
[連想配列,式変形]
・2人の持つ番号の差の絶対値が、2人の身長の和に等しい。
そのような(i,j)(i != j) の組を求めよ。という問題
つまり $a[i] + a[j] = |i-j|$ を満たすi,jの組を求める。
組み合わせを数えるから、(i,j)と(j,i)は同じ物として考える。
j > i となるような組だけ求めればいい。
先程の式を変形すると$a[j] + j = i - a[i]$となる。(iとjに着目して左辺と右辺に分ける)
つまり、各jに対して、a[j] + j が i - a[i] となるものを数えてあげればよくて、これを数える為にi < j となるiを全部見ることは愚かなので、連想配列に格納することで、a[j] + j = i - a[i] を満たすiをMAP[a[j] + j] を見るだけで数えられる!(やった〜!)
ABC070 D- Transit Tree Path
[木、DFS,深さ優先探索]
まぁ、深さでも幅優先探索でもどっちでもいいとは思うけど(知らん)
とりあえず求めるのは、Kが固定サれているっていうので、Kから各頂点への距離を最初に全部調べて上げればいい。 (与えられるグラフは木なので、Kから各頂点への距離はただ1つに定まる)
後はQ回のクエリで,1と8が与えられたら、1からKへの距離+Kから8への距離を答えとして出力する。
この問題、最近のABCで出たらdiffはどんなもんだろう…2017年8月の問題で、diffiが1190だけど、今でたら1050ぐらいまで下がるのかな?それとも茶パフォぐらいまで落ちるのかな?
個人的には深さ優先探索は書くのが苦手だから4桁diffあるような気がするけど...
ARC062 / ABC046 D- AtCodeerくんと変なじゃんけん
[貪欲??]
これは何でしょうか…?
TopCodeer君がpを出した後、AtCoDeer君がpかgかをとりあえず考えてみた。
p-gで負けの時、ポイントは-1, その後1点にするためには2回勝たないと行けない…
(だからソレがどうした??)みたいなよくわからないことを考えてみた結果、パーを出せるときはパーを出しておけ。みたいな考えになってとりあえず提出してみたラACした。
う〜ん、1手目は絶対gだから、そこから考察してみると見えたりするのかな??
今AtCoDeer君がpを一回だ出せる状態で、TopCoDeer君の手はgg/gp/pg/ppを全部考えてみる。
gg -> gg(0) , gp(+1) , pg(+1), pp(+2,不可能)
gp -> gg(-1), gp(+-0), pg(+-0), pp(+1, 不可能)
pg -> gg(-1), gp(+-0), pg(+-0), pp(+1, 不可能)
pp -> gg(-2), gp(-1), pg(-1), pp(+-0, 不可能)
まあやっぱりよくわかんないけど、なんとなくパーを出せるときはパー度しておいたほうが良さそうってことが感じ取れます。じゃあそうしよう!!
string s; cin >> s; int ans = 0; rep(i,s.size()){ if(i % 2 == 0){ if(s[i] == 'p') { ans --; } } else { if(s[i] == 'g'){ ans ++; } } } cout << ans << endl;
ACしちゃった、ってことで解説さんの証明見ましょうね
解説見ました。天才かよ・・・・・・・・・・・・・・・・・・・・・・・!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
一回全部グー出したとして、どこをPに変えるかを考える…すげええ!!!!!!!!!
あとがき
今日なんか面白いこと会ったかな…???
あ、22:30~の仮眠では、サーティーワンの夢を見ました。 そこで一生何買うか決めれずにウロウロしている夢です。 そのサーティーワンにはアイスクリームのみならず、クレープも自分で作れる、みたいなよくわからない仕様でした!サーティーワンアイスクリームが食べたい!!!!!!!!!!!!!
明日はなにする?
明日は土曜日なので大学の授業はない!、課題のストックもない!!ということで、嬉しい日ですね(えへへ)
大学の予習復習をするつもりは今の所ありません。
そのため、毎週土曜日に行っている一週間の整理と競技プログラミングを行っていきたいとおおもいますぅぅう(にゃん)
後、夜はコンテストに出ようね。
以下は毎回記事に貼っているテンプレート
基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)