第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問解いた人の方がレートが高いです。

おわりに

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

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

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


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

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

ごめんなさい

ねこちゃんが

かわいいです

週末にジャッジシステムを自作しようとした話

はじめに

先週の金曜日にジャッジスステムの制作欲が湧いてきたので、作ることにしました(迫真)
平日は忙しいのでとりあえず週末2日での実装を目安に、手元環境で動く所までを目標に頑張りました

金曜日時点での構想(原文ママ)

Pythonとかイケイケな言語とDockerを使って遊びたい
curlでpostしたらレスポンスが返ってくる、程度でいい
問題文(TeXとか使うやつ)とテストケースをjsonで投げると自動で問題が追加されるぐらいのはやりたい

ぼくのぎじゅつりょく

web系と呼ばれる分野が誇張でもなく全くできません
JavaScriptで世界に挨拶する事ができません
webページやサービスを作った事がありません

できた事

flaskさんを使ってlocalhostで動く(は？)webページと自動ジャッジシステムを作れました はい
問題一覧から個別ページに飛んで、提出欄にコードを貼ってSubmitすればレスポンスの確認が可能、みたいな必要最低限の機能まではできました

・提出ファイルを保存してジャッジ環境でコンパイル、実行からの出力確認とRE,TLE捕捉ができた
・問題提出フォームから形式の合ったjsonファイルを投げると自動で問題を追加してくれるようにできた
・問題のjsonを読んで数式表示やサンプル表示まで含めいい感じにやってくれる物をつくれた
・ジャッジ用のプログラムと本体部分(外から見えそうなやつ)を分けて実装できた
・bootstrapさんを使ってまだマシな(メニュー程度はあるよ！！！！)ページが生成できた

できなかった事

・localhost以外で動かせていない
・セキュリティがわからない
・OLE,MLEが捕捉できない(！？)
・例外処理が書けない
・Dockerで動いてないし、そもそもプログラムを分けただけ
・ファイルをローカルにそのまま保存するのをやめろ

など、上に書いてない事ぜんぶができていません…

開発の流れ

web系の開発で使えそうな言語の中で自力で"Hello, World!"できるのがPythonしかありませんでした よってPythonを使います
なんかFlaskってやつに聞き覚えがあって、それを使うとイケイケな開発ができそうでした Flaskを使う事にしました

1日目

まずはCLI側からソースコードをファイル形式でPOSTして、それを受け取ってみる事にしました この辺は結構楽しかった(バグが辛くないので)
とりあえずそれを†ローカルに保存†して、subprocessさんを使ってコンパイルさせてみました ちゃんと動いてくれたので嬉しい
標準入力と標準出力のサンプルを迫真の†Hard Coding†で打ち込んで、subprocessで実行した結果とdiffを取ってみました そんでもってこの結果もローカルにtxt形式で保存します(は？)(データベースがわからない)(なにもわからない)

これでCE,AC,WA,RE,TLE辺りは取得できるようになったので(メモリ使用量はどうした)、問題のjson形式による読み込みをやります
問題文、入出力、制約とかをまとめてjsonにして、それをPOSTで送りつけられるようにします
問題一覧もローカルにそのまま保存して(頭がわるすぎる)、問題idに対応するURLにソースをPOSTする形式に変更しました

ここまでが一日目にやった事です CLIからジャッジできるようにはなったけど実用性は皆無で、とてもかなしいです
ここからwebページのおべんきょうをして、最低限使える物にしていきます

2日目

上で述べた通り、ぼくはwebと名の付く任意のものがわかりません とてもつらいです
Flaskではjinja2って名前のイケてる何かを使えるらしいので、Qiitaとか見ながらがんばります
表示はbootstrapを使うとめっちゃエモい超近代的な物を作れるらしいので、それともサンプル見ながら格闘します

データ取得してhtmlに反映するやつができました
取得したデータはrender_templateから渡してjinja2でよしなに出力します
今の状態だとデザインもクソもない悲しすぎるやつなので、bootstrapさんにメニューとか各種のボタンとかを丸投げします
問題ページぐらいはマシな物にしたかったので、jsonから整形して問題文やサンプルの表示、MathJaxを導入して数式表示辺りをできるようにしました

結果

なんかこういうのができました

反省

ローカルにそのまま保存するのをやめろ(素振り)ローカルにそのまま保存するのをやめろ(素振り)ローカルにそのまま保存するのをやめろ(素振り)ローカルにそのまま保存するのをやめろ(素振り)ローカルにそのまま保存するのをやめろ(素振り)
ジャッジの隔離もしてないので悪意のある提出で死ぬ 間違えてデバッグ出力消さなかったらそれだけで多分死ぬ というかMLEの確認すらしていない
jsonの形式間違ってたら多分落ちる よくない
メモリ使用量も実行時間も表示してないので結構かなしい事になっている というかwebページの作り自体がかなしい

うれしかった事

実態はどうあれ2日で動く物ができた
うぇぶがまったくわからない人間でもなんとかなる(？)事が分かった

Re:AtCoderで青色になるまでにやった事とかをまとめる

前回までのあらすじ

1.この記事を参考にして水色になりました。

2.この記事を参考にして青色になりました。

3.この記事を参考にしたら水色に戻りました。

はじめに

こんにちは。7/1のARC100で無事青色に戻る事ができました。やったー！
流石に二回連続でクソ記事を生成するのも良くないので、この記事ではARC100の参加記と考察を書きます。

記録

