utsubo’s blog

競技プログラミングとか．

ICPC国内予選 参加記 2016

ICPC国内予選に参加しました。
順位は、95位でした。

今年はあんまり参加する気はなかったのですが、ICPCが近づくとやっぱり出たくなりました。
チームメンバー集めは、4月ぐらいから始めて、5月頃メンバーが決まって、それから週1ぐらいで過去問を解いて練習。

僕以外は初参加だったのですが、A,B,Cまでは一人一問比較的スムーズに解くことができたので、
一応、最低限の目標は達成できたかなと思います。

その後は、D問題に絞ってウンウン唸っているだけでした。
区間DPだろうなとは思ったのですが、そこから何も思いつきませんでした。
完全に過去の問題の復習不足で、後悔しかないですね。
SRMで出てた括弧の問題とかちゃんと解いとけばなぁとかずっと考えていました。

僕は来年が最後なので、来年はもっと早くメンバーを集めて、ちゃんと復習して、国内予選を突破したいです。

応用情報技術者試験 合格しました

合格しました

応用情報技術者試験についてはリンク参照．
IPA 独立行政法人 情報処理推進機構：制度の概要：応用情報技術者試験
得点は，午前・午後共に8割程度で，割りと余裕がありました．

午前

自分は，情報系の学生であるものの，授業でやった基本的な部分ですら，覚えてたり，覚えてなかったりしました．
ということで，基礎を固めるため，適当な対策テキストを借りて，半分ぐらい読みました．

その後，面倒臭くなり試験3日前ぐらいまで放置．
本を読む気力がなかったので，そこからはずっと過去問道場で過去問を解いてました．
応用情報技術者過去問道場｜応用情報技術者試験.com

午前試験は，過去問から結構出てる感じがあり，最悪それだけやってれば受かりそうだと思いました．

午後

対策せず．
全体を読んで，簡単な問題を探して解きました．
これ国語の問題でしょみたいなのもあったので，そんなにガッツリ対策はしなくて平気そうです．
あと，時間的にはかなり余裕があり，そこで焦る必要はないと感じました．

感想

数年振りに資格試験的なものを受けたので，だいぶ緊張しました．
twitterで受験費をつぶやき，固定ツイートにしておくと，モチベが上がるのでオススメです．
次はネスペを目指します．

ビームサーチの練習用にパズドラAIを組んだ

大学の先輩がパズドラのコンボのAIの話をしていて，そういえば組んだことがないなぁと思い立ち．

目的

パズドラのパズルにおいて，コンボ数をできるだけ大きくするようなパズルのスライドのさせ方を出力する．
今回は，ダメージ等については考慮しません．

方針

ビームサーチを使います．”ビームサーチ”で検索すれば良い記事が沢山出てくると思うので，詳細は割愛．

ビームサーチは下のをそのまま実装しました．

状態は，｛”パズルの盤面の状態”，”今動かしている部分の座標”，”何手動かしたか”｝とし，パズルを1手動かした状態を遷移状態としています（上下左右で4つの状態に遷移）．
コンボ数をそのまま状態の評価値として扱います．

初期状態は，パズルをスライドさせるスタートの位置を変えたもの，計30個に設定．
また，ビーム幅は40000，最大ターンは12として実行します．

ZobristHashで盤面のハッシュ値を生成し，同じ盤面を2回探索しないようにしています（出来てるかは謎）．


deleteしてないからヤバそうなC++コード
https://ideone.com/MbxQOR

まとめ

サクサクっと作った割には5,6コンボ出るので，凄いと思いました．
適当に作ったので（言い訳），全てにおいて杜撰なコードになっています．

記事の書き始めた時はもっとしっかり書こうと思っていたんだけど，途中で面倒くさくなってしまった．

グラフ理論系の好きな問題 5選

最近何もする気が起きないので，今までに見た数少ない問題の中で好きだった問題を紹介します（脚注にネタバレ）．

1. TopCoder Single Round Match 642 Div.2 Hard Tall Shoes

