シコウノストレージ

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

今年の振り返りと来年へ

今年は正直に言えば、あまり成長感というものは感じられない年だった。

というもの競プロに力を注いだけれども、必要最低限の能力が欠如していて具体的に何をやればいいのかというのを模索しながら勉強していたというのが主な理由。

最近それをやっと気づいたというか、回数をこなすことでその判断ができるくらいにはなってきたので来年こそは飛躍していけたらと思っている。

 

ただ、目に見える成長感というものは感じられなかったけれども、土台作りという意味で一番大変な部分、畑を耕す段階としては悪くなかったとも思う。

競プロ自体はプログラミング能力のすべてをカバーしているわけではないが、去年の今と比べたら、実装力という面から見ればプログラミングのスキルも向上している。

 

やっと軌道に乗ってくるかなという感覚はある。

だからこそ、来年は勝負の年という感覚。

今年は種まきと畑の整備両方をやってしまったせいで少し迷走した感はあるものの、ようやく畑の整備が最低ラインに乗ってくる感覚はある。

今年耕した畑を有効活用できなければ、また畑を耕すということをやらなければならなくなる。

そうならないためにも、しっかりと軌道に乗せて一定の壁は超えたい。(目標は水色)

 

また、最近気づいたこととして畑の耕し方にもレベル感があるように思える。

種まきの段階から同じように育ててきても、畑の状態(環境)が違えば同じように育たないように、土台(基礎)をどれだけ解像度高く理解できているかという視点はとても重要と思った。

 

それに気づいたのは最近ではあるのでまだまだ改善できる部分はある。

ただ一度気づいてしまえば、水を上げている段階でもおそらく畑の耕し方が悪いのだろうと気づけるので、常に畑の整備というのはちゃんとしていきたいと思う。

 

畑の耕し方を例に出していたが、要は物事を見る目の解像度の問題のことである。

認知といってもいいだろうし(?)界隈では言い換えなんて言われたりもしているが、要は物事の本質を見極めたうえで、いろんな視点で見れるかだったりそこに装飾したりできるかということである。

 

いろんな視点で見れるかというのは、よく言われているので割愛するが、そこに装飾できるかというのも本当に重要だと思っている。

これが応用力につながってくるのだろうという認識はある。

装飾できるかというのは普遍的に使えるように抽象化したものを、具体にあてはめる際に最適化するということでもある。

これは、もちろん基礎をちゃんと理解していないといけないので一つ上のランク。

ただ、来年はここまで行きたいと思っている。

自分に合ったやり方は大事だが視野狭窄になってはならないという話

自分に合ったやり方を貫くというのは大事なことで万人にとってのベストアンサーなど存在しない。

つまり自分の正解が他人の正解ではないし、その逆もまた然り。

とそういう考えはとても大事だが、同時に視野狭窄にはなってないか振り返るというのもまたやらねばならない。

 

それは自分に合ったやり方を主体的に選ぶということででもある。

試した結果で選ばず、俺にはこのやり方があっていると消極的な選択をし続けてはならない。

 

これは、穴掘りで例えるが自分の手になじんだスコップで掘っていくというやり方があっていると思っていても実際は明らかにブルドーザーを使って掘ったほうが速い。

 

それを試して運転できないまたは習得コストを考えて、スコップを選択をするというのならばそれは主体的な選択だが、全く見向きもせず俺はこのやり方があっているという信念を持っていてもより良い結果にはつながらない。

 

自分に合ったやり方を見つけたからといってこれからも続く保証はどこにもないし、そもそももっとあっているやり方がある可能性だって全然ある。

いつでもそれを探すという主体的な姿勢が大事だが、意識しないと忘れていく部分でもあるので注意したい。

ちょっと精神論的な話

タイトルの通り。

今日は全然やる気がわかないので自分の考えを外に出しておこうということで。

 

自分は少々正解を求めすぎている時がある。

正解がないとわかっているからこそ、普段は行き過ぎることは少ない。

