うにゅーん、って感じだ

だいたいのコンテストサイトで橙か赤です、よく C#を書きます。

三角形はいくつ？ 雑記

Advent Calender Contest yukicoder

これは
ひとり Advent Calendar 2016 - Adventar
の14日目の記事です。



アドベコン2016の12日目の問題を担当させていただきました。

www.adventar.org


問題はこちら
No.461 三角形はいくつ？ - yukicoder


問題概要としてはパズル的なのでよくある、線をいっぱい引いた図形の中に三角形がいくつあるか数えるものです。




さて、解法としては、直線を3本取ってきたときにその3本で三角形が描けているか、を判定してあげればいいです。



判定方法についてですが、まず3本が1点で交わるとダメです。また、3本の互いの交点のうち一つでも最初の大きな三角形の外側にある場合、3本は最初の大きな三角形の中のみ伸びてる線分なのでこれも三角形となることができません（日本語が下手）。


実は、この2点をクリアすればその3本は必ず三角形を描けています。



次はこれを実際にどう判定するかですが、
{\displaystyle q_i = \frac{b_i}{a_i + b_i}}
という値に注目すると、
前者は3本の {q_i} の和が1であるかどうか、後者は3本のうち任意の2本に対して {q_i} の和が1より大きいかどうか、にそれぞれ対応しています。
（これはもちろん {\displaystyle \frac{a_i}{a_i + b_i}} という値に注目してもほぼ同じように解けます）


この判定を全組み合わせに対して調べれば、とりあえず {O(N^3)} で解けます。ただ、2本を確定させたとき、もう1本に対して3本の {q_i} の和が1になる線分があるかどうかと、任意の2本の {q_i} の和が1以下のものがいくつあるか、というのは {q_i} の値でソートしておけば両方 {O( \log N)} で解け、結果 {O(N^2 \log N)} となります。

（うまくしゃくとりとかすると {O(N^2)} になります）





これは最初 {O(N^3)} が通る制約で★2で出す予定でした。ただ、アドベコンの周囲の問題の難易度を眺めているとどうも★2が多そうだったので（ただこれは罠でその後みんな★3に昇格した）{O(N^2 \log N)} に制約を変えて、ついでに誤差を {10^{-16}} 程度まで小さくして分数で足したりソートしたりしてもらうようにしたりとか、{N = 4000} にしてオーバーフローを誘ったりしました。


ただいくつか誤算があって、まず、long double は仮数部が 63bit あるので、long long の範囲では誤差が出ない、ということ。これは出題前に気づいていました。本当は浮動小数点数を使った解答を全て誤差死させたかったのですがまぁ致し方なし。double がほぼ全て落ちるだけでも僥倖みたいなところがある（ちなみに C# には double より精度の高い浮動小数点数型が存在しないので分数解しか通らない、はず）。


次に、変に {N = 4000} とかいうギリギリを攻めたせいで TL が少し厳しくなってしまったこと。これは kimiyuki さんにテスターをしていただいた際に明るみになりました。まず、Python ではナチュラルな {O(N^2)} が TLE するらしくもうびっくりという感じなんですけどまぁこれは置いといて。問題は、分数クラスがちゃんとしていて毎回約分するようなものだと毎回 {\log} がかかって 5sec でも TLE することがあるらしくにゃーんという感じでした。

それと相反して {O(N^3)} が通っていたりもして、それは本当にびっくりなんですけど。というのも、オーバーフローをさせる関係で今回ちゃんと最大ケースを作っていて。しかもそれの答えが 23億 とかで。でも一つ一つ数え上げて 4sec ちょいで通っていて。もうC言語ってなんなんだよ、という感じ。

それと★4に昇格したのも誤算の一つで。おそらく {N = 4000} のせいで解法が {O(N^3)} の全探索から一つ {\log} に落として高速化、というプロセスを辿りづらかったのかも？ 部分点というか部分ケースがあってまずそっちが通るかどうか試す、みたいな方針でいったらもう少し楽に解かれたのかも。そもそも {O(N^2 \log N)} が通る制約に見えなくてずっと {O(N \log^2 N)} 解を考えてた、とかがあったらめっちゃ申し訳ない。



でもまぁストックのクソ問が思ったよりいい感じな問題になった（ほんまか？）のでまぁよかったかなぁ。とは言ってもストックのクソ問の中でもまだマシなほうなので残りのストックは本当に日の目を見ることがないかも……。