*1が好きなので好きです．
https://community.topcoder.com/stat?c=problem_statement&pm=13523
TopCoder SRM 642 Div2 Hard TallShoes - kmjp's blog

2. Indeedなう A日程 D: Longest Path

全然わからなかったけど，解説を読んで実装するのが楽しかった．
D: Longest Path - Indeedなう（オープンコンテスト） | AtCoder
Indeedなう A日程 解説

3. CODE FESTIVAL 2015 決勝 H: 焼肉の達人

*2に帰着できて感動．
H: 焼肉の達人 - CODE FESTIVAL 2015 決勝（オープンコンテスト） | AtCoder
CODE FESTIVAL 2015 解説 - SSSSLIDE

4. CODE FESTIVAL 2015 決勝 I: 風船ツリー

これも実装が楽しい問題でした．
I: 風船ツリー - CODE FESTIVAL 2015 決勝（オープンコンテスト） | AtCoder
CODE FESTIVAL 2015 解説 - SSSSLIDE

5. dwango プログラミングコンテスト B: コメント

*3の問題をあまり見かけない．
B: コメント - dwangoプログラミングコンテスト | AtCoder

まとめ

グラフ理論系の問題は実装が楽しいものが多くて好きです．
なんか最近の問題が多くて申し訳ない感じになりました．
手を付けてない組み合わせ系の問題に取り組みたい．






以下，問題の解法ネタバレ．

*1:二分探索

*2:最短経路問題

*3:フロー

2016年の目標

競技プログラミング

・Topcoder/Codeforcesの問題を解く．
・Div1入り

英語

・TOEIC 730点以上
・単語帳やる

その他

・何か2つ作る

課題を締切直前までやらずにいて痛い目を見たので，計画性を持って行動出来るようになりたい．
頑張る．

2015年振り返り

こんな目標を立てていたらしい．
2015年の目標 - utsubo’s diary

競技プログラミング

レート等

  • SRM　(903 -> 1165)
  • Marathon Match　(? -> 864)
  • CodeForces　(1440 -> 1702)
  • CODE FESTIVAL　(138位 -> 91位)
  • CODE RUNNER　(65位 -> 46位)

目標

  • SRM Div1 入り　✕（まだだめそう）
  • オンサイト　◯（CodeFes出れて良かった）
  • 蟻本読了　✕（目標自体を忘れてた）
  • CF出る　△（5回しか出てない）

若干成長できたのかなぁ．正直，誤差の範囲だと思ってます．
達成率は40％ぐらい．

英語

目標

  • 洋書読む　✕（目標自体を忘れてた）
  • 洋楽聞く　△（聞き流しは多少）

洋楽は前よりかは聞いたから，達成率は20％ぐらい．

その他

目標

  • 何かしらで2つ以上作る　◯（まだまだな部分もあるけど）
  • ラブライブの声優に1人以上会う　✕（こんなのも立てていた）
  • 大学の特待生制度で15万貰う　△（だめです）

まずまず．

雑記
  • 某社ツアーが最高でした．ほんと感謝．
  • そろそろ分野絞ってやらないといけないと強く感じます．
  • 各方面に迷惑をかけまくった一年だった．

今年も大変お世話になりました．2016年目標に続きます．

ACするとLEDがピカピカ

作ったもの

AtCoderのコンテストでACするとLEDが点滅する奴を作ってみました．こんなの↓

構成

Pythonで提出状況を取ってきてパース，正誤をシリアル通信でArduinoに送っています．
ArduinoではACであれば点滅，それ以外であったら点灯するようにしました．（他の色があれば，色を状態によって変えたかったのですが，手持ちになかったので...）
f:id:utsubo_21:20151225223411p:plain

pythonはシリアル通信にpyserialとhtmlパーサーにbeautifulsoupを使用．
beautifulsoupがよく分かってないので適当．
procon_led.py · GitHub

Arduinoは基本的なコマンドのみ．
serial_test · GitHub

まとめ

PythonとArduino便利！