草体にぼ日記

だらだらと

螺旋本/AOJ本 partitionとquickSort

こんにちは。
螺旋本を勉強していく上で、コードを理解するためにコードを画像にして書き込みしていって学ぶっていう方法が僕の中で流行っているので、他人に分かりやすいように加工なんてことはしていないんですけど貼っていこうと思います。

もしかしたら螺旋本勉強難民がこのブログを読みに来ることがあるかもしれないので一言。
これ、僕が螺旋本を勉強する際のただのメモっていうか…みたいな感じなものなのであまり期待しないでください。


一応検索がしやすいようにAOJ上での問題の名前をタイトルにしていきます
f:id:niboshi_bisyoujo:20191022024438j:plain
まずはpartitionです。
こちらは"一回だけ"一番右のものを選んでそれより左に小さいの、右に大きいのを置いていくから割と分かる

でも実装できるかって言われたら無理^^


f:id:niboshi_bisyoujo:20191022024505j:plainf:id:niboshi_bisyoujo:20191022024511j:plainf:id:niboshi_bisyoujo:20191022024516j:plain
はい次、quickSort
こちらはpartitionしまくる。
pointは、分割する際に使った番兵の位置は正しくなっているので、次の分割には関与しない。
・今使っていた番兵の要素の位置がq,であるとき、次の分割統治はそれより前とそれよりあとをやればいいので引数は q-1 と q+1 が出てきている。

(螺旋本をそのまま写真で撮ってのっけてるわけじゃなくて自分で書いたコードだからブログの内容は別に問題ないよね?)

もしも将来僕が将来強くなったら、螺旋本の解説の解説みたいなことしてるかもしれません…(ホンマか??)

ぶっちゃけ螺旋本は蟻本より簡単だ~なんて言われていますが、そんなことないよね^^
どういう人に対して簡単だって言ってるんだろう。
アルゴリズムとデータ構造を一度学んだ人??


ってかこれさ、画像でかすぎて気持ち悪くね?
俺的には小さく画像を配置しておいて、押したら拡大して見える。なり、押したら別タブで開く。って感じにしたいんだけど…

でもブログに時間かけるのめんどっちいので不格好だけどとりあえずはほっておきます。

別に毎日更新する義務はないんですけどね

いや~~ブログ更新忘れてました。ブログ用のメモは書いていたんですけどね
ブログ用のメモからとりあえず一昨日(土曜日)の分のブログを少し短めにですが。

昨日(10月19日)、17時ごろに起きて、友人のVScodeeのターミナルが使えない問題を解決しようとしたけど、できませんでした。
それからすき家に行って風呂に入ったらもう19時半とかでした。

コンテスト始まる始まる始まる始まる始まる始まる始まる始まる始まる始まる。
緊張した
緊張する
失敗したら茶色に落ちるぞ。おちたくない!おちたくない!おちたくない!おちたくない!おちたくない!おちたくない!おちたくない!おちたくない!おちたくない!おちたくない!

おちませんでした。
良かった。
Cまでをかなりの鈍足で解いてしまい泣きそうになった。

ちなみにですが、れーとは100弱上がりました。嬉しいです。
螺旋本をどんどんやって緑、さらには水色も目指していきたいですね。
一応これでも努力の成果は表れていると思っています。

実質的なプログラマーの期間は4か月くらいでしょうか?

本日分(日曜日)
多分5時間くらいの睡眠を一度と
1、2時間程度の睡眠を4回くらいしてました。

あんまり捗りませんでしたね。今は結構はかどってます。
螺旋本時間をかけてゆっくりねっとりコネコネしていこうと思ってます。

ってかブログの内容どうしようかな
短すぎて特に見る価値もないので今日は更新の通知出しません(恥ずかしいので)

ところでどなたか僕にc++デバッグ機能を丁寧に教えてくれる方はいませんか?
ディスコか何かで画面共有しながらやってくれると助かるのですが…
vimデバッグ用のプラグインを入れる方法でも、VScodeでデバック昨日を使う方法でもVisual Studioで使う方法でも何でも構いません…。

今日は久々のABCでつね!!

ねこ!!(新種の挨拶(猫なので))

