ロアちゃんかわいい

競プロっぽい話がなされる駄文の掃きだめ

典型攻略:絶対値の和の最小化

おはようございます。 明日から夏休みですね。

DP記事とか言うのは知りません。(もうちょっとかかりそうです)

ここまで解いた問題で2回使うことになった内容なので知識として記録しときます。

TeX記法とかいうので表示する練習も兼ねています。上手く表示されない場合はご一報ください~。

実数列a_{i}(1≦i≦n)に対して
\sum_{i=1}^{n}|a_{i} - x|
というxの関数を考えます。
この式をf(x)と置くと、y=f(x)は折れ線のグラフを書きます。
絶対値の和なのでf(x) ≧0は明らかですが、これはxをどこまでも小さく、あるいは大きくしていくと、無限大に発散することがわかります。
この関数の最小値を与えるxを考えます。

さて、最小値を求めるにはどうしたらよいでしょうか?
結論から言うと、xがa_{i}の中央値になる時にf(x)は最小になります。
例えば数直線で級数の各項はxとa_{i}の距離なので、xの右にa_{i}がn個ある時にxを右に1動かしたらf(x)の値はn減ることがわかります。
それぞれの点にxが1だけ近づくので。

xが右にΔx動くとすると、右にn個a{i}があればf(x)は当然nΔx減ります。
xの左にm個a_{i}があるなら、右にxを1動かすとf(x)はm"増え"ます。
なのでxの左と右にあるa_{i}の個数が等しくなる時に値が最小でーす。

勝った!第三部完!
一見当たり前だけど!こういう典型知識の積み重ねがなんかいい感じにあれするんですよ!

以下使う問題です。(なんか2017年の慶應医数学で似た問題が出てたみたいです。こういう各場合にxをちょっとずらして考えていくみたいな発想は受験生諸氏も覚えておくといいかもしれません)

C - Linear Approximation

B - AtCoder Market

ではおやすみなさい~。

茶色になったしC問題も実装できたぞ!

おはようございます。(今回の記事は例の如く、流れが分からない人は第一回を見てください。)

 

茶色になった!

 

f:id:zero_kpr:20190422010919p:plain

 

謎の新生物こと私こるぼーですが、ABCのコンテスト中にC問題を実装して、さらに茶色になったのでこの度進化しました。

自撮りです↓

f:id:zero_kpr:20190422012611j:plain

これが

 

 

f:id:zero_kpr:20190422011310j:plain

 

ちょっと成長して腕とか固まりました。まっくろくろすけとはもう呼ばせない。

 

このまま精進して最強の新生物になるね!

 

おやすみなさい!

プログラムってどこに書いたらいいんですか?

おはようございます。

 

今日はテキストエディタとかいうやつの話です。

 

前回、前々回とプログラムの書き方を習ったわけなんですが、そもそもプログラムってどこに書いたらいいでしょう?

 

これまではAtCoderのコードテスト(※前回記事のAPG4bに載ってたはずです)に直接書いてたんですが、みんななんかかっこいいやつをpcに入れてる。ぼくもあれほしい。

 

例えばゲームをやったりする時に動くプログラムはPCのどっかに保存されてるわけです。しかしどこに書けばええんや?

 

それで調べたら出てくるのがこれです。

 

メ モ 帳

 

おちょくってんのか?

 

……と思いましたが、どうやら本当らしいです。

 

適当なメモ取る時に使うだけじゃなかったんかお前……

 

プログラムって結局は文字列で出来てる情報なので、書けて保存出来れば何でもいいらしいです。書いて保存するためのソフトウェアをテキストエディタといいます。

 

メモ帳はWindowsに最初から入ってますが、もっと便利なテキストエディタが色々と開発されているらしいです。

 

沢山あってよく分からんので適当なのを入れよう!

 

https://azure.microsoft.com/ja-jp/products/visual-studio-code/

 

Visual Studio Code!通称VScode、なんだか高機能らしいです。

 

