シコウノストレージ

自分自身の考えを整理するために書いています。

恋する寄生虫

三秋縋の「恋する寄生虫」を読んだ。

感想書いてないけど、この作者の本は「いたいのいたいの、とんでゆけ」に続き2作目。

 

 

簡潔に面白かったか面白くなかったかで言えば面白かった。

多少のご都合主義的な部分はあったが、個人的にそこまで気になるほどではなかったし、話の方向性は完結まで一貫性があり表現のきれいさの方が目立っていた。

ラノベ寄りともいえるが、表現の秀逸さという点はプロを感じた。

 

次に、内容に焦点を当ててこの本を一言で表すなら「終生交尾」だろう。

最初出てくるフタゴムシの話。

これがこの本の核であり、佐薙と高坂の関係そのものだと思う。

フタゴムシの終生交尾という性質を肯定も否定もせず、きれいな形で二人の人間に落とし込む。

そしてきれいな形のまま終わりを迎える。

 

「いたいのいたいの、とんでゆけ」でもそうだったが、この作者の終わりの美しさとか終わることに対するネガティブな感情を尊くポジティブに表現してるのが好き。

 

高坂が思い悩む場面で、自分は寄生虫によって恋をしているわけだから糸が目に見えないだけで操り人形と変わらない。

そこに失望する高坂がいて治療を受けることを決心する描写がある。

結果的に治療を受けないことを選択をした佐薙が最後には死を迎えないという意味で正しい選択といえるが、「自分の気持ちではなく恋をしてた」と知って治療を受ける選択をした高倉の誠実性の高さはうかがえる。

 

ただ、「最終的に自殺を迎える背景があった」から治療の選択したとも取れるので、もしあの時点で寄生虫の生態が分かっていていたのなら間違いなく治療をしないという選択をしただろうなと思えてその部分はやるせない。

 

最後の終わり方に関しては想像の余地が多分に含まれて、佐薙としては間違いなくハッピーエンドだろうけど、高坂はおそらく佐薙が自殺した後につらい気持ちを持ちながら後を絶つのだろうとは思う。

だってそれが終生交尾だから。

しかし、虫がいなければ二人ともとっくに命を絶っていたはずであるし、このような一瞬の煌めきさえなくして死を迎えていただろうから、佐薙のいうように最善とは言えずとも最悪とは言えないだろうと思う。

 

作者のあとがきからもうかがえるように、「人の価値基準は場当たり的なもので人間の価値観の倒錯はもっとも美しいバグ」この言葉に集約されると思う。

絶対的な価値観がすべて正しいわけでなく、「引き算の幸せ」おそらく「相対的な差分」そんな価値観がその人にとって一番の思い出でいい。

 

佐薙も高坂もそれぞれにとって一瞬の煌めきを持ったまま死ねたのは多分幸運なことなことでハッピーエンドと言ってもいいと思う。

精進記録

典型26

木の問題。

隣り合ってない頂点を探索するためにDFSを行い、各階層ごとにbool値を反転させて隣り合わないグループに分ける。

最初そのまま提出したがそれだとn/2よりも数が少ない可能性があるため、WA。

それを直してAC。

 

典型28

問題見ても太刀打ちできないと感じ解説へ。

2次元のimos法を使うらしい。

imos法が分からないので調べたまとめ。

ようは累積和で、2次元の場合inの場所とoutの場所を2つずつとり、縦と横で累積和をとることによって、この問題だと1×1㎡のマスのタイルに対して何枚重なっているかが分かるので掛け算などをせずに重なった各枚数ごとの面積を求めることができる。

 

abc211d

dfsで最短路を求めて、もう一度dfsで求めた最短路で行ける道のうちn頂点に行けるものの個数を計算するという方針を立てて提出したがTLE。

解説を見るとどうやらDPで求めるらしい。

 

精進記録

典型26

木の問題。