昨日ブログ書いたあと、4時半ぐらいに寝ました(寝子なので)
ちょうどホットアイマスクを切らしてしまったので、なかなか寝付けませんでした。(寝子なのに)

ジャガイモは根です(根っこなので)


どうですか?本日のブログは面白かったですか??
それではまた明日。





嘘です(嘘つきキツツキなので)

はい、それじゃあブログ書いていくよ(現在時刻は6:25)
まず日常
7時半ごろ起床。起きるも、「これ睡眠時間足りて無くね?」まじでだるい!!布団出れない!って言って8時20分ぐらいまで布団にいました。
8:40から授業開始。18:30くらいまで学校にいました
疲れマンガリハッタイ。(疲れました)

で帰ってきたらtwitterで、バチャコン19時からやるよ!!ていうツイートを見かけたので、本当はお風呂に入ってから寝ようと思っていたけどバチャコンに参加しました。

バチャコン means AtCoder virtual contest. つまり、競プロ感覚を味わえるもの


んで、20:30睡眠 23:00起床
起きてからというものtwitterにあまり活気がなくて気分が沈みましたね。えぇ。
うどんを茹でたり茹でなかったりして、たぶん1時くらいから勉強を開始。
そしてダラダラとTwitter、精進、アニメ。今に至る。

大学での日常は特に面白いこともなく終わりました。
あ、いや、嘘3コマ終わった後の4コマが空きコマで、5コマが授業なので時間をつぶさなきゃいけなかったのでPCルームに行きました。

そこで、AtCoderの解説動画を流しながら寝ていました。
これは面白いことといっていいでしょう。


精進録

先ほども言ったようにバチャコンにでました。
ABC140を解くコンテストでした。本番で解けなかったDが解けました。
とはいってもABC140本番当日のTLの記憶があったので若干解法バレはしていたんですけどね。
楽しかったっす。

でまあ、このバチャコンやった後寝て、23時になったわけです。

おきてだらだら → C++言語本を少々。(1章も進んでない)
そしてARCのAを一問だけやってたら6時です。嘘やろ。
ヴァイオレットエヴァ―ガーデンを見て泣いたりもしました。

今日解いた問題はこちら~~
(バチャコンは外します)

ARC064 Same Integers.
解き方一応書く(頭整理用かな?)
atcoder.jp
(超雑に書いたので読むと混乱するかも。読まないほうがいいよ)

これはですね、A,B,C三つの値としてみるんじゃなくて、
3つの値を入れれる配列に値をぶち込んで
sort.

・1番小さい値を2番目に小さい値と一緒にする

・その二つの値を同時に3番目の値と同じにする

この二つの手順で答えを求めました。
また、小さい方から x , y , z
として、 y - x の値が奇数の時は、2ずつ+してもxをyにできないことに注意
たとえば x , y が 1 6 のとき
xを1 -> 2 -> 4 -> 6という風にしてyまでもっていかなきゃいけないのですが、xだけ+1する操作はできないので、yとzに+1する操作をします。
よって3つの値は y - x が奇数の時には (x, y+1 , z +1 );
となっています。そしたら、2番目の値と1番目の値の差を取って2で割ったもの、3番目と2番目の差を取ったもの、を足し合わせれば答えが求まりゅ。


っていうのは今気づいたはなし。
僕は、y - x が奇数なら操作回数1増えて、そうじゃないなら操作回数は増えない。

あとは (y - x) / 2 を足す。 (z - y)を足せば答えかな?って思ってコードテストすると1足りなかった。じゃ、1足してみるかってことで足したのを出してみたらACしました。

よく考えたら、2を足さないといけないのは、
xをyにするのができないから zとyに+1するので操作回数が1、
そしてxをy+1に持っていくのも1回増える
だから2を足さないといけないんですね。

ex) (x,y) = (1,4)なら 2数の差は3、これを単純に2で割った値を足すと1だけど、yを5にしてから 1 -> 3 ->5とするのでここで操作回数が1回増える。
こんな感じで2回操作回数増えるね。


