みんなのプロコン2019 予選 参加記

はじめに

JOI会場から参加しました 時間めっちゃギリギリで、自分の部屋からテザリングでやりました 遅刻しなくてよかった

本番の流れ

解いた

A 通した むずかしい
B 通した 嘘っぽくてこわったけどOK
C 通した これめっちゃ難しい B-Aで場合分けすればOK ここで16分 順位冷えて萎えた
D 通した ここまでで34分 その時点では52位で暫定パフォ2700ぐらい出た 優勝！ｗ

風呂に入った

バスタオルを忘れかけたりしましたが、大丈夫でした なおっぴーくんありがとう
風呂、とても気持ちよかったです(ここまでで70分弱経過)

また解いた

風呂の中でE考察したけど無理そうだった
で、EもFも風呂上がりにめっちゃ解かれてて怖かった ので、考察しないといけないと思った

EよりFの方が明らかに人間向け ツイッターしながら考察する
なんかi回目にj個目の赤い球を置けるか、とかで500点ぐらいの自明DPができそう 実装めんどい
とか言ってたら某氏が900通した うっわ怖いってなって自分も通さないといけない気分になった

通した 900点は初AC やったー！！！！！

で、今はツイッターやりながら参加記書いています 残り10分 ちゃんとコンテストに集中しような

おわりに

たのしかった 結構温まった(風呂に入ったので) JOI本番でもあたたまる予定です。各位震えて待て

第18日本情報オリンピック(JOI2018/2019)本選 参加予定記

はじめに

まだ参加していないのでこの通りになるかはわかりません。

当日の流れ

土曜日は秋葉原でお昼ご飯を食べてからつくばに向かう予定です。知り合いがたくさんいて楽しいはずです。あと雪が多分降ってます エモい
プラクティス、強い人たちが爆速で通してから立ち話を始めてすごい面白いと思います。持ち込んだマスコットがかわくて、精神に優しさをもたらしてくれる予定です。
夜はみんプロに出ると思います。ギリギリの参加になると思いますが多分レートが上がるはずです。

日曜日の本選、ぼくは3完+部分点を取る気がします。本番は1と2を40分ぐらいで通して、自明部分点を取ってから1時間ぐらいかけて3を通して4の考察、って所で時間切れになるはずです。難易度は5-7-8-10-12ぐらいになるのではないでしょうか。

結果

多分Aランクです。対戦ありがとうございました。

モザイクアートをしよう

はじめに

　この記事はプロコンゼミ(SPC同好会) その２ Advent Calendar 2018 23日目の記事です。

また、この記事はCombMofで発表したスライドとほぼ同一の内容について扱っています。

スライド

これです

ないよう

　上のスライドを見てください(書くことがないよう＞＜)

真面目な内容(補足)

上のスライドに載ってない内容をかきます、発表スライドの補足としてご覧ください。

焼きなましについて

　「競技プログラミングっぽい事をしたい」「ビームサーチをする」の辺りで感づいて言及していた人を複数人観測しました。が、今回の発表では焼きなましの話をしませんでした。(ごめんなさい)
今回の発表で焼きなましを採用しなかった理由は簡単で、適当に焼きなましても山登りより悪い評価しか出ないからです。

焼きなまし法では評価が下がる方にも遷移をする事がありますが、山登り法より良いスコアを取るためにはスコアが悪化した後の遷移でさらに良い評価を獲得する必要があります。
今回は焼きなましでも山登りでも取る近傍を「ランダムに1枚画像を選んでランダムに選んだ画像と入れ替える」としています。 この近傍の取り方だとなんか無意味なスコアの悪化ばっかり出てきてしまってスコアがあまり良くなりません。かなしいね。詳しい説明をしようと思ったのですが現在時刻が12/23の23:40です。あと20分以内に公開しないといけません。時間が足りません。

スライドの内容について

　今回の発表スライドの内容は割と無難なものになっている気がします。理由は簡単で、マサカリが飛んできたりスベったりしたくなかったからです。
ちなみにスライド作成にはこれを使いました。適当にやってもいい感じのスライドができてよかったです。

画像の前処理について

　スライドでは説明をしていなかったのですが、各画像毎に特徴量を前計算する事で高速に探索をさせるようにしています。特徴量の計算には様々な手法がある気がするのですが、今回は画像をぼかしていくつかの画素の色を取る、みたいな感じでやっています。もちろん他にも方法はいろいろあります。

†パラメータ最適化†について