隣り合ってない頂点を探索するためにDFSを行い、各階層ごとにbool値を反転させて隣り合わないグループに分ける。

最初そのまま提出したがそれだとn/2よりも数が少ない可能性があるため、WA。

それを直してAC。

 

典型28

問題見ても太刀打ちできないと感じ解説へ。

2次元のimos法を使うらしい。

imos法が分からないので調べたまとめ。

ようは累積和で、2次元の場合inの場所とoutの場所を2つずつとり、縦と横で累積和をとることによって、この問題だと1×1㎡のマスのタイルに対して何枚重なっているかが分かるので掛け算などをせずに重なった各枚数ごとの面積を求めることができる。

 

abc211d

dfsで最短路を求めて、もう一度dfsで求めた最短路で行ける道のうちn頂点に行けるものの個数を計算するという方針を立てて提出したがTLE。

解説を見るとどうやらDPで求めるらしい。

 

昨日のABC感想戦

A問題

XORの問題。

A ^ C = B → A ^ B = Cになるのでそのまま実装してAC。

 

B問題

ソートしてスコアの2番目を表示。

最初、上位から2番目と誤読していたがすぐ気づきAC。

 

C問題

wとhについて独立して考えればよいことに少し時間がかかったが気づいた。

しかし、実装うまくできずにWA14個。

この時点で考察があっているか確信がなかったのでとりあえずD問題へ。
結局戻ってこれず、WAのまま。

→答えを確認すると解法はあっていた。

解けた問題だけに、惜しかったでは終わらせられない。

問題点として実装の汚さがあると思う。

 

自分コード

  1. int main() {
  2. int h, w, n;
  3. cin >> h >> w >> n;
  4. vector<int> a(n), b(n);
  5. rep(i, n)cin >> a[i] >> b[i];
  6. //最初の値:変更後の値
  7. map<int, int> mh, mw;
  8. vector<int> aa=a, ab=b;
  9. rep(i, n) {
  10. mh[a[i]] = a[i];
  11. mw[b[i]] = b[i];
  12. }
  13. sort(all(a));
  14. sort(all(b));
  15. int starth = 0;
  16. int startw = 0;
  17. rep(i, n) {
  18.     mh[a[i]] -= (mh[a[i]] - starth-1);
  19.     mw[b[i]] -= (mw[b[i]] - startw-1);
  20.     starth = mh[a[i]];
  21.     startw = mw[b[i]];
  22. }
  23. rep(i, n) {
  24.     cout << mh[aa[i]] << " "<< mw[ab[i]] << endl;
  25. }
  26. }

これは元の順番の配列をソートしてしまったので急遽aa,abにソート前の順番でコピーして出力の際にだけ使っている。

これ自体は、出力の順番にしか使っていないしそこまで悪くないかなとは思う。

このコードで一番良くないと思うのが17行目からのコード。

特にmh[a[i]] -= mh[a[i]]-starth-1);が一目でわかりにくい。

そしてこの部分が間違っている。

内容としては、mapのmh,mwには{最初の数、最終的な値}として格納されており、小さい順にソートした上で、値の差分つまり何も書かれていないカードの部分を消した値を計算している。

しかしながらこれだと、11,12のような場合,11はうまく通過するが12の時に最後の値がstarthが1,mh[a[i]]が1であるため1 - 1 -1 でマイナスの値になってしまい結果的には1足される結果となり計算結果がずれてしまう。

 

もう一歩踏み込むには、なぜ計算結果がずれてしまうのかを考えなくてはならない。

まず、mhとmwは一緒の元考えていいのでmhの場合だけを考える。

mhは一次元座標ではないので11,12とhが同じであっても大丈夫だが上記の式の場合、次の場所に移るようになってしまう。

 

条件としては白い部分を消すつまりは、小さい順から考えて2個以上差があるなら詰める。しかし、0個1個の場合は詰めない。この場合の0個を考えられていなかったのが今回バグらせた原因。

 

