読者です 読者をやめる 読者になる 読者になる

うにゅーん、って感じだ

SRM, CF, AtCoder黄. SRM highest:1746. 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)} 解を考えてた、とかがあったらめっちゃ申し訳ない。



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

3DSは持ってないです

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








干し芋は「欲しいものリスト」だからだそうです。

イカれたメンバーを紹介するぜ!

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



ところで3日間くらい空いちゃってますけどどうしましょうね。





イカれた誕生日プレゼントたちを紹介するぜ!



まずはキーホルダーたち! かわいいけどそろそろつける場所がなくなってきている!
f:id:riantkb:20161212133037j:plain



続いて面白そうなラノベ! 最近頭を空っぽにする物語しか摂取してなかったから少し不安!
f:id:riantkb:20161212134459j:plain
[スニーカー文庫公式サイト]ザ・スニーカーWEB



続いて Land of Lispオライリーじゃねぇか! Lisp 書く気、なし!
f:id:riantkb:20161212135044j:plain



続いて電源タップ! なんかとてつもなく便利なんだが???
f:id:riantkb:20161212135847j:plainf:id:riantkb:20161212135942j:plain
seihinbu.pos-tec.jp






(以下、アレなのでアレ)







続いて福袋とローション! 福袋の絵柄がかわいい。ところでなんでこの福袋、ゴムが入ってるんだ。
f:id:riantkb:20161212135501p:plain



続いて、ぽい?っぽい?いえーい(._.)ちゃっくだょ〜〜〜✌️(o_o) (中略) IQが1。
f:id:riantkb:20161212140947j:plain



続いてパンツ! 正直一番キツいぞ!!!
f:id:riantkb:20161212140439j:plain




おまけ

なんかamazonでセールやっててつい長財布を買ってしまったぜ!
f:id:riantkb:20161212141331j:plain




なんかまだ届いたりするらしいのでまた追記します。

ハルコン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万を切り、なんやねんって言う
終了直後の方針ツイートとか色々




nyan

Advent Calender Contest yukicoder

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




ただいま、荒れに荒れています!笑(←笑 ではない)

No.456 Millions of Submits! - yukicoder




今日は本当はハルコンの自分のやったこと解説記事をあげる予定だったのですが、自分のあどべこんの問題のあれこれとかで気づいたら書く時間がなくなっていたので明日以降に延期となります。


あれ、このひとり Advent Calendar 2016 - Adventar、当初書きたかったこと全然書けてなくない???



まぁ荒れていますが、個人的にはまぁまぁ面白い問題だなぁと思ったので解いていただきたい。
実は非想定解がめっちゃ通りそうだったり一部通っちゃったりしてるけど


こういう問題ってやっぱどうしても難しいなぁという感じ。
多分当初のはむこさんの想定解で通す人はほとんどいないんじゃないかなぁ、という感じ。

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

これは
ひとり 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 さんの「色々なアルゴリズムで「殴る」」と、
とこはるさんの「最近改訂した定式化ドキュメントまわりの話」
だそうです! 楽しみですね!

かみんぐすーん

yukicoder

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



www.adventar.org



f:id:riantkb:20161205235851p:plain


f:id:riantkb:20161205235900p:plain



かみんぐすーん