　最近流行りのoptunaさんを使ってパラメータを最適化する事にします。(えらいので)(ネタになるので)(流行に乗りたいので)
今回のプログラムに用いるハイパーパラメータは特に存在しない(かなしい)のですが、焼きなましをする際の開始/終了温度ぐらいなら最適化できそうです。とりあえず温度を引数に計算をしてから評価値を返す関数を用意して、optunaさんに投げてみます。これすごい簡単に実装できるのでよいです。マラソンのパラメータ調整にもってこいだと思うので、みなさんも使ってみるといい木がします。

プログラムを書いたので実行して最適な温度を調べてみました。結果的に温度が低ければ低いほどよい事がわかりました。ようするに評価の下がる遷移はやめた方がいいという事になります。これはつまり焼きなましがあまり意味を持ってないという事ですね。死

二部マッチングについて

　発表の終了後にけんちょんさんから教えて頂いた話なのですが、同じ画像を1枚しか使わない場合のモザイクアートの作成は二部マッチング問題に帰着できるらしいです。(すごい)
片側を元画像(大きい画像)の一部分、もう片側を素材画像(小さい画像)とし、全てのペアについて色差を重みにした辺を張る、みたいな感じにして最大重みの最大マッチング問題を解けばいいらしいです。すごい(ここ間違っていたら指摘おねがいします＞＜)

おわりに

これを書いている時点で12/23の23:58の30秒です。あと90秒で公開しないと遅刻扱いになってしまいます。急いでPublishボタンを押すことにします。こんな記事を見て頂き、ありがとうございました。

第18回日本情報オリンピック予選 参加記

はじめに

参加してきました。 ABCDEの5完+f部分点で520点でした。

ここに本番の流れや解説、完走した感想をまとめます。

本番の流れ

開始から10分でABCを順番に解いていきました。 0WAでした。
次にDを解こうとするとWAが生え、(解法が同じで通した人がいるため実装ミス？)改善するのがつらかったためUnion-Findで殴りました。 EはO(N²)のDP解しか思いつかなかったためそれを実装していた所、1次元DPにしても問題ない事がわかりそれをしました。ここまでで42分でした。

Fは満点解がわからなかったため部分点狙いでO(N³*4^N)ぐらいのものを生やしたのですが、それの実装を無限にバグらせ続けて険しかったです。
開始100分弱の辺りで投げ、6点を取りました。20点分のパートでMLEを出していたためDP配列の次元を落として(空間計算量のみを落として)改善、20点を取る事ができました。

その後は何もわからなかったため80分間椅子に座り続けました。とても疲れました。

(解けた問題の)解説

現時点ではまだ問題文が公開されていないのですが、気合で読んでください。

1問目

算数ができないので愚直にループを書きます。

2問目

O(NM)かけた愚直シミュレーションでいいです。2020に番兵を置くと実装が楽です。

3問目

1次元DPをします s[i]とs[i+1]が異なるならdp[i+2]=max(dp[i]+1,dp[i+2])をすればよいです。

4問目

両隣より高い or 両隣より低い地点だけを気にしながら累積和をすればいいような気がしましたが、WAでした(実装で失敗してたみたいです)
地点を高さ順にソートしてからUnion-Findに突っ込んで、海面の高さを小さい方へ動かしながら[海面の高さより高い地点にある島の数] - [Union-FindのUnite操作で併合されたものの数]の最大値を取るといい感じに解くことができます。(標高が0の地点が陸地になる事はないので、そこだけ注意)

5問目

「dp[i]:i番目まで見た時の最大値」みたいなよくあるDPをしようとすると考えるた場合、LiとRiの制約は「[Li,Ri]にあるものを選んだ場合はdp[Ri+1]に飛ぶ」みたいな感じに置き換える事ができるのでそのまま1次元DPをする事ができます。
飛ぶ先の地点について事前計算をしないといけないため、区間max + 区間更新(ただし更新前の値の方が大きい場合は値を更新しない)を行えるセグ木を貼りました。(実際は累積maxを取るだけで大丈夫らしいです。)

6問目

部分点(小課題1,2の20点分)しか取る事ができなかったため、それについてのみ解説します。

小課題2はNが10以下、Aの最大値(表記が面倒なのでこれに1を足した値をAとします)が3以下と相当緩くなっていて、これの制約でなら"どの国の参加者を何人置いたか"(状態数がA^N)をDPの状態に保持する事ができます。
また、席の左側から埋めていく事を考えると保持すべきなのは前述した情報 + 一番右側にいる人の国籍 のみで済む事もわかります。 そのため、「dp[i][j][k]:左からi個目の席まで埋めて一番右側にいる人の国がjであり"どの国の参加者を何人置いたか"の情報がk」でDPをする事ができます。
遷移をさせる際右端の席に入れる参加者の国籍を全探索するため、計算量はさらにNがかかってO(N³*A^N)となります。(席の数は最大で3Nとなるのでそれの定数倍もかかります)
これは見た感じかなりヤバそうなのですが、dp配列の空間量を1つ落としたりするとなんか通りました(計算量解析ができません…)