こんな感じ。
最後にブログ用にメモってたことをそのまま貼り付けて終わるよ。
AtCoderのレート、目標についてです。
確かに上昇志向はあるにはあるんですが、いずれ、暖色(黄色とかオレンジとか赤)になれるかって現実的に考えたときに、無理な気がするんですよね。
というのも、まだ自分はCやD問題くらいしか解いていないし、EやFはほとんど見ていないのでテキトー(テキトーは雑、適当は妥当くらいのニュアンスで使います)なことしか言えませんが、高得点の問題は数学の知識がかなり要求される?んじゃないかって思ってるんですよね。
過去に数学オリンピックのようなものを目指したことのない僕は数学が嫌いだとは言いませんが、数学にかなり力を入れて本気で勉強した経験がないんですよ。
だから僕は良くて水色、欲を言うなら青ににいけたらいいな、と思っています。それ以上は数オリ目指す人たちが持ってるような知識が必要になるのかな。とも思っています。

こうは言っていますが、本当は黄色になりたいな。って思っていますよ。

螺旋本をやる(これは”やる”という意味。結構本気で)のに数学の知識がいるか分かりませんが、とりあえず螺旋本を読めるくらいの数学の知識は螺旋本をやっている際に入れていくと仮定した場合、いったいどこまでならレート上げれるんでしょうか…?


またね!おやすみ!寝ます!(猫なので)

タイトルは思いつかない

こんばんは。今日は1コマからなのでこの記事書いたらさっさと寝ます。
だから頑張ってさっさと書き終えてやる!!(書き始め,3:06)

近いうちにブログをちゃんと目的をもって書くようにしようと思う。
近いうちにね。
今回はまた昨日までと同じように
日常 → 精進録って感じで。
(今回は精進録までの文量が多いので、読み飛ばしたい方用に、 ・精進録 ってでっかく書いておきます。 スクロールしてください)

・日常編
昨日ブログを書いた後寝る
13時頃に起きる。
おなかは空いていない。昨日の夜すき家に行ったからかな?
でも木曜日で大学の講義はないので、精進する気があるからコンビニに行ってミルクティーを買いに行きました。
で、C問題を1問解く
夕方に大学に行ってごはんを食べる。
帰る (19時くらい)
C問題1問、螺旋本1問
それだけしかやっていなのに気づいたら3時。
なぜ?????
本当に分からん…。まあ今言ったやったことについては後で話そう。

精進録の前に。お悩みの話を。
螺旋本、どうやって学べばいいんですかね…。


(ツイートって多分貼っても問題ないよね)
まあこのツイートは、AOJ本のやり方っていうか、やる価値あるぞ!!って言ってくれてるんですけど。
このツイートを引用して何が言いたいかというと
> 螺旋本やる価値あるんだな。頑張ろうってこと。

では最初に自分が提示したお悩みについてどうするか。
まずは私の最近の螺旋本に対する姿勢をお話します。

第一章のバブルソートあたりまでは、問題とアルゴリズムを読んで自分で実装しようとしていました。
それから第6章くらいまで、
>問題を読む
>分からん
>アルゴリズムを読む
>実装できそうにない
>解説を読む
>分からん
>コードを読む
>分からん
>AOJに行って他の人のコードを読む
>分からん。

こんな感じだったんですね。
で、なぜ「分からん」のかについては、反論はあるとは思いますが二つあります。

・一つは、C++言語に対してまだ知識が固められていないから。
>プログラミングに触れている期間についてみてみると、3月、9月、10月とまだそんなに長くなく、C++言語の本もまだ読み始めて一週間(一応一周はしたけどね。)

・もう一つは、解説を読むのに時間を割いていない。つまり理解しようと努めていないから。
>AOJに行って他の人のコードを読む。 これ、ダメですね。 プログラマーはコードを読めば何やってるか分かる!!! それはそうだ。
しかしそれは言語を理解したもののみ。それに、言語を理解したからと言って何も考えずに読めるわけがない。6年近く習った英語でさえ、何も考えずに読むことはできるようになっていないのだ。
そして生まれてからずっと使ってる日本語だって、ミィィィィって感じで聞いたり読んだりしても理解できない。
きっと今この長文を読んでいるあなたも(もし理解しようとして読んでいるのなら)結構集中して読んでいるだろう。

一つ目に対しては、後々分かっていくでしょう。