解説コード

  1. //input---------------------------------------------
  2. //--------------------------------------------------
  3. //function------------------------------------------
  4. vector<int> compress(vector<int> a) {
  5. int n = a.size();
  6. map<int, int> mp;
  7. rep(i, n) mp[a[i]] = 0;
  8. int id = 1;
  9. for (auto& p : mp) p.second = id++;
  10. rep(i, n)a[i] = mp[a[i]];
  11. return a;
  12. }
  13. //--------------------------------------------------
  14. int main() {
  15. int h, w, n;
  16. cin >> h >> w >> n;
  17. vector<int> a(n), b(n);
  18. rep(i, n)cin >> a[i] >> b[i];
  19. a = compress(a);
  20. b = compress(b);
  21. rep(i, n)cout << a[i] << " " << b[i] << endl;
  22. }

解説コードは、compress(圧縮)という座標返還をする関数を作成している。

座標圧縮というアルゴリズムを使っているらしい。

この方法の方が同じコードを2回書く手間も省けるしミスが起こりにくい。

この問題において、2個以上差があるときだけ消すわけだからmapで小さい順にソートされていて同じマスは同じ移動で考えてよいわけだからその性質を利用して、mapの小さい順にインクリメントしていくというシンプルな実装になっている。

コードも短く、明らかにこちらの実装のほうが良い。

 

D問題。

C問題をいったん放置してD問題を見たが解法が思いつきそうだったので、実装することにした。

まず見たときにシミュレーションをやることを考えた。

方針としては、直接道路でつながっているということなのでその都市をBFSで求めて、スタックに入れていく。行ける道がないのならスタックを使って戻るような実装を考えた。

しかしながら実装していくうちにbfsといえどqueueは使う必要がないことに気づき消したり、行き当たりばったりのような実装になってしまったためバグらせてしまいACできず。。

 

この方針あっているような気はするが、TLE2つとWA11個でてしまい原因も不明なので解説の方針を使う。

 

解説ではオイラーツアーというアルゴリズムを使っている。

内容を見るとDFSの探索順に到達する頂点を出力することらしい。

今回の問題ほぼそのまま使えて、一つだけ小さい順に探索するという制約があるのでグラフを一回ソートしておく。

あとは再帰関数を使って潜るときと戻るときに引数をansに加えていけばよい。

  1. //input---------------------------------------------
  2. int n;
  3. vector<vector<int>>g;
  4. vector<int> ans;
  5. //--------------------------------------------------
  6. //function------------------------------------------
  7. void dfs(int v,int p = -1) {
  8. ans.push_back(v);
  9. for (auto nex : g[v]) {
  10. if (nex == p) continue;
  11. dfs(nex,v);
  12. ans.push_back(v);
  13. }
  14. }
  15. //--------------------------------------------------
  16. int main() {
  17. cin >> n;
  18. g.resize(n);
  19. rep(i, n-1) {
  20. int a, b;
  21. cin >> a >> b;
  22. --a, --b;
  23. g[a].push_back(b);
  24. g[b].push_back(a);
  25. }
  26. rep(i, n)sort(all(g[i]));
  27. dfs(0);
  28. for (int v : ans) cout << v + 1 << " ";
  29. }

この実装個人的にはやりたいが難しい部類で再起を再帰を親の頂点の場合に終了する処理がなかなか思いつかない気がする。

個人的にはused配列を用意してtureだったらcontinueで実装してしまうと思う。

それでもできるのでそれで良いともいえるがせっかくなので掘り下げてみておこうと思う。

まず初めに、問題文でn-1本の道かつすべての都市間は行き来できるとある(=連結グラフ)なので木であるということが分かる。

つまり閉路が存在しないので進み続けるといつかは行き止まりが存在する。

隣接リストの場合次に進む場所が親しかない場合、葉ということが分かる。

そのため、現在の頂点が親しかないような場合に再帰が終了することになる。

それ表現すると、