完走した感想

思ったより順位が高かった(おそらく3位タイ(？)で把握してる範囲で同点がたくさん)のでうれしかったです。ここまで取れば流石に予選落ちはないはずです。
かなり良い得点を取れたため自分自身に自信がつきました。といっても今回は運が良かった方(問題セットがぼくに合っていた)なので、気を抜かず本選まで精進を続けていきたいと思います。
ボーダーは385±30点程度になると思っているのですが、実際はどうなるのかとても気になっています。弊の人や知り合いがたくさん通っている事を願います。

(ボーダーが521以上でなければ)本選もがんばります。ここまで見て頂きありがとうございました。

第18回日本情報オリンピック予選 解説

まだ問題が公開されていないため解説できません
全完できなかったため解説をする事ができません ごめんね

クリスマスも近いので福笑いをしようと思った話

はじめに

　この記事はプロコンゼミ(SPC同好会) その１ Advent Calendar 2018 3日目の記事です。

　部内Advent Calendarは去年に引き続いて二回目になります。うちの部員が真面目な記事を書いたり旅行をしたり数日分遅刻をしたりして面白いと思うので、ぜひみてください。
ちなみにその２も存在しており、自分は12/23分を担当しています。そちらは同じく12/23に開催されるCombmofで発表するものと同じ内容にする予定ですが、こちらもよろしくおねがいします。

やったこと

　人物画像を渡すと福笑い(大嘘)ができるアプリケーションを作りました。いえーい

やってる事は下画像を見ればだいたいわかると思います(lena.pngさんごめんなさい…)




　福笑いは正月に遊ばれる日本の伝統的な遊び(Wikipediaより)です。のっぺらぼうになっている顔の上に顔パーツを載せて、おかしな顔になっているのを見て笑う遊びだそうです。12月は実質1月でお正月みたいなものですしちょうどよいですね。

使ったもの

・Qt(UIをこれで書きます C++をします)
・dlib(機械学習のライブラリです Pythonをつかうことにします 顔認識をするために必要です)
・OpenCV(のっぺらぼうにする処理やパーツを取り出す処理など、画像加工に使います これもPython側でおこないます)
・Flask(これなんで必要なんですか？うぇぶ要素を強引にはさむ必要はないとおもいますが…)

実装の流れ

　まずはQtのアプリケーションで画像ファイルをよみこみます。その画像をPOSTしてFlaskに投げ(なんで？)、Python側でよしなに画像を加工して、それをQt側にかえします。(Flaskいる？boost.pythonとかでよくない？)
あとは返ってきた画像をQtで表示して、顔パーツのドラッグと拡大縮小、回転を実装すればおわりです。

　Python側でのdlibを用いた顔認識ですが、調べるといろいろ出てくるのでここでは説明をはぶきます。(正直なところコピペしただけです ごめんなさい)

　その辺に落ちてるやつをコピペしたら顔パーツや輪郭の情報が頂点の配列になって出てきたので、それを使っていろいろやります。
各顔パーツについてですが、頂点情報をもとにfillPolyをしたマスクデータを作って、bitwise_orをした後にresizeするだけです。OpenCV全然わかんなくてもできたので、かなりらくでした。
　顔ののっぺらぼうを作る時はまず輪郭(とか認識できた顔パーツとか全部)の凸包をとります。頂点が順番にならんでなかったりしても凸包すれば優勝！ｗなので、らくです(OpenCVに関数があるのでやるだけです OpenCVにはなんでもあるなぁ)
その後に輪郭のちょっと内側にある点の色(要するに肌の色)をいくつか抽出します。そして凸包のなかをその色たちで埋めてしまって(ランダムに点をたくさん打つやつをしました)、ぼかし加工とかをした後に元の画像につっこみます。よくわかんない加工をしたらマシな感じになったので、まぁいいんじゃないでしょうか。(？)

　GUIですが、Qtを使うと優勝ができてよいです。画像を読み込んで表示、クリックされた場所のピクセルが透明じゃなかったら(これパーツ数だけ計算されるけどまぁ問題なさそう)ドラッグして画像移動、キー入力で拡大縮小と回転をします。行数が少なくて精神にいいです。

　ネットワーク関連、たいへんです QNetworkRequestとかQNetworkAccessManagerとかQNetworkReplyとか、なにもわからないのでたいへんたいへんでした。
　Flaskも5億年前に3秒触った程度のことしかわからないので、たいへんでした そもそもこれ、なんでlocalhostないでPOSTとかしてるんでしょうか？なんで？boost.pythonでファイル受け渡すかそもそもGUIもPythonで書くのが最適っぽい気がします なんでこんな所で消耗してるんですか あほじゃない？