だが、同時に探すことこそ大事だとも思っている。

正解はないけど探すことに価値がある。

だから、探し続けている最中にそのことを忘れてしまう。

もちろん、知っているので一歩立ち止まれば思い出すことはできるが。

 

ここで、正解がないというのはそのままの意味では少々正確性に欠けるのでちょっと説明する。

"何かに対して"は必ず正解がある。

例えばダイエットをするにも食べないor運動するなどをして摂取カロリーを消費カロリーが一定以上上回ればよいというのは正解。

 

つまり、上の条件が満たされていれば何をやっても正解ということになる。

しかし、なるべく早く痩せたいというのならば、よりよい解が存在するし場合によっては不正解になる場合もある。

瘦せるのに10年かかる方法だったら良いとは言えないだろうし、期間が明確ではないが” なるべく早くなのでもっと早い方法をネット検索するなりで見つけて不正解にしてしまうことだって可能だろう。

 

このように、正解というのは考慮する変数が増えれば増えるほど複雑化ししまうので、そこにこだわって探すことも大事だが、あまりに複雑な場合変数に優先順位をつけて減らしてしまっても良いということだ。

 

難しいのがどのくらいのバランスで考えればよいかという部分。

例えば極端な例だと先ほどの10年ダイエットを愚直に実行してしまうよりはもうちょっと調べて考えたほうが良いだろうし、逆に調べすぎて真実が分からなくなって時間を消費→結局たっせできないなら元も子もなくなってしまう。

 

ここが考えるほど難しい。

そもそも優先順位を定義するのが難しい。

個人的にだが、優先順位なんて決めなくても良いとすら思うくらいに。

例えば、ダイエットの例で行くとダイエットをするのが目標で、次になるべく早く痩せたいがきて、なるべく楽な方法で、短時間で、安くて、人目につかないところで来て、人におすすめ出来て..etc

と希望は尽きないとは思うが、後半になってくればくるほどプラスαの差異が小さくなってくるので優先順位をつけるのが難しくなってくる。

なら、許容できるところに境界線を引いてそこを達成できればなんでもいいじゃないと考えるのを個人的にはやりたいと考えている。

個人的にはなるべく楽な方法で~以降はさして重要ではないので以下を切る。

なので、つらくてもやる。

もし、続かないのであれば一段境界線を落とせば良い。

そうやって許容度を考え、全部の理想的な世界=聖杯を探そうとするのではなく、必要なものだけを満たすということを意識するだけでよい。

こうすればよりシンプルになるし、かといって許容度を超えるようなことにはならないだろうと考える。

 

ただ、何度も言うように欲張ってこのラインを下げすぎるのは厳禁。

かといって本当の高みを目指すならここを極限まで下げる必要があるのだろうなとも思っている(これは想像でしかないが)。

ひとまず、自分はこう考えている。

今日のキョウプロ

122C

f:id:slwmtin:20210911113658p:plain

解法としては累積和でOK。

ただし少し工夫が必要で、ACの状態が確定した時点で累積和する。

確定した状態で累積和することで、普通の累積和と同じように扱うことができる。

 

今日は自分の苦手分野を伸ばしていくようにしたいので問題を解くことはあまりせず、理解度を上げていきたい分野をより詳しく学習することにする。

目に見えるだけでも不完全に理解している分野が多くある。

 

・累積和

・imos法

・グラフ

・dp

まだ完全ではないがサラッと思いついたのを書くだけでもこれだけある。

何となくどれも何となく問題解いたことがあり、基本中の基本問題くらいなら解けるものだが応用が問われた時や、実装の重い問題が来た時に大体バグらせて解けない。

バグらせるのは実装力のなさ、デバッグ力のなさでもあるので、その辺の部分も考えていきたい。

以下、学習したことを自分でまとめる。

 

累積和

まず、現状の理解

累積和自体は単に配列の一番左からi番目までの総和を記録しているに過ぎない。

だが、これを利用することで元のデータではできない便利なことが行える。