とにかくこれで書きやすくなるわけですね。

 

早速使ってみましょう!

 

ç»å

 

なんだかかっこいいですね。

 

このVSCode、最初は機能とかも全部英語で書かれてるんですが、拡張機能(expansion)とやらの項目で日本語化機能をインストールすると日本語表示ができます。英語あんまり読めないので助かります。

 

これで狂気のマッドサイエンティストに一歩近づけたような気がするぞ!

 

でもなんだか味気ないですよねこれ。他のみんなのを見てると文字に色ついてるんですよ。

 

おかしいなーなんでぼくのは色ついてないんだろーなーと思って色々調べると、どうやら使用言語を選べるようです。

よく考えるとテキストエディタの方で使う言語を認識できるはずないんで、こっちから選ばなきゃいけないのも当然なんですが、これ分かるまでにかなりの時間を要しました。

ç»å

 

VSCode画面の右下の方が↑のようになっているので、「プレーンテキスト」をクリックします。すると言語を選択できるので、そこからc++だのpythonだのを選べばいいわけです。

 

実際にやってみましょう。

 

ç»å

 

すごい!色が付いた!世界は美しい!ありがとう!ありがとう!第3部完ッ!

 

これで書きやすくなったね!書いたプログラムをどうやって動かせばいいのかとかよく分からんので後回し!

 

今回は以上!さよなら!さよなら!

 

速さがだいじ!APG4bを読もう!

おはようございます。

 

前回に引き続きAtCoderの話です。

 

謎の新生物、@saba_kprのせいで魔法少女にされてしまったぼくは、次なる目標としてAtCoder Programming Guide for beginners、通称APG4bの攻略に挑むことにしました。

 

APG4bとは、大まかに言うと「プログラミングやったことない人がAtCoderをやるための教材」です。

 

知識のない僕にはちょうどいいぜ!という事で早速リンクに飛びました。

 

https://atcoder.jp/contests/apg4b

 

どうやらC++というプログラミング言語を使って教えてもらえるらしい。

 

前回書き忘れましたが、プログラミング言語には色々な種類があり、それぞれ違う文法や機能があるようです。

動作の早さも違うとかで、中々一大事。

 

競技プログラミングは実行速度に制限があるのです。言語によっては同じ内容を書いても時間切れになってしまうとか。

 

新生物仲間、sabaが教えてくれた言語のpythonはかなり書きやすく機能が充実しているけど、実行速度はあまり早くないようです。インタープリタがどうこう言ってたけどよく分からないので後回し。

 

一方このC++は、pythonに比べるとちょっと書きづらいけど、実行速度は早いとか。誰かがC言語との互換性がどうたら言ってた気がしますが、よく分からない!後回し!

 

早速APG4bを読んでいく。現在午前2時。踏切に望遠鏡担いでいく時間です。

 

何やらfor文やif文など、pythonでやった内容が結構ある……。

言語に種類があると言っても、ある程度やりたいことは共通らしいです。そりゃそうか。

ということは、その「やりたいこと」の部分を理解する方が大事っぽい?

 

午前5時。読み終わった。再帰関数とかいうのよく分からないからとりあえず飛ばした!後回し!

 

どうやらこのAPG4bはまだ未完成っぽいです。しかし未完成とは言え、プログラミングの入門が大分スムーズに行えました。完成に期待しましょう。

 

分かりやすくてすぐ読めるのでとてもありがたいです。AtCoderの使い方やらも載っていたので助かりました。

 

章ごとの例題も解き終わったので、過去問の方をぶっ飛ばしていきましょうか。

 

A問題とかいうやつ簡単すぎるのでB問題からやっていきます。

 

おやすみなさい!

 

新生物、AtCoderを始める

 

はじめまして。こるぼーと申します。真っ黒な不定形の新生物です。

 

f:id:zero_kpr:20190422012611j:plain

 

魚の形の新生物仲間(@saba_kpr)にプログラミングを始めないか?と言われたので、この度プログラミングを始めることになりました!(事態が呑み込めない方は前回記事を参照してください。)

 