で、2つ目に対して、僕は今日螺旋本で、コッホ曲線という問題をやっていました。
当然解けるはずもなく、 さっき述べた螺旋本お勉強手順の コードを読んで分からんってところまで行きました。
で、ふと「このまま 分からん -> 次の章へ行く->次の章…」って感じでやっていけばいつか分かる問題に出会える。そう思っている自分がいることに気が付きました。
おそらくですが Noです。
それともう一つ。
螺旋本ってなんか、問題がAtCoderの感じに似てないから、AtCoderに似てない問題はそんな考えなくてもいいでしょ。
DPとか累積和とか説明したら集中してやろう。

そうやって怠惰に学んでいました。

で、話の転換はここから。
今日、コッホ曲線という問題を分からんまで行った後、ちゃんと理解しようと努めたのです。
まず結果から。
「ちゃんとやれば理解できんじゃん!!!」

はい、理解できました。
僕がコードを読みたくない理由は、主に以下の理由でした
「scanf , printf 分かんねえよ」

はい、よく考えたらこれだけだったんですよ。
構造体も、自作の型も一応お勉強したのでそこそこ分かるようになっているんです。
だからちゃんと読めば分かりました…


というわけで!!!
螺旋本、時間をかけて勉強します!! あっはっは!!
(文字でかくするのテキトー(何も考えずに雑にという意味のてきとう)にやってます、見づらかったらごめん)

あともう一つお悩みがあるんですよ。こっちは解決できません。

僕は、高校受験の頃と大学受験のころとどちらも、塾を途中でやめてるんですね。
塾を好きになってかなり勉強をやった後で嫌いになってやめた。
そして辞めた後は気分が最悪になって勉強ができなくなった。

こういう流れがあるんです。
であんまり大学内の話はしたくないんですけど、大学入ってからも同じようなことがありました。

この話から何が言いたいかっていうと、今競プロをとても好きで頑張っている(当社比)のですが、いつか嫌いになってしまいそうなのがとても怖いです。
それは誰かと不和を起こしたのがきっかけで起こるかもしれない。普段のツイートがきっかけで人と喧嘩して嫌になるのかもしれない。
とても怖いです。
あくまで主観ですが、結構な数の人を好意的に見てしまうので、距離感を間違えて死ぬ可能性が結構あると思うんですよ。
だから、気を付けてるつもり。
そして本当に気を付ける。(ほんとか??WW)
かといって、ネットの人はネットの人!と割り切って考えるのは流石に寂しすぎる。
Twitterを介して友達になったりするのはダメなんでしょうか…?
僕は「あり」だと思ってるんですよね。でも、ありだと思っているせいで不和を起こすのかもしれない。

まあとりあえず気を付けて生きます。
そんだけ・。・


・精進録
お待たせ
今日はC問題二つ解きました。少し解いてる際の考察等を書きます。
C - Rectangle Cutting
まず一つ目、面積の小さい方の最大値を求めろって問題です。
僕の考えの流れを書きます
>出力例を見る、長方形の面積の半分が出力例にある。ってことは大きい方と小さい方のサイズが一緒はおkか
>どういうときに長方形の半分が答えになる?そしてどういうときに最適な分割方法が二つ以上ある?
>長方形を横、縦に二等分、対角線で二等分するときは半分にできそうだ。
>では、上記で上げたとき以外はいったい何が最大になるのか
>(x,y)が入力で与えられたとき、その点を通る直線の方程式 Y = a( X - x) + y だ(aは任意の実数)
>でもこれじゃ解けないな。お手上げだ。「ギブ!!解説読む!(とツイートをする)」
するとフォロワーさんが、高校数学は対称性大事 のようなことを言ってくれました。

>対称性を意識して最大の面積が導出できる…?
>あ!!!!!!長方形の中心と反対側の点を直線で結べば半分にできる!!!
>さらに、上記のように点を取るとき、点は1点しか取れないので、真ん中以外の時最適な分割方法はない!!
あとは頑張って実装
ってことで解けました。
C - Prison

2問目です
テキトウに紙に書いてみる。分からん
>bitset で L1 とR1 が3,5 . 00111 11111にして、うまいこと 00111 ←3番目から5番目をつなぐ線分としてみる
>みたいなことが出来ないかな…できねえ…諦めた(ここまで1時間くらい?)
>ディフィカルティ―100が解けない…俺はダメ…