それは、L番目からR番目の総和をO(1)で取り出すことができるという点。

これを元の配列でやろうとするとO(N)かかり、クエリ処理などをする場合O(NQ)かかってしまう。

累積和の場合、一度前計算O(N)を行えばあとはR-Lで求めることができる。

 

累積和の難しいのがそもそもどういう仕組みなのかというのと+-1(開、閉区間)の理解。

それは、L番目からR番目の意味を考える必要がある。

L番目からR番目ということは配列の数で言えば、R-L+1個である。

なぜなら、L番目もR番目も"含まれる"から。

逆にL番目を含まず、R番目を含むような場合はR-Lで良い。

 

整理すると

-LならばL番目までは引かれる、つまりL番目は答えに含まれない。

-(L-1)ならばLの1個前まで引かれる、つまりL番目は答えに含まれる。

 

コーナーケースを考える

もしL番目からR番目の総和を求めよ

L=0,R=max

だった場合、Lを含むはずなので-1を求めたいが配列外参照になってしまう。

 

一つはどうせLとRは1-indexのことが多いので、0番目に0を置いてしまう。

そうすれば同じ処理で完結できる。

もう一つは、0だけ例外処理を行ってRの値を出力するという方法もある。

どちらの方が良いかは、個人的には前者でやったほうがバグらせにくいのではないかと思うのでなるべく0インデックスでやりたい。

 

上記のC問題も、どこで累積してどこが引かれるのかが分かっていればすぐ解けたのではないかと思う。

 

二次元累積和は軽く調べてみたが微妙に理解できてないので後回し。

 

imos法

考え方としては、累積和に近くて前処理してそれを足し引きしてO(1)で求めようみたいな部分は一緒。

簡潔に言えば累積和のパワーアップバージョンみたいなイメージで簡単な問題では、ある店に客がN時からM時まで滞在していて、L時~R時の間に何人いるかみたいな問題の時に入ってきた時間と出る時間を加味して、累積和を求めることでL時からR時に何人いるか求められる。

つまり入ってきたときに+1,出るときに-1して累積和をすればよい。

これも二次元以降はまだ理解してないので後日。

今日のキョウプロ

198D

問題要約

文字列S1,S2,S3の三つが与えられるので、各文字列に対応する数字N1,N2,N3が存在するかを判定しなさい。

 

条件

1:対応する文字列の数字と同じ桁数

2:S1+S2=S3

3:各文字列に同じ文字が含まれる場合のみ同じ数字でなければならない

 

考察

1と2の条件から、0~9までの数字をどの組み合わせにすればよいかという問題に言い換えることができる。

これは最大でも10!通りにしかならないのでTLEにはならない。

 

気を付けること

考察はそれほど難しくはないが、問題は実装のほうでうまく書かないとバグらせて時間がかかってしまうので効率の良い書き方を模索したい。

まず、バグらせそうな部分を列挙する。

1:同じ文字に対しての処理をどうするか

2:先頭が0の場合のコーナーケースに気を付ける

3:気持ち的にはfor文1回で3つの文字列を埋めたい

 

2は気づいていれば問題ないとして、1,3をどう処理するかがちょっとめんどくさい。

同じ文字があるかどうかの判定はmapでもsetでも問題ないが、後で使うときに何文字目の何番目かの情報を持っていないといけなくてそれがめんどくさい。

 

そのため、3のお気持ちと合わせて最初に3つの文字を1列の配列に格納すればどちらの問題も解決。

まぁその処理も少し難しくて,i番目の文字列のj番目というような二次元配列にする。

その配列に一列にした時の配列mのインデックスを入れる。

mには親の番号を入れる(UnionFIndの根を更新するやつみたいな)

などやろうと思えばできないわけではないが、バグらせやすく実装にも時間がかかるため、あまり効率的なやり方ではない。

 

解説のやり方

文字列3とも端っこからmapで重なりを外して、当然昇順ソートになるのでソートされた順番をstring(配列でも可)に保存しておく