感想

　画像をいろいろ加工するところとかなぜかネットワークの勉強をするところとかソースコードをコピペするするところとか、いろいろ勉強になってよかったです。
　12月に入ってからAdventCalander用のことに手をつけ始めて、結果的に土日を使ってこれを実装することになりました。ぼくにしては働いたほうじゃないでしょうか(？)(ほめて)

　久々に期限ギリギリのデスマーチ気分を味わえて、いい気分転換になりました。ところで今日12/3はテストの最終日です。ぼくはいま12/2の22:30にこの記事を書いていて(追記:いま23じになりました)(追々記:いま記事を書き終わりました 23:55です)、これから記事内容の付け足しとか手抜き部分の一部修正とかきょうのABCの解法確認とかをやってから0:00に記事を投稿する予定なのですが、勉強するじかんはありますか？ありませんね… かなしい
落単で落胆しないようにがんばります。もし落単したら「部活の強制労働のせいで単位が落ちたはなし」を書くよていなので、各位そちらもよろしくおねがいします。

　最後にうちの部員の顔面で福笑いをした画像を載せておわりにしたかったのですが、うちの部員に眼鏡オタクしかいないので福笑いができませんでした…部員各位はもっと福笑いしやすい顔になってほしかったです。
　あとこれたった今気付いたんですけど、これ選択中の顔パーツが隠れるわけでもないし目隠ししてやらないと福笑いにならなくないですか？これ福笑いじゃないじゃん…

おまけのおまけ

　あなたはQt for WebAssembryについて知っていますか？知っているあなたはえらいです 知らなかったあなたも今知ったので偉くなりました 偉いです

細かい説明をするとマサカリが飛んできそうなので省きますが、Qt for WebAssembryを使うと、C++のQtで作ったアプリケーションをそのままブラウザ上で動かす事ができます。(表現のしかたで怒られそうだけどゆるして＞＜)
つまり、これを用いることでぼくが今書いたプログラムをそのままWeb上に公開できる(語弊アリ)わけですね。すごい
実はわざわざC++のQtで書いたり謎の采配をしていたのはこのためで、この機会にWebAssembryを試してみた上でネット上に公開しようと考えていた訳です。


さて、という事で今回のプログラムをブラウザ上で動作させてみましょう。Qtのwikiに詳しい解説が置いてあったり日本語の情報も(少しは)あるので、それを見ながらファイルのダウンロードや操作をしていきます。
最終的にはQtプロジェクトのproファイルをqmakeにかけて、make allでコンパイルする事でhtmlやjsファイルが生成されます。

自分のプロジェクトで正常にqmakeとmakeを終え、htmlファイルが生成されました。では、実行をしてみます。下に結果の画像を添付するので、そちらをご覧ください。

おわり

最近レートがあがらない…なんで？原因を分析してみた！！！！

はじめに

どうも、塚本です！！！

みなさんは、なぜかレートが上がらない現象が続いていて困っているみたいな事はありませんか？




私もちょうどそうなっていて、最近はレートが上がらなくて困っています。

そのため、このような状況を脱却するために

  レートが上がらない原因は何か？

について、考えてみました！

レートがあがらない理由

調べてみた結果、以下のような原因がある事がわかりました！！！

・高いパフォーマンスを取れていない

・レートが上がるとレートが上がりづらくなる

・コンテストにあまりでていない

・精進をしていない

これらの原因について、なぜこのような事になっているのか考えていきます。

高いパフォーマンスを取れていない

実は、パフォーマンスが高いほうがレートが高くなりやすいです。

残念ながら、最近のぼくはあまり高いパフォーマンスを取れていません・・・
そのため、レートが上がりづらいようです！

レートが上がるとレートが上がりづらくなる

基本的には、レートが低いほどレートが上がりやすいです。

レートが上がらなくて困っている…みたいな人も、それは自分のレートが上がったからです！

そのため、焦らなくても大丈夫です！！！！！

コンテストにあまりでていない

どこかで聞いた事のあるはなしですが、コンテストに出なければレートは変化しません。

そのため、まずはコンテストに参加する事が大事なようです！！！！

精進をしていない

コンテストの過去問を解くことで、レートが上がりやすくなります！！！

個人差もありますが、1問も解いていない人より1000問解いた人の方がレートが高いです。

おわりに

いかがでしたでしょうか？今までの話をまとめると、

コンテストで高いパフォーマンスを取る！

事が、レートを上げる事につながるようです！


このような記事を見ていただき、

ありがとうございました！！！！！

ごめんなさい