ARC100では176位でパフォ2086、レートは1544から70上がって1614(highest)になりました。
CEの2完で1000点、提出情報はこんな感じです。

Submission #2775185 - AtCoder Regular Contest 100
Submission #2775990 - AtCoder Regular Contest 100

コンテスト中の経過

コンテスト開始と同時にCを読みました。問題文が難しかったので理解するまでに3分ぐらいかかってしまいました。
でも解法はよくわかりませんでした…

ちょっと考えてbの値を決めた時の悲しさの値のグラフが凹のような形になる事は分かったのですが、そのような問題を解くのに便利な三分探索のライブラリを持っていませんでした かなしいね
検索をかけて調べてもコードがそのまま載っているサイトは(検索上位の数ページでは)無かったし、自分で書くとバグらせそうなので諦めました ここまでで約10分(は？)

そこからDとEの問題文を読んだのですが、これもよくわからない…
DはJOIにいくつか類題(いくつかに切って最小値や最大値を求める問題)があったので、とりあえずそっちの問題を見ながら進めていきました。
類題として思い当たったのが水ようかんやバームクーヘンなどで、前者は切り分けた時の最小値と最大値の差、後者は円を分割した時の最小値の最大化を求める問題でした。
水ようかんの方はとても似ている問題だと思ったので解説を見たのですが、どうやら計算量的に間に合わないらしい かなしい
バームクーヘンはO(NlogN)ぐらいで解けるらしく、そちらの解説スライドを見る事にしました。

とりあえずそれに載っていた「最小値を決め打ちして累積和にぶたんをして貪欲をする」みたいな方法を試してみましたが、"3 2 4 1 5"のようなケースでWAを吐いてしまい断念
そもそも最小値の最大化と最小値と最大値の差は全く別物なので、かなりのガバでした…

想定解だった「真ん中の値を固定してにぶたんorしゃくとり」は思いついたのですが(負け惜しみ)、2つに分割した中でさらに半分になるように切ると答えが出る、という部分に正当性を感じられなかった(ここもガバ)ので諦めました 見返すとガバばっかりだなお前

という事でDは諦めてE問題へ向かう事に この時点でNoSubのまま50分ぐらいが経過していたので、最悪このまま未提出レート変動0でもいいかなとか思ってました
見た目と制約を見るとなんとなくbitDPっぽい…それっぽくない？ みたいなお気持ちだったのでとりあえずbitDPをする方針に決めました。

まずは仮にK=6のケースについて考えてみます。
Kは2進表記で110なので、2進表記でi={000,010,100,110}になるAiの中から値の大きい二つの和を出せばいいような気がします。
しかし、その考え方だとi,j=(1,5)になるようなペアを選んだ時に総和が最大になるような数列が来た時に正しい答えを出す事ができません。
そこで、Kが小さいものから埋めていってその累積maxを取る事にします。累積maxを取る考えはサンプル2やサンプル3を合わせているうちに自然と湧く気がします。

ここまでで、各Kについて(i or j) and ~K が0になるような(i,j)の組のうちAi+Ajが最大のもののペアを取ればいい事が分かりましたが、肝心の(i,j)のペアの求め方がわかりません。
とりあえずdp[i][j]:kを「i and ~k == 0を満たすAiの中でj番目に大きい値」としてみます。
この場合、dp配列の添字jの部分は2個しか取らなくてよく、添字iの部分は2^N個取る必要があるので、O(2^N*(一回の遷移にかかる計算量))ぐらいでDPができそうです。

肝心の遷移については配るDPで、「0<=K<Nを満たす各Kについて、dp[i|(1<<K)]の部分にdp[i][0]とdp[i][1]を割り込ませる」みたいな感じの事を考えてみます。
もしdp[i|(1<<K)][0]よりdp[i][0]の方が大きかったらdp[i|(1<<K)][1]=dp[i|(1<<K)][0]としてdp[i|(1<<K)][0]=dp[i][0]とすればいいですし、dp[i][1]についても同様に遷移ができます。
しかしこのような取り方をすると、A0が最大になるようなケースでdp[8][0]とdp[8][1]の両方がA0になってしまうような問題が起こります。同じ値が来た時に回避させたいならif(dp[i|(1<<K)][0] != dp[i][0])のようにすればいい気もしますが、数列の複数の要素が同じ値を取っている場合に問題を起こしてしまいます。
そこで、dp[i][j]:kを「i and ~k == 0を満たすAiの中でj番目に大きい値のindex」と変えて重複対応をしてみると綺麗に解決させる事ができます。

ここまで書いてサンプルを合わせたら後は提出のみ、なのですが開始80分を過ぎた後の初Submitは心臓に悪かった…
これで落ちたら最悪太陽だったので、通った時は本当に安心しました。

さて、このままだとE<CDで負けてしまうのでCを通す事にします。CE>CDなのでそこさえ通せれば順位もレートも爆上げなはず…！
落ち着いて考え直してもまぁ三分探索っぽいなぁ…って感じだったので、インターネッツから他人のライブラリを盗んでくる事にしました。
判定関数の実装部分はとても楽でバグらせる事はなかったのですが、初期でのbの範囲設定を[0,INF)とかにすると最後のサンプルが合わず普通にWAを吐くので注意しましょう…計算量にも余裕があるので[-10¹⁸,10¹⁸]を初期範囲に持った三分探索をしました。

これでCも通して2完、CD2完の人より高い点数なので順位も爆上げで精神に優しかったです 0完太陽じゃなくて本当によかった

おわりに

また水色に落ちたら記事を書く予定です お楽しみに！