競技プログラミングをゆる~くやりはじめた
もともと競技プログラミングや数学があまり得意な方ではなかったなんですが、N高等学校で競技プログラミングを教えるということもあるし、N高生には競技プログラミングがまじで得意な生徒さんやら、アドバイザーのドワンゴ社員もいるのでこれはチャンスと思い自分もゼロから競技プログラミングをはじめてみることにしました。
競技プログラミングといいつつ、かなりゆるくやっていこうと決意。たぶん、競技ゲーみたいに勝負と思ってやると心折れそうだったので、低い山から自分なりの目標を持ってやるということで、まずはAtCoder Beginner Contest(通称ABC)の001からはじめて見ることにしました。
開発環境整備
言語は、競技プログラミングのプログラミング言語はほとんどの人がC++を利用しているということで、自分もC++ではじめることにしました。思えば、CとかJavaとかはそこそこ書いたりするのですが、C++をしっかり書き始めるのははじめてなので環境整備から。
最初CLionとかのIDEを使って書こうと思っていたのですが、ほとんどの参加者がエディタでやるということで、自分もUbuntuのg++とVimでやることにしました。
構成は、VirtualBoxとVagrantをインストールして、そこにUbuntu16を入れ、そこでg++とVimをインストールして使っています。そのへんの構成の構築はQiitaにも書いたとおりです。
エディタは、VS Codeでもよかったのですが、生放送配信とかする時に VS Codeの画面がうまくキャプチャできなかったのでVimではじめたというのが理由です。なお.vimrcはこちら。
VimのC++の環境を整備して思ったのは、vim-clangというプラグインで利用できる、clang-formatが思いのほか便利ということ。このVimでもVS Codeと遜色なくコーディングすることができました。
あと、大会によってはエディタでないと困ることもあるようなので予めVimやEmacsなどのコンソールエディタに慣れておくのは結構良さそうです。
というわけで実際にここまで説いた問題のメモをまとめていきます。 コード自体は、GitHubのsifue/cpp-studyにまとめてあります。
ABC 001
まず、最初の001で結構な洗礼をうけましたw
A問題
これに関しては、C++の標準入力と標準出力の行い方の手習いという感じでした。特に難なく終了。
B問題
突然長いif文をかかなきゃいけなくなり苦戦。そもそもC++の標準出力のフォーマットの仕方がわからなかったのですが、 C++ の iostream フォーマット指定早見表 のおかげでなんとかなる。
C問題
巨大なswitch文とif文を書くことになり心が折れる。
0~31までの数を。"N"とかの文字列に変換するところなどでバグを埋め込んでしまい、その修正に結構時間をかけてしまうということをしました。
得られた教訓としては、できるだけデータ構造にぶっこんでswitchとかifとか長いの書かないほうがよいということです。最期は <
を <=
にし忘れていたという凡ミスでした。
D問題
境界値が重要ということを思い知らされた問題。 60分と0分って同じなんですが、処理の過程でやりやすくするためにどちらかに統一しないとミソ。データのマージ自体はまあ職業プログラマなら約やっていると思うのでアルゴリズムに関しては特に何か気になることはありませんでした。 ただ、この問題もバグでひたすら苦しんでいました。 C++ の iostream フォーマット指定早見表 が神でした。
ABC 002
突然問題がストーリー形式になって、なぜか楽しみながらできるようになりました。 やはり面白い問題文のほうがやる気がでますw
A問題
if文がかければ大丈夫な問題でした。
B問題
とりあえず配列に文字を全部突っ込んでチェック。 この時に久しぶりに配列を使ってみて便利ー、と思っていたのがD問題で罠でした。
C問題
精度に気をつけなきゃいけない問題でしたが、なんとか正解。 ただ、intとdoubleの計算時の変換などは、ある程度CとJavaで知識があったから良かったものの、intをdoubleで四則演算するとdoubleになっちゃうなんていう情報は、プログラミング初心者は知らないだろうなぁと思いつつ。 多分このへんでC++の文法の本を読み始めたいとおもう問題に作ってるあるのだなぁと思いました。
D問題
ドハマリしました。 最初は議員の関係の表を作って、その一つの関係から探索して最大を探すような貪欲法的プログラみムを書いていたのですが、なぜかWrong Answer。ちゃんとだめなパターンが入っているようです。 で、結局最後は全パターンを調べるということで深さ優先探索で全パターンを作ってACとなりました。 まあ計算できる計算量なら最初から全探索したほうがよいということでしょうか。 あとここではじめて再帰が必要になったりして、だんだん競技プログラミングらしくなってきたなというふうに感じました。
あと最初2次元配列で実装したのですが、関数での引き渡しの際は参照渡ししても二次元配列の二次元目は固定長でなくてはならず、結局ポインタ操作になってしまう非常に面倒くさいことになったので、コンテナを使ったほうが良いということを学びました。
以上のサイトのAPIリファレンスが神でした。とりあえず存在するコンテナを一通り確認して、サイトの右上にあるカスタム検索でvector、set、map、pair、priority_queue、queue、stackなんかを探して使うことに。
なお、C++のデータ構造、代入し直した瞬間にコピーになるので、関数とかで&をつけて参照渡ししたいときだけは気をつける必要がありそう。とはいえ、参照渡ししないといけないほどシビアになることはまだなさそう。
ABC 003
だんだん難しくなりつつあることに怯えながらのチャレンジ。
A問題
合計して割るだけ。for文がかければなんとか。 なおintとdoubleの変換もあり。
B問題
過去の教訓から配列ではなく、setを使って排除。 コンテナの便利さを感じた瞬間でした。
C問題
priority_queueとstackを使って処理。とにかくC++のコンテナが偉大。 ただ最後は精度の問題があってハマったので、long doubleという型を初めて使いました。
D問題
3日悩んで結局解けず。先程回答を見ました。 1000000007という素数が出てきてなんとなくmodule演算をしてほしいのだなぁと思いつつ。やっていたのですが、配置で壁に沿ってなくてはいけないという部分が難しすぎて断念。 module演算に関しては、
にまとまっていて、ありがたいなぁと思いつつこれを使って計算。ただここに載っているフェルマーの小定理、理解しておらず。
これは部分点だけとれて満足すればよかったのかもしれないと思いつつ。なお、解説を見てもいまいちわからないという状態。解答を見ると、
というのを使って解いていたということが判明。 パスカルの三角形って使えるのか…ということにもびっくりしつつ、フェルマーの小定理も使えるようにして、再度100点の問題だけ説いてみようかなという感じです。
とりあえず、答え見たので答えどおりに実装してみたいところ。
ABC 065
たまたま夜にやっていたので、これにもチャレンジ。
A問題
if文を使った数値判定。
B問題
mapを利用してパスを消しながら検索していくというスタイルで解く。 やはりC++はコンテナが優秀。
C問題
ちょうどABC003のD問題で調べていたmodule演算がそのまま使えたので適用。 ただ、掛け算のときはintからあふれるのでその部分にハマり、最終的に型をlong longにして解決。
D問題
結局未実装なので、どこかで解きたい。 全探索すると10000!というでかい数になってしまうので、結局全パスから最も離れている2点を探して、それを両端として片方から貪欲法で道をなぞっていくのがよいかなとおもったりしつつ、実装はしていない。 他にも罠がありそう。ただ絶対値で係船できるのでC++の複素数ライブラリを使うと実装量が減らせそうだなぁと思ったりしてました。
おわりに
とりあえず、ここまで解いたABCの問題のメモをまとめてみました。まだ解けてないD問題が003と065とあるので、これからやってみたいところ。
だんだん数学的なテクニックが必要とされてきてるので、ある程度やって無理だったら答えを見ながら実装して学んでいくというスタイルでも良いのかなぁと思いました。
これらかも、ゆる~く競技プログラミングをやっていきたいなと思います。
プログラミング初心者のためのワークブック「高校生からはじめる プログラミング」を発売しました
この度、N高等学校/N予備校のプログラミング入門コースで授業した内容の最初の3か月の部分が本になりました!
表紙や中の扉絵がソードアートオンラインなのは、中高生の皆さんにとりあえず興味を持ってもらえるようにそのようになっています。川原礫先生、本当にありがとうございます。(あと一応キリトくんの趣味はプログラミングだそうです。そして、最近映画見に行きました。)
内容は、初めてPCを触る(最近はタッチデバイスしか触ったことがない生徒さんが多い)、中学卒業程度の英語と数学を持つ方を対象としたガチのプログラミング初心者本となっています。具体的に言うと、一番最初はGoogle Chromeのインストールからスタートし、Webプログラミングを通じてプログラミングの基礎を学んでいきます。
目次はこのような感じです。この本で学ぶと、プログラミング経験ゼロの初心者が、Twitterに投稿可能な診断メーカーのような動くWebページをゼロから作れるようになります。
なおこの内容は、 この本の内容はN高等学校の生徒約2200名のうち700名以上が学んだものです。この一年間で授業やQ&Aで生徒から出てきた疑問や質問が解消されるよう、内容を加筆/修正したものとなっています。
- キーボードのキー配置、文字ごとの入力方法など操作法の説明
- ブラウザやエディタのインストールから利用方法までの環境構築の手ほどき
- WindowsやMacのファイル操作の説明
- 中学数学範囲外の内容である論理(かつ、または)などの説明
- 登場する英単語の説明
上の写真のような内容です。学習は、コードを読み、書き、改変するということをプロダクトを作りながら学んでいくようになっています。実際に手を動かして物を作り、反応を見ながら、最終的にオリジナルのプロダクトを作る。プログラミングを楽しみながら学ぶ内容になるよう心がけました。
作るもの一覧はこのようになっています。
この教材はPC、それも5年以上前のPCでも十分にプログラミングを学べます。
最近プログラミング教育ブームとなっており、小中学生にはScratchやProcessing、ArduinoやRaspberry Piといったプラットフォームでのプログラミング教育が盛んにおこなわれています。本書はそういうものとはちょっと違い、かなり実践的ではありますが、中高生がWebプログラミングを通じて普段利用しているサービスの仕組みの一部を知り、プログラミングを体験できる教材になっています。
またこの内容を学ぶと、例えばブログなどでHTML編集の機能を使ったり、Webページのチェックボックスをすべてオンにするスクリプトを書いたり、HTMLとJavaScriptで抽選プログラムを作ったり、そんなことができるようになります。
そしてそれは、Webがあらゆるところで使われている現代において、中高生が学んで実生活において決して損にはならない内容であると思います。
最近「中高生にプログラミングの教育をしてくれ」と頼まれるWebエンジニアもいたりするのではないかなと思います。 そういう時にこの本は教科書として最適です。ぜひこの本書を活用し、中高生へのWebプログラミングを通じたプログラミングを教えていただければ幸いです。
本当に初心者で、特に何かやりたいことが決まってはないけれどプログラミング入門してみたいというみなさんも、ぜひこの本でプログラミングを楽しんでもらえると非常にうれしく思います。どうぞよろしくお願いします 。
- 作者: 吉村総一郎
- 出版社/メーカー: KADOKAWA
- 発売日: 2017/04/14
- メディア: 単行本
- この商品を含むブログを見る
追伸
この内容も含め、続くLinux開発環境構築、Node.jsを使ったWebセキュリティ、フレームワークを使ったWebアプリ開発、Scalaを使ったオブジェクト指向プログラミング、関数型プログラミング、Androidアプリ開発の教材は、N予備校にて月額1000円で一般向けに提供されています。なおiOSアプリは2017年4月、並行処理プログラミングは7月には公開予定です。この本を読んで、続きが気になるよって状態になった方、ぜひ N予備校 プログラミング を体験してみてください。
またこのN予備校の教材を作ったコンセプト、背景などは、Qiitaの記事「高校生にWeb上でプログラミングを教え始めたエンジニアがこの8ヶ月間で得た気づき」 にまとめてありますので是非ご覧ください。
SIerクエストとSIerクエスト2をiPhone/Androidに移植しました
SIerクエストリリースして1年経つわけなんですが、たまたま開発者登録する機会があったので iPhone版とAndroid版に移植して作ってリリースしました!
SIerクエスト iPhone版
https://itunes.apple.com/jp/app/sierkuesuto/id1163670015?l=ja&ls=1&mt=8
SIerクエスト2 iPhone版
https://itunes.apple.com/jp/app/sierkuesuto2/id1163672423?l=ja&ls=1&mt=8
SIerクエスト Android版
https://play.google.com/store/apps/details?id=org.soichiro.sierquest
SIerクエスト2 Android版
https://play.google.com/store/apps/details?id=org.soichiro.sierquest2
以上になっています。
なお開発に関しては、RPGツクールMVのヘルプのとおりにやって、iPhoneはCordova最新バージョン、Android版はcrosswalk、ただし自分はversionCode対応が必要だったためバージョン17系を使いました。あとはスマホ向けプラグインを入れたり、Androidの100MB制限のために不要素材を削除したりするのが意外と時間がかかります。本当にMV Stripperに救われました。
環境構築だけ済めばアプリにするのはすごく簡単で、それよりもアプリアイコンを作ったりスクリーンショットを作ったり、説明文書いたりするほうが作業としては時間がかかっています。RPGツクールMVの素材偉大です。あと、Appleの審査とかストア公開までの時間を待つのにモヤモヤしたりしていました。
まだやってないよ〜。って方はぜひ、SIerクエスト1と2やってみてくださいね。
なおWeb版はこちら。
SIerクエストWeb版
http://sifue.github.io/SIerQuest/
SIerクエスト2 Web版
http://sifue.github.io/SIerQuest2/
では。
追伸
「不要なファイルを削除できる【未使用ファイル削除】機能を追加」
https://tkool.jp/mv/special/update0110.html
最新のツクールMVでは未使用ファイルを削除する機能がついているらしい!気づかなかった!みんなこっちを使いましょう!
SIerクエストとSIerクエスト2の攻略方法
SIerクエストとSIerクエスト2 と作者のsifueです。
あまりに難しすぎてクリアできないよ!って話をよくもらうので、ストーリーでネタバレしないように攻略方法を書きました。検索で見つけた方、これを参考にクリアしてください。
SIerクエスト
- 最初の敵は通常攻撃の連続で倒す。たまに運が悪いと負けますのでくじけずに挑んで下さい。
- 次の敵は、ビンが置いてあるテーブルの手前にとあるアイテムが落ちてるのでそれを使ってから通常攻撃の連続で倒してください。
これらを行えばおそらく2分以内にクリアできるのではないかと思います。
SIerクエスト2
第1章
- 基本的に特別対応しないと勝てないので特別対応ガンガン使って下さい。
- 2戦目は勝てない戦いです。
- 3戦目で出てくるキャラは恐ろしく通常攻撃が強いので殴って下さい。
第2章
- 主人公は通常攻撃、仲間には特別対応をさせると良いです。
- バックアップが取れた後の戦いは、二番目に強い範囲攻撃を2度、その後は通常攻撃を3度使うと勝てます。
- その後出てくる敵は、特別対応で一番弱いのを2度使うと倒せます。
第3章
- 主人公たちは、通常攻撃で十分強くなっていますので普通に殴って下さい。
- ただし、底が知れない敵が現れたら逃げるを選択して下さい。3分の1ぐらいの確率で逃げおおせます。
第4章
- 最初の戦いは勝てないので諦めて負けて下さい。
- とあるアイテムを手に入れた後は、絶対にドリンクを飲んではいけません。全快にはなりますが全員バーサク状態になって詰みます。
- 最後の戦いでは、全員でそのとあるアイテムを使ってください。生き残った誰かが目的を達成してくれます。
以上が攻略方法でした。ゆっくり目にクリアしても20分ぐらいでクリアできる内容となっています。ぜひエンディングまで見てやって下さい。
以上、攻略法でした!
結婚式の二次会用にビンゴゲームのJavaScriptを書いた
WindowsでもMacでも結婚式の二次会用でビンゴをやるためのフリーソフトで良い物が見つからなかったので、JavaScriptで書いてみました。
サンプルは、こちら。
なおこの度も、MITライセンスで、githubに公開してあります。
なお、動作確認は、ChromeとFirefoxとSafariのみ。
インターネット環境がなくても動きます。
機能としては、
- Startボタンでスタート
- Stopボタンでストップ
- 履歴はローカルストレージなので、再読込してもOK
- リセットは、resetボタン。
- ドラムロールが3.5秒間ほど流れる
となっています。
HTMLなので、新郎新婦からデザインの変更が求められたら好きな様に、CSSなどを買えればよいかなと思います。自由にご利用下さい。
あと、iPhoneだと、サイズを調整しないと厳しいですが、iPadなら利用することができました。
なお、ドラムロールの音にニコニコモンズを利用させてもらいました。
http://commons.nicovideo.jp/material/nc79078
kenapoさん、ありがとうございます。
React.jsでLoL生放送のリアルタイムランキングを作ってみました
お盆で会社も気分転換に休んでちょっとしたWebサービスを作ってみました。
世界で一番遊ばれているe-sportsな無料のネトゲ、League Of Legends(LoL)を遊んでいる日本語の生放送だけを抽出して、スコア付けしてランキング化しています。
使った技術はいつもどおりのPlay2/Scala、PlayJsonです。WSは使わずHttpclientをそのまま使っています。WSは罠が多すぎるので...。
やっていることはTwitchのAPIとニコニコの検索APIを叩いてAkka Actorで1分毎に実行しつつそれをCacheに積んでいるだけです。
クライアントサイドは、今回はじめてReact.jsを使ってみました。React.js、以前勉強会に参加した時にはまだまだ使えるようになるの先かなぁと思っていましたが、JSXで書いてコンパイルするというスタイルがおもったより良い感じです。ただエディタは、IntelliJを無理して使うよりはAtomを使ったほうがいろいろ便利でした。
使ってみた感じコンポーネントの再利用がし易い感じがします。TypeScriptとReact.jsを組み合わせて使うと結構保守性も高そう。ただ別に実行速度が高いとかいうわけでもないので、無理して使わなきゃいけないというわけではなさそうですね。
罠としては
- classをclassNameに書き換える必要があること
- {}の中はJ結構JSのコードがかけちゃうので気をつけないと複雑になること
でしょうか。あとComponentというクラスが描画戦略を持っているのですごく頑張って実装すれば最終的に高効率の描画ができそうです。
なおこのサイト、今は前回と今の結果から差分だけをだしていますが、いずれリアルタイムランキングだけではなくLoLのゲーム実況配信者の人気統計みたいなのを取って週間ランキングや月間ランキングを出せればなと思っています。
にしてもこのランキング、今日一日眺めてたけどLoLの女性配信者の多さね...そして、女性ゲーマーでダイアとかゴールドの人がゴロゴロいるってのが本当にすごいなと思います。
JavaFXとRxJavaの勉強のためにSocket通信対応したMac用棒読みちゃんクローンを作ってみた
あけましておめでとうございます。
丁度冬休みということもあって、Mac用の棒読みちゃんクローンを作ってみました。
インストールバイナリもソースコード自体もgithubで配布中。あと、ソースコードはMITライセンスです。
見た目はこんな感じ。
使ったライブラリとしては、
- JavaFX (Java8からデフォルトになったJavaの新UI)
- RxJava (ReactiveExtensionsのJava版)
- gradleのmacAppBundle (Mac用の.appファイルを作ってくるバンドル)
- kuromoji (日本語形態素解析ライブラリ)
- Netty 4系 (高速なTCP通信が可能なサーバー)
実装した機能としては
です。過去読み上げしてくれるMac用のアプリはいくつかあったのですが、棒読みちゃん互換のSocket通信読み上げに対応したものがなかったので自分で作ったというのが軽易です。
ここからは開発の感想です。ここ1年以上ずっとScala書いてるので久しぶりのJavaプログラミングはいろいろ懐かしいものがありました。ただラムダやStreamを使おうとしてみるもののイマイチぱっとしなかったりという感じで、そこはScalaの方が圧倒的に便利です。
まずJavaFXについてです。過去Swing、SWTと触ってきましたが何が特に非同期処理の部分のところが専用のTaskやpropertyのbindを使わなきゃいけなくなっていて結構面倒くさい感じになっています。その他の部分はUIのAPIはかなり素直な作りになっており、初心者にはわかりやすい仕組みになっているのではないかと思います。
個人的に何がすごかったかというと、JavaFX Scene Builderです。こいつが使いやすすぎる。これのためにJavaFXを使ってもいいといっても過言ではない感じでした。fxmlをIDEで協調しながら編集した際にも問題なく利用することができました。
あと、RxJava。元々いろいろ情報は知っていたのですが柔軟なイベントハンドリングをするためのライブラリ。オブザーバーパターンでさえ、様々な実装を用意してくれています。非常に便利なことができるライブラリですが、正直イベントが鬼のように飛びまくるようなUIでは便利ですが、ちょっとしたアプリぐらいであれば、間違った使い方をしてしまうのが少しこわいなと思う所あります。
個人的には、Subjectが様々なバリエーションがあって感銘をうけました。
java - How can PublishSubject and BehaviorSubject be unsubscribed from? - Stack Overflow
GradleのmacAppBundleは、Oracleが.appファイルの作り方を紹介してくれているやつをそのままプラグイン化してくれたもの。kuromojiやNettyは過去何度か形態素解析やTCP/UDPサーバーを作ってみるということをやっていたので、特に問題なく利用することができました。どちらもバージョンが上がってどんどん洗練されている気がします。
このMac用の棒読みちゃん、棒読みさんを今後も少しずついじりながら機能拡張していきたい所です。
追伸
この冬休みずっとFF14とダークソウル2をやっています。真成2層練習パーティが中々集まらないそんなTitan鯖。