microbeの活動日記

プログラミングコンテストとか勉強とかいろいろ

第30回全国高等専門学校プログラミングコンテスト参加記 #procon30

はじめに

美少女に蹴飛ばされたい

 

概要

・熊本高専熊本キャンパス 4年

・競技部門

・第4位,特別賞

・2年次までは八代キャンパスに在籍していて,その時を含めると3回目の出場

開発について

開発項目を

GUI

・通信およびその他

・ソルバ

の3つに分けてメンバー3人で完全分業で開発しました.僕はソルバを担当しました.ソルバのアルゴリズムについてはNAPROCKがあるので詳しい内容は控えますがパンフレットからそこまで離れてないのでパンフレット見てください.インターンとか受験勉強とかあってソルバを完成させたあとは他は何も手伝ってません.ごめんなさい.

 

移動部門

交通費削減ということで八代キャンパスの人たちと一緒に貸切バスで都城まで移動しました.近いのもあって台風の影響は受けませんでした.ホテルの外観が廃墟みたいでした.LANがなかったのでつらかった.

 

本選

日曜日(1日目)

予行演習

トークンがいつ公開されるんだろうなーとメンバーと駄弁りながら参加者連絡会議を聞いてたら運営のほうから「トークンは事前に指導教員のほうに連絡してあります.」という声が聞こえてメンバー一同「は?」となりました.
急いで指導教員のところに行ってトークンが届いてないか確認してもらいましたが,1か月前くらいに連絡が来てて僕たちには転送してなかったことが発覚しました.結局予行演習までにトークンを使った通信の修正は間に合わず,予行演習中は修正に時間を充てました.

 

ファーストステージ

 何とかファーストステージまで修正を終わらせました.とはいっても修正してくれたのは通信担当のメンバーなので僕は何もしてません.ありがとうございます.そして何もできなくてごめんなさい.

 ファーストステージは「都立(品川)高専」さん,「呉高専」さん,「宇部高専」さんとの対戦でした.競技部門に関しては2日目が本番だと思っているので初日は評価関数のパラメータを適当にして2位通過でもいいので良さげなパラメータを探してみようみたいな精神でいました.

宇部高専さんはどうやら通信がうまくいってなかったようで勝ちました

・呉高専さんはちゃんと通信が出来てたので警戒しながらなんとか勝ちました

・都立(品川)さんには評価関数のパラメータを適当にしていたのもあって2戦とも負けてしまいました.普通に強かったです.

結果としては2位通過しました.

 

深夜開発

ホテルにLAN環境が無かったので近場のカラオケまで行ってから,初日の様子を踏まえてパラメータ調整をほぼ徹夜で行いました.パラメータ調整は「俺たちが遺伝的アルゴリズムだ」みたいな感じで人の手で調整しました.ごめんなさい.

徹夜でパラメータ調整をするつもりでしたが,そこまで勝てると思ってなかったので公開フィールドのDくらいまでを調整したらみんな飽き始めて人同士で対戦して遊んでました.なんだかんだで一番楽しかったです.

 

月曜日(2日目)

セカンドステージ

セカンドステージは「呉高専」さん,「奈良高専」さん,「福島高専」さんとの対戦でした.

記憶が飛んでるのではっきりは覚えてませんが,なんだかんだみんなで動いてたので警戒しながらなんとか勝ちました.

 

準々決勝

決勝トーナメント進出だー.わーいと喜んでたら前回優勝の仙台(名取)高専さんとあたりました.仙台(名取)さんには前回大会の予選リーグでボコボコにされた記憶があったのでこわかったです.(前回はソルバをうまく使えなかったというのもありますが)

公開フィールドも非公開フィールドも前日に調整したパラメータの得意な盤面だったのでなんとか勝ちました.リベンジ(?)を果たせたのでうれしかったです.

準決勝

八戸高専さんとの対戦でした.正直ここまで勝ち上がれると思ってなかったのでDより広い盤面を想定したパラメータ調整をしてませんでした.普通にソルバ負けしました.完敗です.

3位決定戦

名門の久留米さんとの対戦でした.ところどころ順位が入れ替わったりしましたが結果的に負けました.やはりソルバも強かったです.

 

本選を終えて

反省

パラメータの調整不足というのもありますが,ソルバもエージェントの数が増えてくると大きく弱体化するようなアルゴリズムだったのでそこが敗因だったのかなーと思います.NAPROCKまでに修正しようと思います.

結果