ハルコン2016 参加記

ハルコン

これは
ひとり Advent Calendar 2016 - Adventar
の8日目の記事です。




カービィやスマブラなどで有名なハル研究所が開催していたプロコンに参加していました。

www.hallab.co.jp


期間は11/7 ~ 11/25 で2週間以上あり、まぁいわゆるマラソンマッチです。
私がコードを書き始めたのは多分11日くらいなので、ちょうど2週間くらい参加していたことになります。



最後に順位表を見たときは6位だったので、再評価でいい値が出たり上がコケたりしてくれれば、賞金がワンチャンありうるかも…？



こちら、提出したコードにめっちゃコメントを書いたものです。読んで。

ハルコン2016でのrian_tkbのコード · GitHub

そのうち、自分の方針をまとめた解説記事みたいなのも書きたいと思ってます

（マラソンやったことないのでビームサーチとか焼きなましとか言葉しか知らないので、今回も盤面評価すらしていないので多分他の人とは方針が全然違いそう）



以下、期間中の関連ツイートを適当にまとめたもの


C++書けないマンとしてはな


誤差の処理とか、ちゃんとREADMEに書いておいてほしかった（コードを読解した）
C++書きたくないマンとしてはな
最初、1ターン目からビームが打てて、かつ次に打てるのがその40ターン後だと思っていた、けわしい
（実際には、最初にビームを撃てるのは40ターン目で、次に打てるのはその41ターン後）
ようやく主なバグが取れてまともなスコアが出る

普通のオンラインジャッジみたいに1ケースずつ動かし直してると思ったら1回で200ケースまとめて動かしてたでござる
探索の深さを増やすようにして2位まで更新
（この時期ですでにhirokazuさんは58000台を出してたのか…）
かっこいい…
2円の共通接線はめんどいので結局別の方法で解決しました
無限にバグが仕込まれているのでもうダメ
2位争いが熾烈になり、程なくして置いていかれる
これも地味につらかった
このツイートをしたら翌日には修正が降ってきてて、もしかして監視されてる！？ ってなった

C++書けないマンとしてはな

めっちゃTLE

残り1日を切り、更新できず賞金ボーダーから置いていかれて焦る

残り1時間を切ったタイミングで、乱数で回数を回す方向にシフトしたら突如として6万を切り、なんやねんって言う
終了直後の方針ツイートとか色々




初心者が作問して思ったこととか

これは
ひとり Advent Calendar 2016 - Adventar
の6日目の記事であり、かつ
Competitive Programming Advent Calendar 2016 - Adventar
の6日目の記事でもあります。



簡単な自己紹介とか

競プロアドベントカレンダーに載せさせていただくので多分5億人くらいが見てくれるだろうと予想して、少し自己紹介を書きます！

いま大学3年で、競プロを始めたのが大学入ってすぐくらいだったので、なんだかんだ2年半くらいやったことになります。
コード祭り本戦には3回とも出ていて、2015だけパーカーをもらえました。

SRM

https://www.topcoder.com/members/rian/details/?track=DATA_SCIENCE&subTrack=SRM
https://competitiveprogramming.info/topcoder/srm/history/rian

最近低迷していて、今はギリギリ黄色です。
Div1Easyが解けないことに定評があってつらい。

一番成績の良かった回は0完7撃墜350点です。
https://competitiveprogramming.info/topcoder/srm/round/16776/div/1

Codeforces

riantkb - Codeforces

最近始めました。ギリギリdiv1。
一応調子が悪くなければ2完できるみたいな感じっぽいしdiv2に落ちたくない。

AtCoder

https://atcoder.jp/user/riantkb
http://kenkoooo.com/atcoder/?kind=user&name=riantkb

黄色です。writer権はちょっと得られそうにないです。
前はけっこうちゃんと埋めてたんですけど最近はとてもサボっていてダメ。

作問履歴

yukicoderの方で何問か作問をしました。
りあん🐺☔️⛄️さんの問題一覧 - yukicoder

一番最初に作問をしたのが去年のあどべこんの12日目で、
www.adventar.org

こちらの問題になります。
No.319 happy b1rthday 2 me - yukicoder


そして先月、5問中4問が自作の問題なコンテストを開催させていただきました。
rian.hatenablog.jp