ソートされたすべての文字列に対して、0~9の順列を試していく。

これはS1[0]からS3[max]がソートされた文字列の何番目かの情報を取得してきてそれに当てはまる番号を文字列として代入。

最後にS1+S2 = S3の実装の判定をして終わり。

 

189D

問題

文字列SがN個与えられるのでS[i]がANDならAND演算、ORならOR演算をX[i-1]に対して行いY[n]がTrueの数を出力せよ。

ただし

x[0]はTrueまたはFlase

y[0]はx[0]

素数はx,yともにn+1

 

解けなかったので解説見てAC

以下解説

これはi個目にTrue、Falseだった時のTrueの数とFlaseの数を配列に記録しておくDPで解く。

AND は 前回True、今回TのみTrue。

dp[0][i]・・・i番目の時のTrueの数

dp[1][i]・・・i番目の時のFalseの数

ORは前回OR,今回ORのみORの性質を使い

f:id:slwmtin:20210907173230p:plain

 

182D

問題

数列A1~ANが与えられ座標0にいるロボットが,A1,A1+A2,A1+A2+A3.....A1+....ANまで進むときの座標の最大値を求めよ。(Aiは負の数になることもある)

 

考察

負の数になる可能性もあるので、累積和を使えば距離を求めることはできるが最大値を求めることはできない。

また、動く順番が決まっているのでソートはできない。

かといって全探索をしていては間に合わない。

なので、i番目に進む距離の総和とi番目までに進める距離の最大値を記録しておき、N回シミュレートして最大値を算出しておけばよいと考えた。

 

結果それは正解でAC

f:id:slwmtin:20210907230905p:plain

 

今日のキョウプロ

217のD

長さLメートルの直線状の木材があり、Q個のクエリが与えられるのでクエリに応じて地点Xを切るか、地点Xが含まれている木材の長さを出力せよという問題。

 

昨日考えていた解法。

まず、クエリが最大2*10^5個与えられるので残りは10^3くらいしか計算することができない。

L制約が大きいため配列を用意して切った場所を記録していくのは無理。

次にグループに分けるということでUnionFindを考えたがこれも制約により却下。

(実際は圧縮してやる方法もあるらしいのでこの後記述。)

最後にXの位置を記録しておき、その位置を二分探索して求められれば,right-leftで答えが求まるだろうと考えた。

二分探索自体の計算量はO(logN)なので、最大でも2*10^5なのでO(LlogL)になり間に合う。

しかし、これには一つ問題点があってソートがO(NlogN)なためそれでは間に合わない。

setを使ってみたりいろいろ考えたが結局この部分の計算量が減らせずに解けず。

 

答え

set+lower_bound,upper_boundでいける。

setで実装も考えたがsetだと二分探索で求めたインデックスにアクセスできないようなので断念していたがX以上の最小値を求めるloewr_bound,X以下の最大値を求めるupper_boundを使えば同じことが可能。

 

せっかくなので、lower_bound,upper_boundの中身についてみていく。

まず、set.lower_bound(x)の仕組みについて考えていく。

そもそも、setがインデックス指定でアクセスできないのでどうやっているのか。

まずは、setの仕組みについて知っておく必要がある。

https://cpprefjp.github.io/reference/set/set.html

setは連想コンテナの一種で、要素自身がキーになると書かれている。

要するにインデックスでアクセスはできず、要素でアクセスするということ。

これはfind(x)で行える。

このインデックスでアクセスできないというのは、コンテナの種類によってできるものとできないものがある。

Forward Iterator, Bidirectional Iterator, RandomAcccess Iteratorの3種類あり、それぞれ++itだけできる、++it,--itだけできる、++it, --it, it+=3ができるようになっている。

setはBidirectional IteratorでありBegin()+3みたいなことができないためインデックスにアクセスできない。

これがVectorであればできる。

詳しくは下記にて

https://rinatz.github.io/cpp-book/ch03-08-iterators/

 

上記で示したようにランダムアクセスで、二分探索で求めたLとRの差をsetで求めることはできない。

