2023-09-11

競プロまだやってる

飽きっぽい俺がまだ熱を持ってやれていることに自分が一番驚いている。
もうすぐrecomendationの灰色が全部埋まって、茶色に突入するレベル。
知識さえ身に着けられれば緑まではいけると思うんだが、グラフ、DP、、マジで手強い。
そして本業の方が時間泥棒すぎて全然勉強できねえ。あ、勉強って競プロのほうね。

ん？総合内科専門医試験？
なんでしたっけそれ。

2023-08-08

ラムダ式の「キャプチャの&」と「パラメータの&」は全然違う

(2024/1/9　スーパー意味不明な記載になっていたので書き直し)

ラムダ式が全然わからなくて、dfs書いてて一生エラー吐きまくってたんだけど、やっと解決したから記録しておく。
[&]と(int &x)はしっかり区別しなきゃだめ。

まずは例示から。

#include <bits/stdc++.h>
using namespace std;
int main()
{
   int a=1;
   int b=2;
   int c=3;

   auto f=[](int x, int y, int z){
        x*=3;
        y*=3;
        z*=3;
   };

   f(a,b,c);

    cout<<a<<b<<c<<endl;
}

この場合出力されるのは123なのか369なのかってことだけど、

です。
キャプチャの&：[&]は、外にある変数を参照で使えるという意味。
パラメータの&：(int &x)は引数として入力された変数を参照で使うという意味。

上のコードはパラメータに&がついてないからfはa,b,cをコピーで渡しているので、値は更新されない。
参照で渡すときはパラメータに&をつけて

#include <bits/stdc++.h>
using namespace std;
int main()
{
   int a=1;
   int b=2;
   int c=3;

   auto f=[](int &x, int &y, int &z){
        x*=3;
        y*=3;
        z*=3;
   };

   f(a,b,c);
    
    cout<<a<<b<<c<<endl;
}

にする。
これで答えは

になる。

キャプチャの&をつかうならば、

#include <bits/stdc++.h>
using namespace std;
int main()
{
   int a=1;
   int b=2;
   int c=3;

   auto f=[&](){
        a*=3;
        b*=3;
        c*=3;
   };

   f();
    
    cout<<a<<b<<c<<endl;
}

これで答えは

になる。

きっちり区別しながらコードを書くようにする。

2023-07-16

やっと茶色になった

Atcoderやっと茶色になったわ。
今日のABC、DE手も足もでんかった。
緑ぐらいまでは行ける気はするけど、そこからは厳しそうかな。。
ワンチャン水色ぐらいになれんかな。。。

まいるすとーん
atcoder problems 500AC　ほぼ灰色問題

連想配列を使って計算量を減らす対応ができる
わかるアルゴリズムはDFSとBFSのすごいかんたんなやつだけ。dpも１次元ならなんとか。
ソラでかけるアルゴリズムはユークリッドの互除法と素数判定ぐらい。DFSとBFSは本見ながらじゃなきゃ無理。
ラムダ式は自力じゃかけない。
lower_boundを扱えることが二分探索できるということなのかはわからんが、前者はできる。

2023-07-02

Twitter見れなくてABC終わったあとの一人感想戦ができない

もうタイトル通りなんだけど。

Twitterのアカウントもってないんで、twitterの競プロコメント見ることができなくなってしまった。
ただ今からTwitterやるってのものなー。

昨日のABC308は3完。
Cってsort関数の第三引数に比較関数いれるってのが正解みたいなんだけど、long doubleで無理やり通しちゃった。
浮動小数点本当に苦手。

2023-06-18

atcoderまだやってます

ABC306、ウンウン考えて残り30秒でやっとD通したのにunratedだったわ。
3,4回unrated食らって流石に萎えてるわ～。
でも初めて本番でD問題通せたので嬉しかった。

とりあえずDFSとかDPぐらいは勉強するかあ。。

2023-03-21

AtCoder茶色の壁は結構高いぞ

AtCoderのランク別色ってのは赤色から始まって、赤、橙、黄、青、水、緑、茶、灰と８段階に分かれてて、茶色ってのは下から２番めなんだけど、なんもしらんと茶色なんてゲームでいうブロンズみたいな初心者ランク帯の様に感じる。

では茶色が時間かけて考えれば解るとされる茶diff問題がこちら。
atcoder.jp

ようは９×９のマス目があって、その複数のマス目に#で表されるコマがおいてある。
そのコマたちから４つを選んで、正方形となりえるのは何個か？という問題だ。

以下ネタバレ全開なので、問題解きたい人はここでバック。

方針としては♯の点から2点を取り、その2点から作れる正方形の残り2点を求める。
新たに求めた残り2点が、①そこにコマがあるか、②マス目に入っているか、で判定する。

このときに正方形の一意性を保つ（同じ正方形を何回もカウントしない）ために、#の2点 $d_1(i,j)$ , $d_2(k,l)$ としたときに $d_2$ が $d_1$ の"右上"（真上はOK）というふうに4重for文の設定で $k=i$ 、 $l=j+1$ 開始と限定して、 $\vec{d_1d_2} = (k-i,l-j)$ を回転行列 $\begin{pmatrix}cos90° &-sin90° \\sin90° &cos90° \end{pmatrix}$ で回転させて、そのベクトルと $\vec{Od_2}$ を足して $d_3$ を反時計向きに取る、という作業が必要。