dfs(v,p)のVは現在の頂点でpが親の頂点。

親の頂点なので最初は-1で初期化。

nex == pの上限を満たすときcontinueで行き止まりと逆向きに探索することを防ぐ。

よってきれいに探索できるというわけだ。

 

今回は木なのでそれが適用できたが、閉路が存在するような場合においては先ほどのused配列で到達判定などをするる必要がある。

グラフ【1】

グラフ問題を解くうえで理論もそうだが、まず用語とか区別の仕方が分かってないのでそれを調べてまとめることとする。

 

グラフとは何なのか|

頂点と頂点を辺で結んだもの。

頂点は形あるものでもよいし、形のないものを頂点とみなしても良い。

 

有向グラフ、無向グラフ|

辺に向きの制限があるかどうか。

あるのは有効グラフ、ないのは無効グラフ。

 

完全グラフ|

各頂点からすべて自分以外のすべての頂点に辺が伸びているもの。

無向グラフである必要はない。

 

2部グラフ|

2部グラフは隣接しない頂点集合を2つにわけることができるグラフ。

2部グラフの集合をA,Bとすると辺は必ずA-Bの関係になっている。

 

完全2部グラフ|

2部グラフであり、各Aの頂点から各Bの頂点すべてに辺があるグラフ。

A1,A2,A3があるならA1-B1,A1-B2,A1-B3,A2-B1.....となっている。

 

連結グラフ、非連結グラフ|

任意の2点間に道が存在する(直接または間接的に辺があるかどうか)場合連結グラフ。

そうでなければ非連結グラフ。

 

パス|

f:id:slwmtin:20210807180800p:plain



サイクル(閉路)|

f:id:slwmtin:20210807181213p:plain

 なお頂点の数が偶数の場合「偶閉路」、奇数の場合「奇閉路」

 

木|

閉路を含まない連結グラフ。

有向グラフなら有向木と呼ぶこともある。

有向木の場合、辺の向きが根から葉or葉から根に統一されていなければならない。

 

葉、枝|

グラフを木とみなせるので、2つ以上頂点を葉、辺を枝と呼ぶことがある。

 

根付き木|

ある頂点を根として考えたときの木

 

DAG(有向非巡回グラフ)|

閉路を持たない有向グラフ

頭バグらせることが人生の楽しみだったりする

頭バグらせるというのは言ってしまえば価値観を大幅に変化させるということ。

 

おお幅な変化といっても、単純に遠い価値観に迎合するでもいいし、それに限らず長らくの固定観念を変える時なども割と大きな労力を要するのでその場合等も含む。

 

そうやって価値観を変えるのは苦痛を感じる人もいるし、個人的にも刺激強すぎれば苦痛に感じるがそれが案外楽しみだったりもする。

 

なので意図的に感覚的に嫌なものを続けてみて慣れさせるということをやったりする。

慣れは続けられればいつか必ずきて、その感覚に慣れたときには慣れる前の感覚なんて忘れてることもある。

 

それを意識的にやっているとバグらせることの刺激自体にも段々慣れてくるし、新しい価値観を得ることができて結構楽しい。

アウトプットをもっとしていこう

最近うすうす感じていたことだが、自分はアウトプットの割合が少ない気がする。

これは結構昔からの傾向なので、最近からというわけではないが何か物事を覚える時などにトップスピードがなかなかでない状態な気がしている。

集中力のなさが原因かとも思っていたが、それよりもインプットとアウトプットのバランスの悪さがそうさせているように思える。

 

よく言われているやつだとinが3割outが7割くらいが良いらしいが、それの是非は置いておいてそれよりははるかに少ないと思う。

それに、自分としてもブログとして書き出すなど外に出すときに考える力によって、成長スピードが加速しているような気はする。

 

そんな理由でもっとアウトプットを増やしていこうと思っている。

外に出すのは頭の中で考えるよりも多少時間がかかるが、そこにある程度時間を割いても良い気がする。