lower_boundの実装には二種類のやり方があって、lower_bound(set.begin(),set.end(),x)とset.lower_bound(x)では計算量がO(N)とO(logN)で大きく変わってくる。

 

前者はxの場所を求めるのに前と後ろからひとつづつずらしていくので線形時間がかかってしまう。

実装としては以下と同じ

f:id:slwmtin:20210905173911p:plain

これでも答えは求まるが、O(N)かかってしまうので今回のD問題だと,最大O(Q^2)の計算が必要になりTLE。

 

後者のやり方は、二分探索してやるのだが実装方法理解中()

後者のやり方を使うとO(QlogQ)になり、D問題がTLEにならずに通すことができる。

C++はset::upper_bound,set::lower_boundを使うことができるので簡単に実装可能。

 

f:id:slwmtin:20210905221123p:plain

 

217E

問題

クエリが個与えられ、列Aに対して以下の操作いずれかを行う。

1:Aの最後尾にxを追加

2:Aの先頭を出力

3:Aを昇順にソート

 

これも、本番中Priority_queueとqueueをうまく使って管理するのだろうという推察は行えたが、計算量の見積もりを誤ってしてしまっていた。

クエリが1ならqueueにpush、2の場合pryority_queueが空でなければ先頭を取得、削除空であればqueueの先頭を取得、削除する,3の場合はqueueに入れられている数をpriority_queueに入れる。

この際に,1.2はO(1)なので大丈夫だが、3でpriority_queueに移す際O(Q)かかってしまうのでないかと考えてしまい実装できなかった。

 

よくよく考えてみると、3を最後に1回だけ行う場合O(Q)かかってしまうが、それ以外は1,2だけということが保証できるのでO(Q^2)にはならない。

逆に頻繁に行う場合、1回ごとにpushする数は少なくQ回目の操作で3を行うなら全体でQ回しかプッシュを行わない。

つまり、どんなクエリが来ても全体でQ回より多くのpushは行われないということが言える。

解説によると、これの計算量を求め方を償却解析と呼ぶらしい。

 

今日のキョウプロ

216D

2N個のボールがあり、各色で塗られたボールはちょうど2個ずつ存在する。

ボールがM本の筒にk個入れられており、色はa[i][j]。

全ての筒の先頭を比べて同じ色なら取り出すことができる。

すべてのボールを取り出すことができるかという問題。

 

ボールがちょうど2つずつ存在するというのがポイントで、筒に2個同じ色があればそれをとればよいので最良の選択肢は存在しない(貪欲に取っていく)。

計算量が問題になってきて、M個の筒を比べる必要があるので必ずO(M)以上は必要。

配列を使えばとりあえずO(M^2)にはならなくて済むが、それをN回やる必要があるのでO(NM)になってしまう。

しかし、よくよく考えてみると2個以上同じ色のボールがないのだから、筒からとったボールをpushした時点で、pushしたボールの色以外の色が2個揃うということはあり得ないし、ボールの数が3個以上になることもあり得ない。

なので、pushした際に2個になったかどうか判定すればO(N+M)まで縮めることができる。

なお、実装が重たいので変数はしっかりわかりやすい名前にしたほうが良い。

 

216E

N個のアトラクションがあって、i個目のアトラクションの楽しさをA[i]とし、アトラクションを1回遊ぶごとに楽しさは1減少していく。

K回乗るときの楽しさの和の最大値はいくつかという問題。

これは、i番目にどれ乗るかというのが重要な問題で、現在の楽しさの大きいアトラクションから順に乗っていけばよいので貪欲法の問題。

降順にソートした上でA[i]からA[i+1]番目の差は、A[i]番目が一番大きい時に乗れる回数で、以降iが増えるにつれて、i+1個のアトラクションが最大値になる。

それを利用して、等差数列の計算をすれば答えがでる。

なお、i+1番目すべてをとるとK回を超えてしまうときは(i+1)個をとれるだけ取って残りを加算する処理が必要。