解説を見る

は?? 天才か??

解説頭いいっすわ。僕が言っても面白くないので解説見てください。
ってか皆さんは解説読まなくても解けると思う。


で、今日C問題二問しかやってないって言ったけど嘘ですわ。
AtCoderに新しく生えたチュートリアルやりました。
みんなもやろうね!!

やべえよ、執筆で1時間ぐらい使っちゃったよ…
寝ようね。

おやすみ

プログラミング課題にいじめられたの巻

うぃ。

こんにちは。僕です。もう朝ですね。おはようございます。
とりあえずいつもみたいな感じで、一日の流れ → 精進の話って感じで進めようかな。

1日の流れ~ (一日と1日、表記を統一しろ。って自分でも思っている)

昨日ブログを書き終えたのが6時とかだっけ?それから寝る
→12時頃起床 →大学→ハラヘッタ
でも講義あるので飯食えん。
3コマ中 →
ハラヘッタ 寝起き、なんもやる気起きん。
気づいたら授業が終わっていた。
ちなみに授業中
先輩からDMが来る。「同じ講義受けてる?」 →僕「y」
そして授業後に初対面。こんにちは。こんにちは。
その先輩、来年から他大学に編入する方なので、編入についてのお話を聞きました。

3コマ終わった。飯。豚辛みそ丼。おいしい。
4コマは空コマ なんもやる気が起きない
で、今AtCoderの提出歴を見てみたんですけど、昼は全くAtCoderしてないらしいです。
あ、いや、やったわ。やったけどやってない。
javaの課題でAtCoderをやれっていうのがあって、それを3秒くらいやりました。
今日の13時〆の課題があるんですけどやってません。やる気ないです(ダメ人間)

でまあ、その課題をしてボーっとしてたら5コマの数学が始まりました。
プログラミングのための線形代数っていう本で線形を勉強しようと思っていたんですけど、どうもやる気が出ず、板書だけ取って、まあ、いつかこのプログラミングのための線形代数を読んで理解深めよう…っていうスタンスで授業聞いてました。


思うんですけど、まだ後期が始まったばっかで比較的授業が重くないうちに、学業投げ捨てて競技プログラミングやっといたほうがいいと思うんですよね。知らないけど。
まあそんな感じで言い訳して学業を結構疎かにしています。

はい。授業終わった~ 飯食った~
飯タベタ…そして声を掛けられる
「にぼしくん、プログラミングできる???」
アーッ
成り行きで図書館へ行き別学科の子のプログラミング課題をやることに…
計算量10^9を軽々と超えるプログラムしか書くことが出来ずに泣きました。
いじめられた。悲しい話。
まあいろいろ言いたいことはあるけどあんな課題はプログラミングの課題じゃねぇ!うんちだ!!

で、あと僕にも悪い点がありまして、それは "Java書けない^^"ってことなんですよね。
C++でできることjavaでも3/4くらいはできるようにしとけよ。

ってかさ java めんどくさくね?
何が楽しくね
Scanner sc = new Scanner(System.in); (あってる?)とか書かなあかんねん。

だるすぎやろ。
しかもあの言語、小文字と大文字区別するやん!しんど!しんど!だるい!だるい!Www書き方分からんおしまい

以上、競プロerからのjavaおよび課題に対する愚痴でした。

で、3時間くらい図書館に拘束されていたんですけど、その学科の課題をやって自身の課題は1ミリもやっていません

面白いですね。面白いですか?僕は面白くありません。

21:30 帰宅
風呂
22:PC前。
なんかやる気起きないな

学校から帰ってきたままの頭でいるのやだな…
少し寝よう。横になる
1時間くらい寝た。起きた。
よし、頭から大学が消えた。やれるぞ!!

ん~ハラヘッタ。すき家すき家にフォロワーがいた。

瑞々しいにぼし on Twitter: "いみこさんと一緒にすき家行ってきました"
まあ、これは僕にありがちなことなんですけど
「同じ時間帯にコンビニに行けば一緒にコンビニに行ったことになる」
っていう理論をすき家に応用したってことです。