なので、作問を始めてからちょうど1年間で7問yukicoderで作問させていただいたことになります。


本題

記事のタイトルが「初心者が作問して思ったこととか」ですが、とりあえず一番強く感じるのはやっぱり、

作問って難しい！！！

です。その中で、具体的にどういうところが難しいとか、どういうところに苦労してるみたいな話を書きます。

誰か作問のプロ、作問テクみたいな記事書いてほしい

難易度・分野の制限

まぁ当然ですが、自分が解けないレベルの問題は作れません。
さらに、自分が苦手とする分野の問題は本当に作れません。
自分はグラフの問題が本当に苦手で、逆にDPやsegtreeを用いると解けるような問題が比較的好きなので、実際にyukicoderで作問した★3以上の問題(5問)はDPが2問、BITを使う問題が2問、数学が1問となっていてひどい偏りようです。

作問のプロ各位は一体どれだけの地力と隙のなさをお持ちなんだ、って感じ。

また、証明はしてないけどきっとこれで通るやろ！ みたいな解法は自分がコンテスト参加者なときは好きに投げられますが、自分が作問側の場合はちゃんと証明しないとひどいことになりますし、なんかコスパが良くない気がします。特に自分は嘘考察をすることに自信があるのでつらい。

良問が作れない

つらい。クソ問ばかり量産されます。

自分の作った問題の中でそこそこ良問なのでは？ って思っているのが、
初作問のNo.319 happy b1rthday 2 me - yukicoderと、
最近のNo.448 ゆきこーだーの雨と雪 (3) - yukicoderなのですが、
どちらも解法からではなく先に問題概要を思いついた、という共通点があります。

上のツイートでも言っていますが、なんか個人的には「このアルゴリズムを使う問題を作りたい！」とか言って作ろうとするとクソ問しか産出されず死亡、みたいなことが多いです。きびしいせかい。

というか初めての問題であるところのNo.319 happy b1rthday 2 me - yukicoderがもはやピークだったのでは？ という危惧があります…

テストケース作成が大変

作問をすると自動的にテストケースも作らなければなりませんが、強いテストケースを作るのがとても難しいです。
嘘解法を落としたり、TLE解をきちんとTLEにしたりするのがとても大変。というかできない。

特に後者は C++とかいうクソ速クソ言語のせいで とてもきびしい。C#解よりオーダー悪いのに爆速、みたいなこともあってもうなんやねんという感じ。

そもそも想定解法が正しいのかとても不安

毎回、出題してからACされるまでビクビクした時間を過ごしています。
テスターってすごいだいじ。

C++はクソ

C++はクソです。

想定解法で解いてほしい

平衡二分木で殴った人は早く解説記事を書いて。
No.449 ゆきこーだーの雨と雪 (4) - yukicoder


誰か作問のプロ、作問テクみたいな記事書いてほしい

書いてほしい。



ところで

ただいま、Advent Calendar Contest Advent Calendar 2016 が開催中です！

www.adventar.org

私は今年も12日目に出題させていただけることになりました。多分★3で、去年のより簡単めだと思います。
こちらもどうぞよろしくお願いします！！！





明日の記事は、
Yazaten さんの「色々なアルゴリズムで「殴る」」と、
とこはるさんの「最近改訂した定式化ドキュメントまわりの話」
だそうです！ 楽しみですね！

ゆきこーだーの雨と雪(1)~(4) 雑記

yukicoder

これは
ひとり Advent Calendar 2016 - Adventar
の4日目の記事です。



11/18に、なんと5問中4問が自作問題のコンテストが開かれました！ わーい

f:id:riantkb:20161204234041p:plain
yukicoder contest 154 - yukicoder


問題名は、ゆきこーだーの雨と雪(1) ~ (4) でした。

元ネタはもちろんおおかみこども的なアレです。

一番最初に作ったのが(2)で（多分半年以上前）、多分その時に金曜ロードショーか何かでやってたのだと思います。


(2)はまぁ簡単な問題だなぁと思いながら、当初は最後にsort関数にぶっこんで {O(N \log N)} が想定解の★3でした。★2になった理由は後述。


その後、(4)の問題概要を思いついて問題文を書いたのですが、実はその時はまだ解法が思いついていなくて、やっぱ平衡二分探索木とかで殴らないと解けないのかぁとか考えていました。
そんなとき、クエリ先読み座標圧縮からのBITでできるやん！ となり、完成に至りました。


