STLを活用しよう

この記事は熊本高専Advent Calendar2017 3日目の記事です.


数か月ぶりの投稿になります.民です.最近書いてなかったので僕が言えたことではないですがみんなブログ書きませんね.そもそも存在を忘れていそう

用途にもよりますが皆さんプログラミング言語は主に何を使用しているでしょうか?
僕は主にC++とHaskellを使っていて,新入生に対してもC言語を教えているので今回はC++のSTLについてお話しようと思います.

STLとは?

STLとは,Standard Template Libraryの略で,C++の標準ライブラリの1つになります.ヘッダファイルをインクルードすることで使うことができます.
しかしここで注意してほしいのは,Cの標準ライブラリのように関数名だけを書くだけでは駄目で,std名前空間を指定する必要があります.名前空間については説明が面倒なのでC++の参考書を読むなりググるなりしてください.

今回はSTLの中でも自分が特に便利だと思うものを紹介します.今回はあくまで紹介なので使い方に関しては参考書読(ry

~アルゴリズム系~

・std::sort

algorithmヘッダをインクルードすることで使用することができます.
概要としては名前そのままで,引数の範囲をソートします.
クイックソート(C++11以降ではイントロソート)で実装されており,計算量はO(N log N).

・std::next_permutation

algorithmヘッダをインクルードすることで使用することができます.
順列を生成してくれます.ただしソートされている必要があります.計算量は最大O(N).

・std::lower_bound

algorithmヘッダをインクルードすることで使用することができます.
指定された要素以上の値が現れる最初の位置のイテレータを取得することができます.いわゆる二分探索みたいなものです.計算量はO(log N).

・std::upper_bound

algorithmヘッダをインクルードすることで使用することができます.
指定された要素より大きい値が現れる最初の位置のイテレータを取得することができます.std::lower_bountと同じく二分探索みたいなものです.計算量はO(log N).

~データ構造系~

・std::vector

個人的にダントツで使ってます.重いけど便利.
vectorヘッダをインクルードすることで使用することができます.
いわゆる動的配列と言われるもので,可変長配列として実装されています.配列の動的確保と何が違うかというと,vector自体がストレージを管理しているため,自動的に領域が確保されます.

 ・各要素への添字アクセス(定数時間)
 ・全要素の両方向の走査(線形時間)
 ・末尾への要素の追加・削除(償却定数時間)
という点で優れているのが特徴です.いろいろなメンバ関数があるのでぜひ触ってみましょう.

・std::map

mapヘッダをインクルードすることで使用することができます.
キーとそれに対応する値を格納するデータ構造,いわゆる連想配列といわれるもので,二分木(赤黒木)で実装されています.
こちらにもさまざまなメンバ関数が存在します.

・std::priority_queue

queueヘッダをインクルードすることで使用することができます.
いわゆる優先度付きキューといわれるものになります.

 

以上,本当にざっと紹介しただけでしたがSTLはかなりの数が存在し,正直列挙できるような量ではありませんのでその都度調べたりしましょう.
これを機にSTLや標準ライブラリに対して興味を持ってもらえたらなと思います.
アルゴリズムだったりデータ構造だったりを一から実装していくのもアリですが,ライブラリに存在するものは積極的に活用していくことしていくことをおすすめします.

 

次は高専プロコンの振り返りとかをAdventCalendarも兼ねて誰か書いてくれるはず…書いてくれるよね?
 

 

 

南九州ハッカソン参加記

久しぶりの投稿です.民です.
9/2(土)〜9/3(日)の二日間で鹿児島市で開催された南九州ハッカソンにチビフェスさんと一緒に参加し,最優秀賞を頂いてきました.

南九州ハッカソンとは?

Mashup Awards 2017 鹿児島,宮崎,熊本 etc.予選を兼ねたハッカソンになります.テーマは自由で開発スタイルも遠隔サポートありなど,とても自由度の高いハッカソンになっています.

最優秀賞はMashup Awards 2017の準決勝進出権が与えられ,最優秀賞の他にも企業賞があったりします.

詳しくはこちらを見てください

南九州ハッカソン : https://mashupawards.connpass.com/event/63855/
Mashup Awards 2017 : http://mashupaward.jp/

作品
僕たちのチームは,「IoY(Internet of Yakiniku)」という焼肉とIoTを掛け合わせた作品を作りました.肉が焼けているかどうかを判定して,わかりやすくプロジェクターで投影するという色弱の方にも優しい焼肉支援システムです.

1
こちらに作品が紹介されていますので,詳しくはこちらをご覧ください
http://hacklog.jp/works/50512

移動

9/2の朝,起床チャレンジにも無事成功し,新幹線にてチビフェスさんと合流して会場へと向かいました.熊本-鹿児島間での新幹線移動はトンネルばっかりでこれといって面白いものはなく,1時間もせずに鹿児島中央駅へと到着し,会場には開場の1時間前に到着してしまったので適当にそこらの公園で時間を潰しました.鹿児島中央駅で少し遊ぶのもありでしたね.

イベント開始〜アイデアソン

無事イベントが開始し,まずは参加者の自己紹介,企業さんによる技術サポートのインプットがありました.今回のハッカソンでは,サイボウズ株式会社さんのkintone,アームさんのArm Mbed,ソフトバングロボティクスさんのPepperが技術サポートとしていらしていました.

ちなみに参加者に学生は僕たち二人を含めても三人と少なく,ほとんどが開発などを仕事にしているプロの方々だったりしました.

次にアイデアソンがありました.テーマは自由なので,アイデアソンでは与えられたお題からアイデアを考えたり,自由に考えたりで次々とアイデアを出していき,最終的に作りたいものが一致した参加者同士でチームビルディングをするという感じでした.僕たちはチビフェスさんのアイデアに,僕たち二人を含む,四人のチームとなりました.

ハッキングスタート

14時30分となり,いよいよハッキングがスタートしました.4人で役割を分担し,チビフェスさんはサーバー構築,僕はローカルシステム構築という役割で作業に取り掛かろうとしましたが,開発環境のバージョンの問題などで環境構築に少し手間をかけてしまいました….環境構築の合間に昼頃なので眠くならないようにエナジードリンクを摂取し,いよいよ作業に取りかかりました.

今回はPythonを使って開発したのですが,僕自身はC++とHaskellしかまともに使ったことがなく,Pythonはつい最近基本文法を教わったばっかりで開発できるのか不安でしたが,僕以外の三人がPythonのプロだったのでなんとか教えてもらいながら書きました.開発に使用したライブラリはよく使っていたので僕にとってはそこが唯一力になれた点でした.

1日目終了

20時となり,それぞれのチームの進捗を発表し,1日目が終了しました.1日目は終了しましたが,帰って休むのも徹夜で開発を進めるのもありでした.僕らは徹夜開発をするつもりで宿なんてそもそも確保していなかったため会場にそのまま残り,開発を進めました.(夕食はメンバーの方のご馳走になりました.美味しかったです.)

流石にずっとPCの前で作業しているのはきつく,2本目のエナジードリンクを摂取して気休めに銭湯へ向かいました.銭湯に向かっている最中,食後に炭酸を摂取したため胃がきつくなってきてチビフェスさんに銭湯で使うタオルを買ってきてもらったのですが,なぜか二千円分ものタオルを買ってきていて爆笑しました.

2日目スタート

2日目の早朝,徹夜で少々きつかったので外に出たら桜島が噴火していました.すごかったです.

20170912_001807

チビフェスさんは用事があるため引き継ぎをし帰宅.三人でのスタートです.
朝っぱらですが,ここで3本目のエナジードリンクを摂取しました.

ローカルシステムなどがある程度完成したため,調整ためのデータを集めるために肉を近くのスーパーに買いに行きました.

昼過ぎになり,いよいよ最終調整のデータを集めるために肉を焼き始めました.

20170903_134149
誰がなんと言おうとハッカソン中です.もちろん焼いた肉は美味しくいただきました.美味しくいただきましたがハッカソン中でデータを集めるための焼肉です.通行人にとても不思議がられました.

ハッキング終了〜懇親会

最終調整もなんとか終わらせてついにハッキング終了です.

それぞれのチームがプレゼンを行い,タッチアンドトライがありました.どのチームも個性的なプレゼンや作品で見るだけでもとても面白いものでした.Mashup Awards 2017の公式サイトにもそれぞれのデモ動画が上がっていますので是非ご覧ください.

懇親会では,企業の方々や参加者の方々から面白い話を聞くことができ,とてもためになりました.

審査発表

懇親会が終わり,いよいよ審査発表が始まりました.
まず技術サポートにいらしていた3社の企業賞,そして最後に最優秀賞の発表でした.
なんと僕たちのチームが最優秀賞をいただき,準決勝の出場権を手に入れることができました.
20170904_132312

僕はこのようなイベントは初めてだったのでとても驚きましたが,なんにせよいい経験になりました.準決勝は12/10(日)で,当日が日本情報オリンピックの予選のため僕は参加できるかわかりませんが,準決勝に向けて開発を頑張っていこうと思います.

 

以上,長くなりましたがありがとうございました.

今日から夏休み

初めまして!

新入部員(笑)のおやじです。

今日から高専生は夏休みですねぇ

記念すべき夏休み第一日目が八月十日なんて、たまげたなぁ

まぁ、そのことは置いておいて

新入部員おやじは夏休みをいかにして過ごすのか…

実は高専祭の展示作品としてDXlibで「人生ゲーム」を作っているのですが、しょうもない作業が多すぎてモチベが下がりつつある状況。人生ゲームですからね、50のマスがあるなら50のネタと画像にBGMやらその他諸々。ソースは書いてて楽しいけれども、それ以外の作業は正直、う~ん… まぁ夏休み中にある程度終わらせないと間に合いませんので頑張ります。

完成した作品はいつかWebに投稿するのも良いなぁ、と思いHTMLも勉強中です!

新入部員として今の時期はひたすら勉強ですね、頑張ります。

 

 

ACM-ICPC参加記(?)

民です.久しぶりの更新です.

(だいぶ前ですが)1年生へのC言語ゼミも無事に終わり,教えたことを定着させるためにオンラインジャッジをしばらくやらせています.目標としては来年の新入部員に教えられるくらいのレベルまではいってほしいなと思ってます.
プロコンの予選結果発表もあり,慌ただしくなってくる時期ですが,9月にはパソコン甲子園の予選もあるので高専プロコンと両立して競技プログラミングを頑張っていきたいですね.頑張りたいけどきつそう悲しい…

さて本題ですが,昨日,ACM-ICPC国内予選がありました.当部活からは4年生3人の1チームが参加しました.
国内予選公式サイトはこちら
http://icpc.iisf.or.jp/2017-tsukuba/domestic/

僕は2年生なのでまだ参加できないのですが,問題は公開されていたので解いてみました.参加できないので提出が出来ず,正確な結果はわからないのですがおそらくA,B,Cの3完でした.B問題が例年に比べて若干難化してたように感じましたが果たしてどうなんでしょうか…?D問題はbitDPな気がしてたけどbitDPをまず書いたことがなく,さらに具体的な解法が全然分からなかったです.悲しい.DPに対して強くならないと競技プログラミングコンテストにおいて上位を狙うのはやはり相当厳しいですね…

解けた問題に関しての簡単に方針を載せておきます.
 

A問題
1問目なので難易度はまあはいという感じでした.
N個の数字の中から2つを選ぶ組み合わせの最大の和を求める問題.
2重for文で全列挙するだけ


B問題
概要を説明しようとすると僕の日本語力じゃ説明が足りないので省略.
いつもより難化しているようには感じましたが,難化というより実装が面倒になった問題のように感じました.
二重引用符で囲まれている文字列とそれ以外の文字列を取り出していって,それぞれ比較.STLで殴りました.


C問題
1つ1つに高さが設定されてる3*3以上の長方形において内部のセルが外周より低い長方形から外周の高さとの差の最大値を求める問題.
制約が3≦d,w≦10と小さめなので4重for文での全探索.中の処理も含めても多くてO(N6)ぐらいなので十分間に合う.


これでちゃんとACできるかは分からないけど変なコーナーケースを作れるような問題でもなさそうなので多分あってるはず(?).
4年になることには国内予選を突破できるぐらいまでには精進したいなと.尚,チーム戦なので競技勢をもっと部内に増やさないといけないですね.

高専プロコンまでも時間があるわけじゃないのでコツコツと頑張っていきましょう!

五月病

こんにちはお久しぶりです.五月病に季節です.民です.僕は五月病にはかかっておりません.

本日は新入部員歓迎会があり,今年度シス研には1年生5人,2年生1人の計6人が新たに入部してくれました!最初は1人しか入ってくれないんじゃないかとビクビクしておりましたが無事6人入ってくれてとても安心してます.新歓ということで新入部員は先輩たちのこと,また先輩たちは新入部員のことを知ることができたでしょうか?できなかったとしてもこれからの活動の中でお互いがどんなことをやってるのかが分かってくると思います.

そして現在,高専プロコン予選資料提出期間直前ということで,部内はとても忙しい感じです.課題部門は去年に引き続き「スポーツで切り拓く明るい社会」,そしてまさかの競技部門も去年に引き続きパズルということで波乱を呼んでいるとか呼んでいないとか…
なにはともあれまずは予選を突破できるように各自頑張っていきたいと思います.

新入部員に関しては,まずはC言語ゼミを受けてもらっています.最初はとても難しく感じると思いますが問題ありません.僕たちも最初はわけがわからなかったです.最初のうちはそんな感じですが,分からないところは先輩たちに質問をするなりして,だんだんプログラムを書いていくうちに基礎は身についていきます.頑張っていきましょう!(個人的に競技勢が増えてくれるとうれしかったり)