最初にも書いてありますが,順位的には4位で終わり,特別賞を頂きました.うちの高専(熊本キャンパス・八代キャンパス)は競技はドチャクソ弱くて,熊本電波高専と八代工業高専が合併して熊本高専になってからは競技部門の受賞はなく(合併以前も受賞は10年以上前で1回程度),熊本高専としては今回が初めての競技部門での受賞,ベスト4ということになります.

感想

来年は受験が控えているので出場するつもりはないので,今回が最後の高専プロコン出場になります.最後の出場で結果を残せたのは嬉しかったですし,メンバーには感謝しかないです.本当にありがとうございました.

計算理論の基礎 1.オートマトンと言語 序論

目的

一度読んではいるけど曖昧な理解なまま終わってしまったのでもう一回読んで知識のアウトプット

参考書はこの3つです.

計算理論の基礎 [原著第2版] 1.オートマトンと言語

計算理論の基礎 [原著第2版] 1.オートマトンと言語

 
計算理論の基礎 [原著第2版] 2.計算可能性の理論

計算理論の基礎 [原著第2版] 2.計算可能性の理論

 
計算理論の基礎 [原著第2版] 3.複雑さの理論

計算理論の基礎 [原著第2版] 3.複雑さの理論

 

 

内容 

序論ということで内容はこの本で学んでいくうえで必要なグラフや集合など数学的概念,背理法などの証明のタイプの説明.この本で必要なグラフや集合などの知識は一般的なことなので省略

定理の主張しているものの構成法を見せる論法を構成的証明,定理が偽であると仮定し,その仮定から矛盾を道ぶく手法を背理法,無限集合のすべての要素がある特定の性質をもつことを示す際に用いられる論法が帰納法帰納法は,証明したい性質がx(1)としたときx(1),x(2),...が真であることを証明する基底,各i\geqに対してx(i)が真であると仮定してx(i + 1)が真であることを示す帰納法のステップの二つからなる.

 

感想

基本的なことなのでまあはい.

JOI夏季セミナー2018参加記

はじめに

女の子に踏まれたい

概要

日本情報オリンピック 夏季セミナー2018に参加してきました.ノリで応募したら通ってしまった.

1日目

・空港までが遠すぎるので朝5時に起床する.

・空港へ向かう途中ニュース見てたら台風が直撃してた.飛行機が飛ぶか怪しい

・空港に到着する.ちゃんと飛行機とんだ.よかった.

 

羽田空港に到着する.

・何人かと合流してお昼ご飯を食べるなどする.

・夏季セミ会場への登山がきつい.結構な人がすでに到着していたので適当に座る.

・適当に自己紹介する.

・本を選ぶ.はじめから型システム入門を選ぶつもりだったが念のため全部チラ読みする.全部やばそうな内容やがw型システム入門にしよ!w

・とりあえず本を読み進める.

・夕食おいしい.レストランまでの労力が大きすぎる.

・本を適当に読み進める.まだ内容がわかる.

・健康的なので11時半ごろに寝る.

2日目

・健康的なので7時に起きて朝食を食べる.

・本を読み進める.わからないところがちょくちょく出始める.チューターに聞く.わかりやすい.天才.

・昼食を食べる.

機械学習の講義を聞く.数式が全然わからない.なんとなく雰囲気を理解する.それでも面白い.ためになった(気がする)

・本を読む.なんとなくわかった気になる.

・夕食を食べる.登山がつらい.

・4章がよくわからなくなる.とりあえずOCamlを少し触ってみる.わからない.

・健康的なので11時過ぎ頃に寝る.

3日目

・起床に成功して朝ご飯を食べる.朝ご飯を逃す人々が出てくる.

・5章がおもしろすぎる.5章を完全に理解することを目指し始める.ほかの章もなんとなくは理解したつもりだったけど実装が全くできる気がしない.実装をあきらめる.

・昼食

・5章を完全に理解しようと演習問題をとにかく解いてみる.

・夕食でYou shock

・5章を完全に理解する(ホンマか?)

・健康的なので11時くらいに寝る.

4日目

・朝食で超ショック

・スライドを作り始める.

・昼食

・講義だね.マリオコンピューティング.

・引き続きスライドを作るが作り終わる気がしない.

・夕食

・ひたすらラムダ計算の簡約をする.

・みんながABCをやってる中スライドを作る.2時くらいに作り終わる.ねね.

5日目

・健康的なので7時に起きて朝食にありつく.

・発表順が一番最初になったことに気づき焦る.

・なんとかギリギリ時間内に発表する.

・ほかのひとの発表がすごい.むずかしい(小学生並みの感想)

・最後の発表がおもしろかったね.

