JAG夏合宿2017(+コード祭り2017予選A)参加記
9/22-24 に、JAG の夏合宿(http://acm-icpc.aitea.net/index.php?2017%2FPractice%2F%E5%A4%8F%E5%90%88%E5%AE%BF%2F%E6%A1%88%E5%86%85)に行ってきました。
今年初めて icpc アジア地区への切符を手にしたので、夏合宿は初参加!
宿泊部屋が足らないという話だったので、毎日お家に帰りました(ただ思ったよりオリセンが家から遠く、片道1時間かかったので宿泊したほうが良かったかもしれない)。
今回、チームメイトの一人は学会か何かが被ってしまったので、kurukuru-sushi からは りあん(@rian_tkb)と 葦(@Ashurnasirpal)が参加し、毎日一人チームに迎え入れる形でコンテストに出場しました。
1日目
1日目はすぬけさんのセット(Japan Alumni Group Summer Camp 2017 Day 1 - AtCoder)
jag夏合宿1日目は kurukuru-shuriken (@smiken_61, @rian_tkb, @Ashurnasirpal ) で出ます! pic.twitter.com/UlGXRkbOsf
— りあん (@rian_tkb) 2017年9月22日
この日のチームメイトはすみけんさん(実は高校の一つ上の先輩だったことがコンテスト中に発覚しびっくりした)。
Macbook Air に リアフォ を刺しているという謎環境なので、コンテスト前に簡単な操作方法のレクチャーをする(これは結局 3日間ともした)。
コンテスト中の流れ
(記憶が薄れてきているので細部が違っているかもしれないですがご容赦)
コンテスト開始。問題が1セットしかなくホチキスどめされていたのでまずはホチキスを丁寧に外し、問題を机にばらまく。
自分が最初に手に取ったのは E で、問題文の上部に BNF が見えたので問題概要を全く読まずに 3秒で葦くんに投げる(kurukuru-sushi では構文解析問題は全て葦くんに投げるという戦略を取っている)。
次に D を読むと、これは簡単な算数。早速コードを書き始める。途中少し詰まった(直角でないところを直角だと勘違いしていた)ところですみけんさんが J を一瞬で通す。その間に自分もミスに気づき、続けて D も AC。
次は多分 K に取り掛かっていたと思う。問題文を読んでこれはどうせ C_i - G_i でソートしてほいするやつでしょ、とか言いつつ書く。マイナスがついたりつかなかったり、どっちがおっきいとどうなる(自分は通す直前までコストとゲインを逆だと思っていた)とかがややこしいのでそこらへんを色々試すが、どうしてもサンプル1 とサンプル2 が同時にうまくいくようなことがない。そうこうしているうちにすみけんさんが A をいけそうとのことだったので書いてもらう。
K はこれ以上考えるとドツボにはまりそう(というか既にはまっている)なので、ここで葦くんに投げた E の様子を見にいく。問題を読むにそこまでつらそうな問題には見えず、スカラーは要素数1 のベクトルじゃない? と言ったらなんか解決したらしい。
その間にすみけんさんが一人で A を通し、葦くんに E を書いてもらう。手の空いたすみけんさんに K を投げ、その間に自分は H を考える。制約がクソでかいので、明らかにうまい方法があるやつ。こういう問題はまず条件を緩めた問題から考えると良い ので同じ動きを連続でしてよい場合を考えると、3つのうち高々2つの動きしか使わないことが判明。ということは交互にやっていって片方だけ残ってしまったらくるっと回る動作を間に挟めばよい、とわかる(よく考えるとこれが最短ムーブになる証明をしていない)。
ちょうどその頃 K のサンプルを手で試していただいていたすみけんさんにより、C_i + G_i でソートしてほいだということが判明。そこで自分が C と G を逆と勘違いしていたことも判明。
そのあと順位表を見て F が通されているように感じたので F を解けそうな目で見る。するとぱっと見ごつかった問題が実は自分より後での各文字の最初の登場位置と、自分より前での各文字の最後の登場位置がわかれば解けることがわかり、かつそれは普通に各文字から前後に伸ばしていけば間に合うので、途端に解ける問題に大変身した。
そのあたりで葦くんが E を通し、続けて自分が H, K, F と AC。E が通ってから F が通るまで 30 分かかっていない。
残る問題は 4 問で、正直人間に解ける問題が残っていなさそうに見える。
残り40分くらいで、葦くんが G が最小費用流になりそうだと気がつき、自分がライブラリの写経を始める(G をぱっと見フローと気づけなかったのはとても反省…)。写経をしている間に 2人の考察によりじわじわと解法がまとまり、コードを書くが、実装が重くしかも若干バグらせたため時間切れ、とても悔しい(でも結局その後書き上げても通らなかった)。
結果は 7完 7位。上にはガチプロしかいないので人類トップ、ってことでまぁ僥倖かなぁという気持ち。
7完でした
— りあん (@rian_tkb) 2017年9月22日
最後1時間座っているだけをした pic.twitter.com/BFCmcHU14S
普通に疲れていたのでそそくさと帰宅してしまった…。
2日目
2日目はこどふぉのgym(http://codeforces.com/gym/100633/)
jag夏合宿2日目、kurukuru_algon ( @rian_tkb, @algon_320, @Ashurnasirpal ) で出ます! pic.twitter.com/4UvyItVGK0
— りあん (@rian_tkb) 2017年9月23日
この日のチームメイトはあるごんさん。あるごんさんを kurukuru していく。
コンテスト
(あまり覚えていないし疲れてきたのでここは適当です)
全体的に readforces だった。
最初に L を読んでいけそうに思ったが、誤読したのとまぁまぁバグらせて(無駄に O(N) で解いていた)結局 5WA。冷え冷え〜。
あとは B が簡単な DP だったのでささっと実装したり(Mod が 10億9 でキレた)、G の forward というのが時計回りか反時計かわからずあるごんさんに読んでもらい、そのまま解法を伝えて書いてもらったり、葦くんが H の問題文読解に成功して AC したり、I をわかんねぇなぁ〜、と言いながら貪欲を書いて AC したりしました。
B : mod 10^9 + 9 じゃあないんだよなぁ
— りあん (@rian_tkb) 2017年9月23日
D : forward がどっち向きかわからなくてチームメンバーに投げた
H : 問題文が難しすぎる
I : わからねぇ…って言いながら書いたら通った
L : 問題文が難しい
結果 5完で、オンサイト 6位かな? 全体的にキツすぎるセットだった…。
5完でした(自分がLを無限にバグらせて冷えた) pic.twitter.com/hmBpzjVmhc
— りあん (@rian_tkb) 2017年9月23日
この日は Hec さんとけっこう話をしていた気がする。ABC-D じゃない 400 は怖いよね、という話もした気もする。
コード祭り予選まで少し時間があったので新宿で弐寺をしてから帰った。SP六段です。
チェッキン灰とデイドリ灰が点いた!! pic.twitter.com/Rr0Hz5gIbV
— りあん (@rian_tkb) 2017年9月23日
コード祭り予選A
その日は予選A がありました(CODE FESTIVAL 2017 qual A - AtCoder)
ボーダー予想として、本戦ボーダーは4完早解き、ありがとう祭りのボーダーも4完になるかなぁ、と踏んでいたので、D から開くことを決意。すぎむさんの 700 なので AND Grid のような思いつき構築ゲーが出るかもと予想していたので、死ぬ気で解きにかかるぞという強い意志。
結果、D をうまく思いつけて運良く 27分ほどで通せて、最後に A で 1RE(文字の長さが 4未満の場合に死んでいた)したものの全体 75位、日本人 19位という成績でした。勝ったなガハハ!
全体75位、日本人19位でした!
— りあん (@rian_tkb) 2017年9月23日
勝ったなガハハ pic.twitter.com/CpWz6frumf
D: dが奇数のときはチェス盤みたいに2色で塗っていけばいいので自明
— りあん (@rian_tkb) 2017年9月23日
偶数のときは写真のようにやった pic.twitter.com/uVoVvUWEFD
d が 2 より大きい偶数のときに各色が大きな正方形を描いていることに、ツイートする用の図を書いているときに気づいた(ア)
D はもちろんつらかったけど他の問題も普通につらくてつらいセットだなぁとなった。
2327 -> 2397 (+70)
— りあん (@rian_tkb) 2017年9月23日
えーーーー、オレンジ……
2回目のパフォ 2800 超えによりレートもそこそこ上がった。嬉しい。
3日目
3日目は JAG のセット(Japan Alumni Group Summer Camp 2017 Day 3 - AtCoder)
jag夏合宿3日目、kurukuru-ixmel (@mel_fall524, @rian_tkb, @Ashurnasirpal ) で出ます! pic.twitter.com/UYqCcY6neg
— りあん (@rian_tkb) 2017年9月24日
この日のチームメイトはめるさん。めるさんを kurukuru していく。
コンテスト中の流れ
めるさんが A を読んですぐ AC。葦くんが B を読み、実装に入る。自分は C の読解に苦しむ(グリッドに整数が記入されている的な設定でもよかったのでは?)。
葦くんが苦しみながらも B を通し、自分も苦しみながら C を通す(上から下じゃなくて左上から右下に斜めに埋めていってしまったので実装がクソつらかった)。
D はC に苦しみつつも問題概要を聞いていて、さすがに bitDP だろうという気持ちになる。ぱっと見 っぽいが部分集合の部分集合はもうちょいオーダーが落ちそうに感じ、この方針で行こうと考える。
あいこじゃない遷移は簡単だが、あいこになる確率がとてもつらい。ただ、うまくベン図を書いて考えると で求まり、勝利。AC。
そうこうしているうちに葦くんが F の考察をまとめる。プロ。そのまま葦くんが書いて AC。
E については、自分が + で区切ればいいというのを思いつくが、そのまま区間DPしても 2500^3 になりダメ。すると葦くんが解法を閃いてくれる。プロ。それは自分が実装を行い、AC。実装はめるさんに投げてしまってもよかったかもしれないなぁ。
あとは G を考えていたが、きっと解法は枝刈りではないだろう…、と思ってしまっていたので、相性が悪いと思いつつもフローを考えたりしていて、結局そのまま終わってしまった。6問解いた時点でもう少し時間が残っていたら枝刈ろうと思えていたかもしれないが、まぁ致し方なし。
あと、G をほぼ諦めていた段階で D の計算量を計算したらやはり部分集合の部分集合は 個で、 になっていた(大学受験数学が得意)。
Dを通した後に計算量を計算したら O(N 3^N) で感動した
— りあん (@rian_tkb) 2017年9月24日
結果 6完で、オンサイト 7位? 2日目と同じくらいキツいセットだった…。
6完で18位でした pic.twitter.com/43d1UYEu3C
— りあん (@rian_tkb) 2017年9月24日
まとめ
競プロづくしでとても楽しい3日間でした!
コンテストの内容については、さすがにこれは通せなきゃダメだったなぁ…、みたいなのはほとんど無かったような気がしたのでまぁ悪く無かったと思います。ただ、どの日も半分以上の問題の実装を担当したので、もう少し配ればよかったかもなぁとは思いました(自分はそこまで実装の速い方ではない)。
国内予選突破という目標を達成してしまったので来年の ICPC はコーチとして出ようかなぁとか思っていたのですが、やっぱりチーム戦たのしすぎなので来年も選手として出ているかもしれません。まだわかりません。
懇親会的なものがなかったり帰宅勢だったりしたので、あまり交流ができなかったのが少し心残り……。
次は KUPC 東京オンサイトにいく予定です!
すみけんさん、あるごんさん、めるさん、チームを組んでいただきありがとうございました! とても楽しい3日間になりました!
— りあん (@rian_tkb) 2017年9月24日
夏合宿の3日間で色々な人を回しましたhttps://t.co/e3bRjOZzFRhttps://t.co/xmhzGOpGYMhttps://t.co/QM63D7HqXn
— りあん (@rian_tkb) 2017年9月24日
ACM-ICPC 2017国内予選 参加記
半年ぶりのブログ更新ですね。
本当はこの記事の前に、この前 SnackDown2017 というやつでインドに行った、という記事を書かなければならないのですがちょっと色々忙しかったのでそのうち書きます。
あらすじ
icpc たいてっく予選は毎年熾烈(しれつ)を極めていた。謎の組織 FCCPC 、†赤きもの†へと進化した後輩、大魔王 yosupot ...。
ただ、そんなたいてっくにも希望はあった。謎の組織 FCCPC は謎すぎたため消滅、大魔王 yosupot は力を溜めるための眠りについた。
今こそたいてっく予選に打ち克つべき! †赤きもの†へと進化した後輩の次の1枠を狙い立ち上がったチーム「kurukuru-sushi」の前に立ちはだかったのは、チーム「IQ1」だった…。
icpc、チーム「kurukuru-sushi」(@rian_tkb @Ashurnasirpal @monman53 ) で出ます
— りあん (@rian_tkb) 2017年7月14日
頑張って IQ1 を超えるぞ👊
https://t.co/dXNTyjEsQF
登場人物
チーム「kurukuru-sushi」
rian_tkb(りあん), Ashurnasirpal(葦), monman53(もんまん)からなるチーム
http://icpc2017.yamagula.ic.i.u-tokyo.ac.jp/team/1308
チーム「IQ1」
吹雪, 睦月, 夕立 からなるとてもバランスの良いチーム
http://icpc2017.yamagula.ic.i.u-tokyo.ac.jp/team/1142
チーム「ninjaribaton」
nari, baton, ninja からなるガチプロ後輩チーム
http://icpc2017.yamagula.ic.i.u-tokyo.ac.jp/team/1327
ティッピーぬいぐるみ
チーム「kurukuru-sushi」の机の上に鎮座するぬいぐるみ
kurukuru-tippy pic.twitter.com/7gqWIcsQci
— りあん (@rian_tkb) 2017年7月14日
国内予選前日 (7/13)
たいてっく予選突破が絶望的だった一昨年、去年とは異なり、たいてっく予選突破が現実味を帯びている今年のicpc国内予選。……というより、今年の出場選手のうち†赤きもの†へと進化した後輩の次にレートが高いのが自分で[要出典]、さすがにたいてっく予選突破できないと人権がない、という状況になり今までにないプレッシャーに追われる rian_tkb。
血迷った rian_tkb は、秋葉原に赴き25000円のキーボードとリストレストを購入する。
キーボードとリストレストです(計26k pic.twitter.com/YTDem7fpcS
— りあん (@rian_tkb) 2017年7月13日
(今思うと、ここまでして突破できてなかったら本当にやばかった)
国内予選当日 (7/14)
コンテスト前
今期の授業は全て切ったのでリハーサルが終わるまでに大学に着けばいいのだが、家にいても落ち着かないので早めに家を出る。
落ち着かないので出家した
— りあん (@rian_tkb) 2017年7月14日
ラボに置いてあった蟻本を持ち、蟻本に書いていない平衡二分探索木と、あとは AtCoder の提出のうち特に苦手なものの提出コードを印刷して会場に向かう。
チームメイトが皆蟻本を持ってきていたので積み上がる。
蟻本が3冊揃った pic.twitter.com/kYBYIFABsd
— りあん (@rian_tkb) 2017年7月14日
リハーサルも3問通して暇なので遊ぶ(上の kurukuru-tippy もこのとき撮影)。
— りあん (@rian_tkb) 2017年7月14日
この後、もんまんくんが M問題を頑張って通していた。
練習フェーズ、3年目にしてようやく終止符が打たれた pic.twitter.com/rD9FhFUiIQ
— もんまん (@monman53) 2017年7月14日
コンテスト中
最速で印刷ジョブを飛ばしたつもりがプリンターがトナー切れで、少しタイムロス。
その間に A問題を読む。
……ん? これは恐ろしいほどに簡単だぞ???
横からめっちゃ口を挟みながらもんまんくんにコーディングしてもらい、そのまま AC。ここまで 5min。
葦くんが B を読んでいたので見ると、構文解析。
問題文がよくわからなかったのでよくよく読むと、ダブルクォーテーションで split して偶奇を気にしつつぐっ、とやるだけ。
しかし、A が通ってしまい PC を空いた状態にしたくないという焦りから見切り発車してしまい、少しめんどい実装になってしまった。
ただそこまでバグらせずに通してくれたのでよかった(とは言ってもやはり時間はかかってしまった)。ここまで 30min。
葦くんが B 問題と格闘している間に C 問題を手に取ると、h, w <= 10 なのが不思議なレベルで簡単な問題。
本当にやるだけにしか見えない。
もんまんくんに解法を伝えつつ紙コーディングをしてもらう(もちろんこれにもめっちゃ口を挟む)。
葦くんが B を通したらそのまま C を実装してもらい、AC。ここまで 40min。
ここで順位表を見る。
結構いい感じに進んでいたと思っていたので IQ1 に時間ペナルティでとても大きく離されていてとてもビックリする。
この様子だと正答数で上回らないと IQ1 に勝てないぞ……。
ここで自明問題が尽きる。
自分はすでにちょっとテンパっていたので、葦くんに D の問題文の要約を頼む(正確には問題概要はほぼ入っていたが、D に入る問題に見えなかった(=普通に解ける気がしなかった)ので誤読が怖くて読んでもらうことにした)。
どう考えても n * m <= 500 が重要な制約だが、よくわからない。
葦くんから整理された問題概要を聞くが、まだわからない。
ただ、こういうのは大抵 n = m あたりが重要なので、紙に 20 * 25 = 500 という式を書く
→ あ、これいけるのでは???
PC が空いていた焦燥感もあり、とりあえず書き始める。
途中少しテンパるが、大きなバグもなく実装した……はずが、答えが合わない。
よく見てみると、求めるものが作れるレシピの集合が何通りあるか、ではなくレシピの集合の要素数の最大値だった(ここは葦くんの誤読だったと思う)。
ただ、修正自体はすぐにでき、AC。ここまで 1h10min。
ここでまた順位表を見ると、また IQ1 との差が広がっている。これは本格的にヤバい……。
E は無理そうという話があったので、先に F を見る。明らかに考察ゲーの匂い。
無理そうと言われていた E も読むが、確かに無理そうだったので、F の考察をする。
とりあえず計算用紙に印をつけて実際に折ってみる。
左からの位置と上からの位置と左右どっちに折ったかがわかれば、次の状態が定式化できそうな状態にはなる、が、まだ考察が進まない。
もう少し考察をすると、上から何番目にあるか、というのは折り方と 1対1 に対応することがわかる。
あと、逆に折った状態から展開したとき、右に開いても左に開いても上から何番目かというのが変わらないことがわかった。
が、前からやっていくべきか、後ろからやっていくべきかがよくわからない。
両方からやって 2^30 はさすがに間に合わなさそう……。
ここでうだうだ言っていると、もんまんくんが考察の手助けをしてくれて、一気に解法へ結びついた
競プロ問題の考察、最初の方に気づいたことを後で忘れていることが多く、それを囁いてくれるチームメイトが最高という感じだった(今回のFが完全にそれ
— りあん (@rian_tkb) 2017年7月14日
(折った状態から展開したとき、右に開いても左に開いても上から何番目かというのが変わらない、という自分の考察を完全に忘却していた)
ばばばっと書く。
1-origin なので境界条件とか +1 するか、とかがクソめんどい。
実際にバグる。
サンプルが合うようにコードをいじいじする。
そうこうしているうちに葦くんが G 問題がいけそうな雰囲気になったと言っていて、写経が必要なのでとりあえずコードを印刷して交代する。
コードを印刷して眺めていると、バグがすぐに見つかる。
また交代してもらってそこを直すとサンプルが通ったので、そのまま投げると AC。俺ってもしかして天才か??? ここまで 2h。
葦くんが G の写経をしている間、E を考えるが普通に無理そう。
H に関しても、4回まで調べればいいので探索範囲はすごく絞れそうだが絞り方がよくわからない。
なので、葦くんの G の解放に反例がないかどうかを調べる。
葦くんのコーディングが終わってサンプルを食わせるが、バグっている。
いくつかのしょうもないバグは潰し、見た目上はいい感じに動いているが、どうしても関節点列挙がバグっている……。写経はもんまんくんに適宜チェックしてもらっていたので問題ないはず……。
もう時間がなかったので一回バグったままで投げてみるが、当然 WA。
結局バグがどこかわからず、最後は順位表を見ながら終了。
最後の 2h59m59s で IQ1 が F を通していて、時間ペナルティ的に 1WA でも出していたら順位が逆転していたので、本当に危なかった。
結果、ABCDF の 5完 0WA早解きで 16 位でした! まぁ上々では
Standings
http://icpc2017.yamagula.ic.i.u-tokyo.ac.jp/standings/
コンテスト後
多分通過した!!!!!
— りあん (@rian_tkb) 2017年7月14日
今年、よすぽがいないのに東工大から3チーム通った
— りあん (@rian_tkb) 2017年7月14日
プロにおんぶとだっこ以外で東工大予選を突破できる日が来るとは思っていなかったので思ったよりドチャクソ嬉しいですね……
— りあん (@rian_tkb) 2017年7月14日
しかもわりとチームメイトの力を借りて動けたので本当にベストな感じだった
— りあん (@rian_tkb) 2017年7月14日
今回これも本当に実感した(今回は例年とは違い問題文が簡潔だったが、それでも中盤自分はテンパっていてちゃんと問題文を読める状況になかったので、優秀なチームメイトがわかりやすくようやくしてくれるのは本当にありがたかった
— りあん (@rian_tkb) 2017年7月14日
打ち上げに行くが全然飲み足りないので、家で独り祝勝会
浮かれているのでジンで独り祝勝会をします pic.twitter.com/MssXKAI0na
— りあん (@rian_tkb) 2017年7月14日
いま、めっちゃジンが入っています✌︎
あとがき
国内予選突破できて本当に良かった。
こんな日が来るのは本当に夢みたいで、大学入って競プロ始めて以来、一番嬉しいかもしれない。
それではみなさん、つくばで会いましょう!
三角形はいくつ? 雑記
これは
ひとり Advent Calendar 2016 - Adventar
の14日目の記事です。
アドベコン2016の12日目の問題を担当させていただきました。
問題はこちら
No.461 三角形はいくつ? - yukicoder
問題概要としてはパズル的なのでよくある、線をいっぱい引いた図形の中に三角形がいくつあるか数えるものです。
さて、解法としては、直線を3本取ってきたときにその3本で三角形が描けているか、を判定してあげればいいです。
判定方法についてですが、まず3本が1点で交わるとダメです。また、3本の互いの交点のうち一つでも最初の大きな三角形の外側にある場合、3本は最初の大きな三角形の中のみ伸びてる線分なのでこれも三角形となることができません(日本語が下手)。
実は、この2点をクリアすればその3本は必ず三角形を描けています。
次はこれを実際にどう判定するかですが、
という値に注目すると、
前者は3本の の和が1であるかどうか、後者は3本のうち任意の2本に対して の和が1より大きいかどうか、にそれぞれ対応しています。
(これはもちろん という値に注目してもほぼ同じように解けます)
この判定を全組み合わせに対して調べれば、とりあえず で解けます。ただ、2本を確定させたとき、もう1本に対して3本の の和が1になる線分があるかどうかと、任意の2本の の和が1以下のものがいくつあるか、というのは の値でソートしておけば両方 で解け、結果 となります。
(うまくしゃくとりとかすると になります)
これは最初 が通る制約で★2で出す予定でした。ただ、アドベコンの周囲の問題の難易度を眺めているとどうも★2が多そうだったので(ただこれは罠でその後みんな★3に昇格した) に制約を変えて、ついでに誤差を 程度まで小さくして分数で足したりソートしたりしてもらうようにしたりとか、 にしてオーバーフローを誘ったりしました。
ただいくつか誤算があって、まず、long double は仮数部が 63bit あるので、long long の範囲では誤差が出ない、ということ。これは出題前に気づいていました。本当は浮動小数点数を使った解答を全て誤差死させたかったのですがまぁ致し方なし。double がほぼ全て落ちるだけでも僥倖みたいなところがある(ちなみに C# には double より精度の高い浮動小数点数型が存在しないので分数解しか通らない、はず)。
次に、変に とかいうギリギリを攻めたせいで TL が少し厳しくなってしまったこと。これは kimiyuki さんにテスターをしていただいた際に明るみになりました。まず、Python ではナチュラルな が TLE するらしくもうびっくりという感じなんですけどまぁこれは置いといて。問題は、分数クラスがちゃんとしていて毎回約分するようなものだと毎回 がかかって 5sec でも TLE することがあるらしくにゃーんという感じでした。
それと相反して が通っていたりもして、それは本当にびっくりなんですけど。というのも、オーバーフローをさせる関係で今回ちゃんと最大ケースを作っていて。しかもそれの答えが 23億 とかで。でも一つ一つ数え上げて 4sec ちょいで通っていて。もうC言語ってなんなんだよ、という感じ。
それと★4に昇格したのも誤算の一つで。おそらく のせいで解法が の全探索から一つ に落として高速化、というプロセスを辿りづらかったのかも? 部分点というか部分ケースがあってまずそっちが通るかどうか試す、みたいな方針でいったらもう少し楽に解かれたのかも。そもそも が通る制約に見えなくてずっと 解を考えてた、とかがあったらめっちゃ申し訳ない。
でもまぁストックのクソ問が思ったよりいい感じな問題になった(ほんまか?)のでまぁよかったかなぁ。とは言ってもストックのクソ問の中でもまだマシなほうなので残りのストックは本当に日の目を見ることがないかも……。
ハルコン2016 参加記
これは
ひとり Advent Calendar 2016 - Adventar
の8日目の記事です。
カービィやスマブラなどで有名なハル研究所が開催していたプロコンに参加していました。
期間は11/7 ~ 11/25 で2週間以上あり、まぁいわゆるマラソンマッチです。
私がコードを書き始めたのは多分11日くらいなので、ちょうど2週間くらい参加していたことになります。
最後に順位表を見たときは6位だったので、再評価でいい値が出たり上がコケたりしてくれれば、賞金がワンチャンありうるかも…?
こちら、提出したコードにめっちゃコメントを書いたものです。読んで。
ハルコン2016でのrian_tkbのコード · GitHub
そのうち、自分の方針をまとめた解説記事みたいなのも書きたいと思ってます
(マラソンやったことないのでビームサーチとか焼きなましとか言葉しか知らないので、今回も盤面評価すらしていないので多分他の人とは方針が全然違いそう)
以下、期間中の関連ツイートを適当にまとめたもの
C++書けないマンとしてはな
C++しか使えないプロコンってなんだよ
— りあん😇 (@rian_tkb) 2016年11月8日
誤差の処理とか、ちゃんとREADMEに書いておいてほしかった(コードを読解した)
これ、小惑星に接するようにレーザーを撃ったり移動したりしたらどうなるんや
— りあん😇 (@rian_tkb) 2016年11月8日
C++書きたくないマンとしてはな
ハルコン、適当な方針が立ってしまったので時間があったらC++書くかぁという気分
— りあん😇 (@rian_tkb) 2016年11月8日
最初、1ターン目からビームが打てて、かつ次に打てるのがその40ターン後だと思っていた、けわしい
(実際には、最初にビームを撃てるのは40ターン目で、次に打てるのはその41ターン後)
あれ、もうちょいちゃんと仕様をテキストで書いてくれという気持ちが強い(意識の相違によるバグが多発している)
— りあん😇 (@rian_tkb) 2016年11月12日
ようやく主なバグが取れてまともなスコアが出る
叩き台のバグがね、取れた pic.twitter.com/qHUAq8OsYQ
— りあん😇 (@rian_tkb) 2016年11月12日
ちなみに最大のバグはvectorの初期化忘れでした
— りあん😇 (@rian_tkb) 2016年11月12日
普通のオンラインジャッジみたいに1ケースずつ動かし直してると思ったら1回で200ケースまとめて動かしてたでござる
普段C++使わないし、プログラムを1回動かす中で200ケース試してると思わなかったし!
— りあん😇 (@rian_tkb) 2016年11月12日
探索の深さを増やすようにして2位まで更新
(この時期ですでにhirokazuさんは58000台を出してたのか…)
— りあん😇 (@rian_tkb) 2016年11月12日
かっこいい…
なんか上手くいってるケースだとめっちゃかっこいい動きしてる pic.twitter.com/a4pianVMW0
— りあん😇 (@rian_tkb) 2016年11月12日
2円の共通接線はめんどいので結局別の方法で解決しました
2円の共通接線、普通に4つあるからつらそう
— りあん😇 (@rian_tkb) 2016年11月12日
無限にバグが仕込まれているのでもうダメ
今日のバグの原因、余弦定理を間違ってた
— りあん😇 (@rian_tkb) 2016年11月13日
2位争いが熾烈になり、程なくして置いていかれる
とりあえずその場しのぎで伸ばしたけどすぐ抜かされそう pic.twitter.com/UOTRSR0spU
— りあん😇 (@rian_tkb) 2016年11月13日
これも地味につらかった
ハル鯖、手元より微妙に遅いんだよな
— りあん😇 (@rian_tkb) 2016年11月14日
このツイートをしたら翌日には修正が降ってきてて、もしかして監視されてる!? ってなった
え、こんなケース存在すんの、アホでしょ pic.twitter.com/VrUFW1uPmd
— りあん😇 (@rian_tkb) 2016年11月15日
さすがに宇宙船の初期配置は隕石と重なってて欲しくないが
— りあん😇 (@rian_tkb) 2016年11月15日
C++書けないマンとしてはな
— りあん😇 (@rian_tkb) 2016年11月21日
C++が書けなさすぎてふて寝した
— りあん😇 (@rian_tkb) 2016年11月21日
めっちゃTLE
手元「52.936 sec」
— りあん😇 (@rian_tkb) 2016年11月21日
ハル鯖「Time out」
ぼく「つらい」
— りあん😇 (@rian_tkb) 2016年11月21日
残り1日を切り、更新できず賞金ボーダーから置いていかれて焦る
隕石破壊、ギリギリ賞金が見えるかもしれないところまで来たけどあと更新できるとしてせいぜい80程度なので天啓が降ってこないときびしい
— りあん😇 (@rian_tkb) 2016年11月24日
ついに賞金ボーダーが6万を切ってる……
— りあん😇 (@rian_tkb) 2016年11月24日
残り1時間を切ったタイミングで、乱数で回数を回す方向にシフトしたら突如として6万を切り、なんやねんって言う
— りあん😇 (@rian_tkb) 2016年11月25日
終了直後の方針ツイートとか色々
そこまで色々作った関数を全部投げ捨てて乱数の神に祈ったら60000切ったのなんとも言えない
— りあん😇 (@rian_tkb) 2016年11月25日
全提出にリジャッジがかかるなら数出したもん勝ちじゃない? っつって最後にあまりよくなかった乱数も出しまくった pic.twitter.com/lsFYxqbkqd
— りあん😇 (@rian_tkb) 2016年11月25日
現状6位なので、上がコケてくれれば賞金ワンチャンかなぁという感じ
— りあん😇 (@rian_tkb) 2016年11月25日
ハルコン、遠い隕石ほどレーザーで落とさなきゃいけないので、適当に近い隕石を巡るルートを作って、その中でレーザーを撃つ各座標に対し、どの隕石の集合を落とせるか、という集合を調べて、それらを使って全ての隕石が落とせるか調べる、というのを必要ターン数で二分探索、という感じにしました
— りあん😇 (@rian_tkb) 2016年11月25日
残りの巡ってない隕石をレーザーで落とせるのかどうか、という判定をどうするかと、どういう風に隕石を巡るルートを決めるか、というのが肝だった気がするけど思いつかなかったので前者は嘘貪欲、後者は最初の方は先読み探索してたけど乱数回した方が改善された()
— りあん😇 (@rian_tkb) 2016年11月25日
ハルコンの問題、盤面の初期状態と自分の動きによって現在の盤面が求まるから、盤面の初期状態が与えられて2000ターン分の動きを返すでも良かったんじゃないかなぁとは思った
— りあん😇 (@rian_tkb) 2016年11月25日
初心者が作問して思ったこととか
これは
ひとり 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
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なのですが、
どちらも解法からではなく先に問題概要を思いついた、という共通点があります。
なんか、解法から問題を生成するより問題と解法を擦り寄せていった方が良問になるイメージ
— りあん😇 (@rian_tkb) 2016年11月18日
上のツイートでも言っていますが、なんか個人的には「このアルゴリズムを使う問題を作りたい!」とか言って作ろうとするとクソ問しか産出されず死亡、みたいなことが多いです。きびしいせかい。
というか初めての問題であるところのNo.319 happy b1rthday 2 me - yukicoderがもはやピークだったのでは? という危惧があります…
テストケース作成が大変
作問をすると自動的にテストケースも作らなければなりませんが、強いテストケースを作るのがとても難しいです。
嘘解法を落としたり、TLE解をきちんとTLEにしたりするのがとても大変。というかできない。
特に後者は C++とかいうクソ速クソ言語のせいで とてもきびしい。C#解よりオーダー悪いのに爆速、みたいなこともあってもうなんやねんという感じ。
そもそも想定解法が正しいのかとても不安
毎回、出題してからACされるまでビクビクした時間を過ごしています。
テスターってすごいだいじ。
想定解法で解いてほしい
平衡二分木で殴った人は早く解説記事を書いて。
No.449 ゆきこーだーの雨と雪 (4) - yukicoder
誰か作問のプロ、作問テクみたいな記事書いてほしい
書いてほしい。
ところで
ただいま、Advent Calendar Contest Advent Calendar 2016 が開催中です!
私は今年も12日目に出題させていただけることになりました。多分★3で、去年のより簡単めだと思います。
こちらもどうぞよろしくお願いします!!!
明日の記事は、
Yazaten さんの「色々なアルゴリズムで「殴る」」と、
とこはるさんの「最近改訂した定式化ドキュメントまわりの話」
だそうです! 楽しみですね!