ぼくはこるぼー。この間生まれた新生物だ。ある日、新生物仲間のsabaが家にやってきた!

saba「やあこるぼーくん!ぼくと契約して競技プログラマーになってよ!」

ぼく「むり!」

saba「そう言わずに先っちょだけ!今なら洗剤も付けるから!」

ぼく「こっちは赤ちゃんだぞ!プログラミングなんて出来るわけないだろ!」

saba「ちゃんと教えるからへーきへーき!数学出来れば何とかなるよ!」

ぼく「ほんと!?高校数学は生まれた時から知ってるから出来るかな?」

saba「もちろん!さあ始めよう!」

ぼく「わーい!」

 

そんなわけで国内大手の競技プログラミングコンテストサイト、「AtCoder」に登録することになりました。

 

まずはこれをやって覚えていこう!とsabaがリンクを送ってきた。

 

https://qiita.com/drken/items/fd4e5e3630d0f5859067

 

なるほど、ここの10問でプログラミングの基礎を学べるらしい。

 

saba「初心者でも簡単!pythonを覚えてみよう!」

ぼく「pythonって何だい?」

saba「pythonは簡単に書くことのできる言語さ!機能も充実しているから、いろんなものに応用できるよ!最近流行りの機械学習なんかもpythonが使われることが多いんだ!」

ぼく「機械学習ってあれでしょ!意識高さアピールしたがる横文字大好き文系おじさんたちが自慢げに語るやつ!AIAIえーあーい!うさんくさーい!」

 

ぼくの感想はさておき、pythonは確かに分かりやすい。sabaの説明の上手さもあって、すぐに「最初の10問」を解くことが出来ました。

 

パズルみたいで楽しいです。ほんとは細かい知識も必要らしいけど、そういうのは後回しにして出来るところをガンガン進めよう!ということになりました。(この方針はとても良かったと思っています。お陰で飽きることなく進められています。)

 

その日は上記URLの精選10問を解いて、他にもいくつか問題を解いて終わりました。

 

AtCoderにはいくつかコンテストの種類があり、今回やった問題は初心者向けの「AtCoder Beginners Contest」、通称ABCの問題です。

 

ABCの問題は各回4問で構成され、難易度の低い順にA問題、B問題、C問題、D問題となっています。

 

https://kenkoooo.com/atcoder#/table/

 

↑のリンクでAtCoderの過去問をまとめてあるサイトに飛べます。

 

今回はC問題までやってみました。B問題までは実装するだけ、Cからは頭の中で色々考えることが必要になる難易度という印象です。

(実装・・・機能を付け加えること。ここでは何かの機能を付けるためのプログラムを書くこと。)

 

いくらかやってみたけど、C問題は解けないのも沢山あった……。

どうやら、問題を解くために必要な知識が結構あるらしいです。saba曰く、解いて覚えるのが早いとか。

 

まあ何とかなるでしょう、僕は新生物なので!

 

というわけで。

 

このブログは、知識0のオタクが競技プログラミングを通し、雀の涙ほどの数学力でプログラミングを学んでいく、その過程の記録です。

 

ではおやすみなさい。

 

 

Re:ゼロから始まる競プロ生活

おはようございます。こるぼーと申します。

 

自分の記録~と思ってこのブログをざっと見返してみたんですが、なんだかTwitterでやれば?という感じのものが大半!つまらん!

 

折角競技プログラミングを始めて記録しても、これではいまいち精進の様子が分からないと思ったので、ちょっとこれまでの記録をやり直すことにしました。

 

あたかも「プログラミング始めたて!」みたいなノリで書く予定ですが、その実既に7週間経っています。

 

実を言うと、もうちょっと軽い感じのブログが書きたかったんですよね、ニコ動のゆっくり実況みたいなのが理想です。

 

そんなわけでこれまでのクソ記事は削除しようかと思います。じゃあな!