・終了

まとめ

楽しかった.

各位頭良すぎでは?留年したら来年も参加したい.

日本情報オリンピック2017/2018 本選参加記

2/10(土)から2/11(日)につくばで行われた第17回日本情報オリンピック本選に参加してきました.

 

会場までの移動(2/10)

飛行機で関東まで向かいました.あまり飛行機には乗ったことなく耳が痛くてつらかったです.

関東についてから会場があるつくばまでの途中で秋葉原に昼食をとるために寄りました.蒙古タンメン中本に一度は行ってみたいなと思い蒙古タンメン中本まで向かったんですが,行列がすごいことになっていて並んでいたらプラクティスに間に合わないことを悟り適当に店を探して昼食を済ませました.ヨドバシカメラすごかった.

昼食を済ませた後はつくばエクスプレスで会場であるつくばカピオまで向かいます.

 

会場到着後(2/10)

会場に到着したので本人確認や交通費振込申請などの受付を済ませます.
20180210_210836
受付で予選Aランクの楯をもらいました.うれしい.

荷物置き場に荷物を置きに行ったんですがプロたちがたくさんいてこわかったです.

会場についてしばらくすると本選環境に慣れるためのプラクティスが行われました.
ラクティスはそこまでの難易度はなかったので何とか全完しました.4問目がかなり苦手な類だったのでバグらせずに実装出来てよかったです.
らっはプロとプラクティスの最中にエンカしました(問題解いてる最中に話しかけて申し訳ない

ラクティス後はCiscoの方による講演会がありました.詳しい話をすると長くなるので省きますが,情報セキュリティ関係の話でした(Ciscoなのでそれはそう).情報セキュリティにはそれなりに関心があったので講演を聞けて良かったです.

講演会後は夕食も兼ねての交流会がありました.1人1人自己紹介があったんですが名前しか言えなかったうえにコミュ障を拗らせすぎて席の確保さえ困難でした.つらかった.コミュニケーション力大事.

 

本選競技(2/11)

翌日の2/11(日),9:00~13:00の4時間にかけて本選競技が行われました.問題や解答はこちらで公開されています.

結果としては150点,Bランクでした.最初の20分くらいで1問目を解きましたが,2問目の小課題3までは簡単に思いついて部分点をとるために提出して50点を得て以降は満点解法を狙って残りの時間ずっと詰まっていました.他の問題の部分点をとるために時間を回すべきでしたね…

もともと春合宿にいける精進も実力も全く足りないと思っていたので,Bランクをとれただけでも割と満足ではあるんですが最後のJOIともあって少し悔しさが残りますね.

本選後は問題作成者による解説がありました.解説を聞いていた感じだと2問目があと少しのところだったのでさらに悔しさがありました.
飛行機の時間の関係で解説を4問目まで見て会場をあとにしました.

 

最後に

もともと予選さえなぜAランクをとれたのかわからないくらいの精進量だったので本選へ出場できただけでも良い体験になったと思います.
来年度にもSuperConパソコン甲子園などがありますのでもこれ以上に精進していきたいと思います.

日本情報オリンピック2017/2018 予選参加記

本選参加有資格者として参加しました.今年が最後のJOI予選になります.(高校から存在を知った人にはチャンスが2年しか残されてないの罠じゃないですか)

この記事は熊本高専Advent Calendar 11日目の記事も兼ねています.

 

結果

A,B,C,Eの4完 + D部分点で410点でした.3完で終わると思っていたので4完出来てうれしかったです.

 

解説

1問目 鉛筆(Pencils)

問題:
鉛筆をN本以上買うときにA本でB円のセットとC本でD円のセットのどちらかのセットのみをいくつか購入するときの必要な金額の最小値を求める.

方針:
やる
問題文をよく読むとどちらか一方のセットしか買うことができないことに注意する.

gist4cc34e3387c4d0dbae738baa0e552aa6

 

2問目 双六(Sugoroku)

問題:
スタートとゴールを除いて1と0から構成されるN個のマスがあるので,1のマスを踏むことなくゴール出来るサイコロのうち最も面の数が少ないサイコロを求める.

方針:
考察するのが面倒だったので全探索した.
面の数が小さいサイコロから見ていき,出る可能性のある面をすべて再帰で求めていきゴール出来たらそれが答え .計算量が怖いので1を踏んだらそれ以上は枝刈りした.

gist60247aaaa2a52c1e59dfdb998382e5aa

あとから考えたら1が最多くも連続している箇所さえ超えられればいいので最も多く1が連続している個数+1で求まると気付いた.

 

3問目 幹線道路(Trunk Road)

問題:

南北にのびるW本の道路と東西に延びるH本の道路があって各交差点に人が住んでいる.南北,東西にのびる道路のうちそれぞれ1本の計2本を幹線道路とするとき,各交差点から最も近い幹線道路までの距離の総和の最小値を求める.

方針:
どれを幹線道路にするかを決めて各交差点からの距離*各交差点に住む人数をすべての組み合わせにおいて全探索する.O(H^2 W^2)

gistdb0f1ff0fa9465a8fff11b23bf6a3c95

 

4問目 水ようかん(Mizuyokan)

すぐにDPだと察したので部分点(10点)だけとって逃げました.予選終わってから各プロが話してるの見て解いた.

問題:
N本の切れ目がある水ようかんをどこかの切れ目でいくつかに切った時の長さ最大のピースと最小ピースの長さの差の最小値を求める.

方針:
dp[i][j] := i本の切れ目までの切り方を確定し,長さ最大のピースがjであるときのこれまでの最小のピースの最大値.
Lの累積和をとっておくと切った区間の長さをO(1)で求められるので計算量が減る.別にしなくても十分通るだろうけど.

gist91fce8a135515b29a854b7616cc02090

 

5問目 森林伐採(Deforestation)

何とか時間内にACして100点.

問題:
H*Wのマスで森林が構成されていて木が生えていないマスのみ1マス移動するごとに1分で移動でき,木が生えているマスはそのマスに隣接したマスから1分かけて1本切ることができる.北西から南東まで移動できるようになるまでにかかる時間の最小値を求める.ただし,木を1本切るたびに北西まで1度戻らなければならない.

方針:
問題見た瞬間に最短経路問題に帰着できることに気づき,拡張Dijkstraっぽいことをする.
北西から(i,j)までの最小時間とそこまでに行くことができる最小のマス数を持たせておく.すると1本木を切って北西に持って帰るまでの時間も簡単に計算できる.
グラフを構成してもいいけどグリッドでそのままやったほうが考えるのも実装も楽そう.楽しかった.

gistce24420dd3dc1e39657bbc53c74eb421

 

6問目 L番目のK番目の数(LthKthNumber)

部分点も取れなかった

問題:
横一列にそれぞれ数が書かれたN枚のカードが並べられており,連続するK枚以上のカードの列すべてに対して次の操作を行う

  • 選んだカードを,書かれている整数が小さい順に左から並べる.
  • 並べたカードのうち,左から K 番目のカードに書かれた整数を紙に書き出す.
  • 選んだカードを,すべて元の位置に戻す.

これから書き出された整数を昇順に並べた時,L番目の数を求める.

方針:
わかんないや!(放棄)
プロたちによると二分探索でうまくやるといけるらしい.

 

感想

最初にも書いてますが,3完で終わると思ってましたが4完出来てうれしかったです.ただ問題の雰囲気が今までと少し違って感じたので少し戸惑いました.難易度的には僕の感覚では全然わからないですが5問目が楽しかったです.いい加減DP問題を本番中に解けるようになりたいなあ...
ボーダーもさまざまな情報が飛び交ってますが全然予想できなくて怖いですね.400以上は確定と願いたいんですが1度だけボーダー420の年があるので余計怖い.頼むから通っててくれ.

 

余談ですが景気付けにHHKBを購入しました.おかげで気分が高揚してます.

 

 

 

追記(2017/12/14)

Aランク通過してました.

ガウスの消去法をC言語で実装

この記事は熊本高専Advent Calendar 8日目の記事です.

 

本日AdventCalendarに書く人がいなかったため,それを埋めるついでにガウスの消去法をC言語で実装したので紹介しようと思います.

 

ガウスの消去法とは

ガウスの消去法は,連立一次方程式を解くための多項式時間アルゴリズムになります.他に連立一次方程式の解を明示的に表すことができるものとしてクラメルの公式がありますが,クラメルの公式で大規模な問題を解こうとすると計算量が爆発してしまうためあまり計算機で解くことにおいてはおすすめしません.

ガウスの消去法は,前進消去と後退代入という2つの操作からなります.文字だけで見ると少し難しく感じてしまいますがアイデア的には中学数学レベルで解けるようなものでとても簡単です.

 

本当にその場しのぎみたいな記事で,詳しく解説する時間がなかったので詳しいところは以下のサイトを参考にしていただけると幸いです.

ガウスの消去法 - Wikipedia

 

ソースコード

gist2a2c29a2ae3da762f1cb226f9a7a8e10