んでまあAtCoderしてたらこの時間ですね。
あ、Twitterもしてたよ。
一日の流れここまで

                                  • -

AtCoderのお話
C - Divide the Problems
簡単。 ソートして真ん中の二つの差

C - Remainder Minimization 2019
結構苦戦した。
でもまあとりあえずこの問題を通して
例えばまあ、10^9+7 = mod としたときに、
modで割った余りを求める系問題について
・a+bをmodで割った余りは a と bをそれぞれmodで割った余りを足してからmodで割った余りに等しい。
・a * b をmodで割った余りは、aとbをそれぞれmodで割った余りをかけてからmodで割った余りに等しい。っていうのが理解できました。
証明もできます。嘘です。証明なんて言う仰々しいものはできません。
めんどくさいから自分が書いたのをそのまま貼るだけ貼っておきます
f:id:niboshi_bisyoujo:20191017061834j:plain

ちなみに足したほうについては、割った余りっていうのは、0以上mod以下になるまで
引いて、その0以上mod以下の数のことを指すんだから、まあいけるよね。って感じ
とりあえず入力で受け取った値の2019で割ったものを受け取って、できる掛け算全部やった。
まあ最悪のケースを考えてもありうるのは
1 * 2 から2017 * 2018までを2019で割った余りを求めればいいので
計算量は10^6くらい?
はい AC
そういえばこの問題の解説読んでない気がするぞ…読んでから寝ます


最後
C - Anti-Division
頑張った
偉い
本当はこの問題を一番自慢したかったんだけど
ブログ書くの疲れちゃったのでおしまい

終わる!

じゃあね

良く学びよく遊べ ksガキども

こんばんは。
年ですかね、お尻が痛い。座ってると
おしりが…痛い…

ウィっす。
今日はツイートが伸びました。


ほうれん草。大事ですね。

AtCoderの話に入る前に少しなんかおしゃべりします。

何をはなそうか。
そうだな、じゃあ僕のお気持ちから。
僕はツイートが伸びたらまあそれなりに、嬉しいんだけど、
それよりも普段絡みのないフォロワーからのリプライとかお話のほうが好きなんですよ。
好きなんですよ(大事なことなので390回言いました)
だから積極的に声かけてね。

昨日は寝ずに学校行って、3回くらい意識飛びました(眠気のため)
17時ごろから22時頃まで睡眠
そして今に至るって感じですね。
たまには大学の授業の感想でも書いていきますか。

・英語 何これ ふざけるな くそが
・フランス語 ああ、グループワークの班男一人になっちゃった。宿題ちゃんとやらないと恥ずかしいな。
・心理学 覚えていない

こんな感じ。
ちなみに今日の大学のスケジュールは
ブログ書き終わったら寝て昼に起きて3コマと5コマ
です。


別に僕の生活面語っても面白くないんで今日の精進の記録をつけていきますね。

先ほども言ったように22時起床。
それから…それから…あれ?俺起きてから何やってたんだ?

記憶がない
ツイッター見てきて少し思い出しました
24時くらいまで少しc++の勉強
24時くらいから、ビット演算学ばなきゃいけないことを思い出す。
AC - 3.05.ビット演算
これですね。
んでやる。やった。
ビット演算 はえ~~。
で2、3問解く。ARCの31は難しいな。パス。
その後何も考えずにビット演算関係ない問題を解く。
でまあツイキャスしながら問題解く。解く。Twitterする。
を繰り返してたら5時半くらいになってました。
あ~そうですね…
うーん、自慢できることあるかな…
あ、あった
A - Double Helix
この問題。
普通なら、っていうか僕が一回目解いたときは脳死でif文4個並べて解いてたんですけど、今日はね、なんか楽できねえかな。かっこよく解きたいって思ってやって見ました
それがこれ
見ろ

~
#include <bits/stdc++.h>
using namespace std;
int main(){
	// A T , G , C;
	vector<char> a ={'A','T','G','C'};
	vector<char> b = {'T','A','C','G'};
	char s; 
	cin >> s;
	rep(i,4){
		if(s==a[i]) {
			cout<<b[i]<<endl;
			break;
		}
	}
		
}