その後、2問だけじゃ寂しいなぁとなり、どうせならメタっぽい(?) 問題を作ろう！ と思ってwriter体験問題みたいな(1)を作りました。個人的にはけっこう気に入ってるけどふぁぼがついてなくてかなしい。


そうして3問作ってしばらく経ったのち、（現実世界の）yukiさんからゆきこーだーの雨と雪を用いて当番回をしませんか、みたいなお話をいただいて、二つ返事で了承しました。

ただ、問題が3問しかない、どうしよう…。

よし、もう1問作ろう！

となりました。


そこからがわりと難産で、あと足りてないのはおおかみ要素だ！ って言って2人プレイ用の人狼を題材にした問題にしようかとも考えたのですが、
jinraw.com
ほぼじゃんけん(運ゲー)みたいな感じやんけ！ ってなって断念しました。


その後、「いや、この3問でコンテストやったらただの実用プログラミング実装コンテストになっちゃうんじゃないか…？」と思いつつ、適当なことを考えてたらうまくこじつけてかつ二分探索もDPも使う問題ができました。やったぜ。

でも作った当初は、二分探索パートとDPパートが明らかに透けて見えるしこれは★3弱かなぁと思っていました。


こうして残り1問として★3が生成されたので、(2)は {O(N^2)} で通る制約に変更されて★2になりました。



その後、かみぺさんの点数を計算する★1の問題を加えた5問のコンテストとなることになりました。


ところが(4)のテスターをantaさんにお願いしたところ、なんと C++ だと {O(TM)} ( M は参加者の人数) がわりと適当な実装で通ってしまうらしく激冷えになった。C# の string を key とする SortedDictonary が重すぎて {O(T \log T)} なのに 5sec かかっていたので余計に激冷えという感じ。



さて、コンテストですが、まず(1)はまぁ、という感じ。比較的みんなちゃんと {O(\log N)} で解いていてえらいなぁという感じがした（想定解法は {O(N^2)}）。


(2)は、

  • 実装が重い
  • そもそもstd::mapは★2適正ではない
  • つらい

みたいな感じで阿鼻叫喚になっていました。ほんと申し訳ねぇ。


(3)は、わりと思ったよりつまづいていただけていてびっくりした。
testerさんが後半のDP部分を Segtree で解いていたように記憶していたけど、その解法で通してる人がわりと多かったような気がした。


(4)は、やはり {O(TM)} で通している人がちらほらいたように見えた。
ただ、(3)がけっこうきびしく、(4)に辿り着いている人は平衡二分木のプロばかりで平衡二分木で殴って終了、みたいな解も多かったような気がする（その人たちは頼むから解説記事を書いて、はやく）。
多分想定解で通している人はほとんどいなかったと思う。



結果として、(3)が思ったより良問になってびっくりした。


以下、適当なツイートたち。


バイトが長引いたせいでコンテスト直前にantaさんの追加テストケースを入れる羽目になり、リジャッジでめっちゃTLEしてジャッジを詰まらす。





心の叫び



心の叫び(2)



解説、書いて❤️



自画自賛




今見ると(2)は80人近い人に解いていただいているので、なんか教育的要素を一つでも感じていただけた人が一人でも多ければそれはとっても嬉しいなって

DDCC2016 参加記

AtCoder DDCC

これは
ひとり Advent Calendar 2016 - Adventar
の3日目の記事です。



DDCC2016に行ってきました。



人権が少ないタイプのコンテスト


コンテストの結果としては、A, B, Cの部分点は50分そこそこで取れて、Cの嘘解法がなぜか1WAしか出なくて、解法を見つけるというより嘘解法でごり押して通そう！ って方にシフトしてしまい結果1時間座ってるだけになってしまった😇

結果は2完1半で43位でした。
うーん、2ページ目までには入っておきたかった、というか3完したかった。



🍣とかちょこふぉんでゅとか食べた


講演会、厚切りジェイソンさんとDISCOの方のお話を聞いた。
厚切りさんは普通に有能な人という感じだったし話も面白かった。


KKM(かしこいかわいい森田)




葦くんが酔って顔が真っ赤になっていた



おまけ



結局寿司食べて酒飲んだだけになってない…？