~

今適当にコピペして余計なもん外したりしたから若干変になってる。許して
repの定義も書いてねえわ。
許して
これね。どう?どうよ??!?
aに対応するvector bを用意して対応させるもんを出力させるようにしたの
すごいでしょ。
すごいよ。
すごいから(笑)
ひれ伏せ

なんか書こうとしてたけど忘れた。ブログってなんだろうね。

金のセンテンスをやっていない。やったら寝ます(10センテンスくらい)
それではおやすみなさい。
皆さん、よく学び、よく遊びましょうね。
競技プログラミングは遊びですか??
僕は知りません。でも楽しいです。

僕は探索ができない

うっかりAtCoderの問題の解説を求めてこの記事へ来てしまった方へ。
ここでは問題の解説どころか解答も載せていません。
ごめんなさい


全探索
むずくね?????
各要素になんか操作をする。しないの二通り
制約がきつくなければ2^n通り!!
みたいなこと言うやん
わかる。
分かるよ。
でもね…
書けない・・・
ベースケースが分からないよね。あと遷移も

全探索で解く問題。それはこれ↓
C - たくさんの数式 / Many Formulas
これ、こり!!コリオリ力!!!
コリオリ力については下のサイトを参考にしてください
コリオリ力 ■わかりやすい高校物理の部屋■
ちなみに僕は慣性力の一種ってことしか知りません。

物理の話をしたいんじゃないよ。したいんじゃないんだよ。

要するにこれ解けないって言いたかった。
んでね、仕方ないからね、螺旋本とかで全探索、学ぼうと思った。
ちなみに↑の問題は写経ACしようと思ったけど理解できなすぎてやめた。

全探索ってさ、難しいんですよ。
全探索は二分探索より低俗なもの!みたいに思っていたんですけどそんなことはありませんでした。
まじで実装するの難しいです。
でもやるしかない。
だってレート上げたいもん。
ってことでね、僕はこれからとある全探索の問題を自然に実装できるようになるまで毎日解くことにしました。
典型的な DP (動的計画法) のパターンを整理 Part 1 ~ ナップサック DP 編 ~ - Qiita
けんちょんさんの記事で紹介されているDPの典型問題。(ですが全探索で解いても間に合う)
こちらをやっていきます。
そして、先ほど貼った「たくさんの数式」はビット演算の知識がないとよく理解できないんですよ。
APG4bで1ヵ月くらい前にビット演算の項目が追加されたんですけど、やってなかったんすよね。 なんでかっていうと、「& ?? 1と1 なら1でしょ。知ってるよ。」そう思ってたから。

知ってなかったんですね…悲しい

毎日解くといったあの問題は明日にでも自然に手が動くようになってると思います。
でそれが解けたらついでにDPで解くのも(記事の解説を見ながら)やろうと思うよ…。


話2
みなさん、先週末にABCが開催されていなかったのは覚えていますよね。覚えてるよな?覚えてるって言え。
で僕、競技したい欲がひどすぎて、気づいたらバチャコンに参加していました。
2人でやるか、って感じで友人が開催してくれたので、一応Twitterで告知したら開始10分前の告知なのに2人も参加してくれました。
本番パフォで1200くらいでした。

くっそ楽しい
なんだこれ
楽しすぎる
競技プログラミングって競技中が本番なんだな
楽しい
楽しい
楽しい
楽しい
楽しい
楽しいい……
まじで

コンテスト中の楽しさ半端じゃないっす。
今週末のコンテスト楽しみにしてます。
それと、これからバチャコンの開催がツイッタで告知されていたら積極的に参加しようと思います。


ちなみに昨日の20時に起きたのが最後で寝ていません。今日は2,3,4コマが授業です。家に帰ってくるのは16時。
は~ 頑張るぞ~…
今寝たら絶対に起きられないから起き続ける。

今は全探索難しい;;無理ぃ;;になってるけどいつか
全探索?ww余裕ww って言えるようになっていたい。
それとこの前Twitterだか解説動画で、「水色以下の人全探索もうちょっと実装出来てほしい」って言ってたので頑張る…
実のない記事ですまんな。(話があっちこっち飛んでて申し訳ない)