ICPC2020アジア地区大会参加記

ICPC2020のアジア地区大会(オンライン)に参加していました。

昨年は予選に落ちてしまったので2年ぶりの参加です。

メンバーは変わらずferin+div+olpheの3人でnowcowを結成していました。

コンテスト以前

国内予選終わってからチーム練は12月までほぼ毎週、2月からほぼ毎週やっていた。

受付の様子がある程度は見えていてちょっと面白かった。運営の人大変そうだった。

面白い名前のチームが呼ばれていると面白い。

コンテスト本番

初手でBを読みたかったのでDiv君にAを、ふぇりんに残りのどれかを読んでもらうことにした。

Bは雑にDPを書いて復元するのを書いてWAを生やしていた。修正してAC

Aも辛そうだったけどほどなくAC

Jの概要を聞くと木DPだねって言って木DPを書く。いらんかったらしいけどAC

Hの概要を聞いて、168本のセグ木を生やし出してしまった。

Iの概要を聞いて嘘を実装したのち分かってそうなDiv君に丸投げした。

ふぇりんがGを詰めていて、聞いてもほんまか？ってなったけど丁寧に詰めてそうだったので丸投げした。

微妙にやることがなくなってしまったのでまだ読まれてなかったEを読むと自明だったのでAC

次々とI,Gも通る。最近はしてなかったけど中盤で突然通し出すようになるのはかなりよくないんだよね

しばらくHの高速化をしていて、ふぇりんに話すと動的セグ木？らしいので準備してもらう。

その間にCで手数長かったらこんなに解かれなくない？とか言って6手全探索するコードを書いてバグらせていたら、Div君が5手で右手法する方法を見つけてくれたのでそのままバグを修正する。左右間違えて2WA出した、カス

動的セグ木の準備が辛そうだったので大量に生やしたセグ木を頑張って軽量化していたけど間に合わず終了

nowcowは7完14位で残念ながらここで敗退です……

まあ実力差がそんなに大きくないかな……みたいに思ってたチームすべてに負けたので実はかなり冷えですか？(そう思ってなかったチームにも負けたし)

コンテスト以後

解説の時間疲れてておかし食べまくった。ごめんなさい。

Yes/Noは異常チームがいて盛り上がっていてすごかった。うちも凍結後に1問通せて嬉しかった。

交流フェイズは、何人かと雑をしたり、ちょっと真面目な話もした。

これまであまり交流が無かった人の中で、Flip-Flop Cの人やharaharaのうち二人と話せてよかった。

競プロをやっている高校生は農工大に来てください。

その他

今のチームで3年参加していたが、今年で解散なので寂しくなった

問題文読みたくないので実装奪い取りまくっていたけど、そうじゃないのも何回か試してみるべきだったなあと思い始めた。実装激強マンか考察激強マンがきてくれると楽になりそう

来年もアジアに参加したい。来年は遠征できるようになっててくれ～

Codingame FallChallenge2020

情報少な目のDPをした。

GOLDの上の方だった。全体159位だった。

ルール

ポーションを作って金を得る。

金をたくさん持ってたら勝ち

4種類の材料がある。

常に5種類のクエリが存在する。

毎ターン行動を選ぶ。

相手と被った場合は両方が成功する。

こなされたクエリは消える。

スペルを唱えることで、自分が持っている材料を変えられる。

材料が11個以上になるようにはできない。

新しいスペルを習得できる。

1ターンで複数回唱えることのできるスペルもある。

スペルの習得は i 番目のものを習得するには i 個のレベル0素材を支払う必要がある。それぞれ i - 1番目のものに配置され、素材が配置されているスペルを習得する場合は、素材ももらえる。

6個作った人が発生したら終わり

左のやつにはボーナスがあるらしい。

やったこと

とりあえずできる中で一番利益がでかいものを選ぶことにする。

構造体とか、DEBUG出力用の関数も用意しておく。

(13日1:50)

Wood1昇格(13日2:15)

とりあえず無駄にはならないスペルも唱えてみることにする。

Bronze昇格(13日2:55)

とりあえずはじめはスペルを回収してからコスパが一番いいものを選んでみる？

DPで実装できそう。dp[スペルの使用状況][手持ちの素材]

それぞれ2^Nと14C4になる？

とりあえずスペル10個になるまで下から習得する。(17日3:00)

思ってるより重くてやばい(17日5:45)

スペルの使用状況無視してDPする。初回だけは使えるか判定できるので初回は判定する。一回でもアウトになって以降/2連続同じの使うは判定できないけど、大幅には変わらんやろ！ｗ(17日8:00)

ジャッジ激重だったのでようやくシルバーになった(17日9:07)

スペル7個持たせてたのを12個にする。(17日9:18)ここでsilver240

明らかに強いのを敵に取られる場合があるので、それの対策をする。具体的には、取ることができるスペルの中で一番強いのを貪欲に取ることにする。但し、同利益ならrepeatできるやつを優先(17日11:30)260->150

repeatを別に優先しない？(17日11:45)150->160

DPの復元する際に、コスト軽い方から来たのを優先する。(17日16:30)なんも変化なさそうで困った。

持つスペル12->15個にしてみる(17日17:00)130->160

ポーションの評価に、最後に(作ってから/learn)終えてからのターン数を持たせる？(17日17:45)170->110

スペル12個に戻す(18日20:00)180->160

最後に(作ってから/learn)終えてからのターン数にミスがあったのを修正(18日21:30)170->170

ポーションの余りコストも何らかの形で考慮したい。多く余るものを優先する？

とりあえず諸々の価値が同じとき、多く余るものを優先するようにした。160->170

目指してるのと違うのを作れるようになっても無視する？した。180->200

スペルのバランスも考慮したい。自分の持ってる呪文のdifの総和の絶対値を小さくする方に引っ張る(19日2:30)レート43.3->GOLD昇格

これにも重み付ける？つけないことにする。

コスト(個数)の重さにペナルティを課す？めっちゃ弱い->めっちゃ弱い

スクロール読もうとして読めてない場合がありそう？(直した)190->130

プラスの和のminもでかい方が嬉しい？(19日12:15)140->200

ダメそうなのでこれはやめようかな

スコアに加えてあまりも同等に評価する？(19日14:15)200->90

この変更により、たくさん余るのを優先しないようにする。(19日15:30)90->100

累計のスコア、ターンで重み付けしてみる？あまりにダメそうなのでしない。

最後の1個を作る場合はあまりじゃなくて加算値で評価(20日15:52)170->160

相手が目指していそうなものを検出する？した。

目指しているやつを作れるようになっていて、相手が後1ターン以下で作れるなら即作る。(20日17:15)160->170

コスト(個数)の重さにペナルティつけるのをやめる。(20日18:45)180->140

あまりの計算がミスっていたのを修正(21日3:35)150->120

作れる時でも、ぎりぎりまで粘った方がよさそうな場合はそうする。(21日6:00)110->140?

粘らないことにする。(21日14:20)140->130

相手より遅くなりそうなものの優先度下げる(21日14:45)120->170

相手が即作れる時だけ無視する程度にする？170->140

敵が6個完成させそうなときも特別処理する。(21日16:00) 140->100

スペル10個にしてみる(21日16:30)90->190

スペル15個にしてみる(21日17:00)190->120

ある程度揃ったらスペル習得打ち切る。(21日17:30)120->110

即brewの条件を厳しく？(21日18:10)100->80

即brewの位置を調整 & 無視の条件のミスを修正(21日18:50)90->130

戻す(21日19:00)130->170

相手が5個になったら即brewする170->170

ターン数のカウントのバグを修正(21日20:30)150->110

プラスもマイナスも少ないものを得るのを優先？(22日14:00)180->130

わずかに高速化(22日14:55)

実装の変更(22日16:00)

高速化(22日16:50)

無視の条件のミスを修正、無料魔法の優先度を上げる、少ないものの調整を一度打ち切る(22日17:15)

TimeOutがきついのでdp部分でターン数が10より多く必要なものは無視することにした。(22日23:10)

ちょっと変えた。

消した部分と実装のマージ、スペルの調整するので、スペル12個にしとく(23日3:50)

青の補充したい場合に、tomeを見るようにする。(23日4:20)

習得時に青の支出も考える(23日4:30)

習得してスペルを使うのもするようにする。但し初手のみ(23日10:20)90->70

どちらかが5個作ってるなら次先に作るようにする？せんとく

即作る場合に、作れるものが複数ある時に対応

初手以外にもスペルのやつつける。

なんやかんやあってやってないこと

あと何手で作れるかが正しく計算できていなさそう？出来ていそう

 全種類同程度に消費しやすい方が嬉しい？よくわからん。形を変えて実装した。

使用状況bitで持つのは無理だけど、集合は持つ？サイズで比較して小さい方が嬉しい。重いので無理そう。

初期魔法何回か使う場合に結構引っ張られていてつらい……つらいね。

無料魔法が少ないと……つらい！つらいね。

第4回アルゴリズム実技検定 感想+解法

序盤の問題の読解や細かい設定がつらい感じで序盤でかなり時間を使ってしまった。反面後半の問題で詰まることはあまりなく、全体としてはスムーズに解けたと思う。(100分41秒)

A:vectorにpair持たせてソートした。

B:100倍した。

C:全探索

D:左、右に絶対に行く必要のある回数の最小値がそれぞれ分かる。それでカバーできているか判定する。

E:全探索

F:mapに突っ込む

G:全探索

H:全探索を累積和で高速化

I:全探索と累積和とにぶたんで高速化

J:超頂点用意してdijkstra

K:各数列について転倒数と各数字の数を求めておく。数列に数列を追加する度にそれら情報を使って加算、更新する。

L:偶奇クエリと一点クエリを分けて考える。隣接する要素の差(ただし、添え字が奇数のものから偶数のものを引く)をmapに突っ込んでおく。

M:LCA+imos+マージテク

N:dp[i行目まで見て][i-2行目のbit][i-1行目のbit][i行目のbit]のときの通り数を上から更新していく定数倍軽めのO(2^{4W}*HW)の解法をとりあえず書いて高速化するか～って言ってコードテストで最大ケース試したら間に合ってしまった。

O:dp[i番目まで開錠したかしてないか決まってて、i+1番目以降施錠されているときの]=利益の最大値にi+1番目以降の宝箱による利益の総和を足したものを持っておく。人を右端でソートしてセグ木で更新。

ICPC国内予選2020

出ました。結果は5完で7位！nocowの5位には及びませんでしたが農工大記録に迫る好成績でした！アジアでも頑張ります。

A:一瞬で通ってた

B:一瞬で通ってた

C:1/2乗と1/3乗までの約数列挙すれば全探索できることが分かったので、即2分(120秒)探索を書いた。多分FA

D:二人がある程度考察を生やしていて、僕もちょっとだけ考察投げる。Div君がうまく実装してくれそうだったので実装を投げる。爆速で通してて4問分のペナは1番軽かったっぽい。

E:ふぇりんといろいろ喋ってるうちに30*30を4つに出来るね～とか、ドミノ並べるやつに似てるね～って言ってた。15*60を4つにするの賢すぎない？参りました。

F:ちょっと前にこどふぉで似た問題を見たので、ふぇりんと喋りながら詰めていくと解けた。

Undo可能UFで辺を軽い順に消していって、連結成分が最大じゃなくなった頂点集合を潰していった。

G:フローっぽいねって言ったら残りの二人がいろいろ考えてくれてた。

H:不可能って言ったらふぇりんも不可能って言ってた。

終盤までATELIERが死んでて大変そうだなあって言ってたら一瞬で2問通しててすごかった。

大学別4位でした。上三つはまあ無理。会津東北大阪に勝てたので満足です。

文句のつけようがない成績で素晴らしかった。アジアも勝ちたい。

去年は予選落ちだったので本当に良かった。MCC民は毎週練習に付き合ってくれてありがとう。

模擬国2020

出ました。

ライブラリは、どうしても自分のを使いたいものだけ印刷して、他は他の人に任せるか！ｗという気持ちで準備した。他の人どうしてただろう。(は？)(模擬国のあとでふぇりんライブラリを共有することになった)

Discordのサーバ(？)立てて各問題用にチャンネル用意した。

最初はDiv君がA,ふぇりんがB,僕がDCを担当することにした。

A,Bがいつの間にか通ってた。

C,どのセンサーが邪魔になるか判定するの無理じゃんって言って困ってた。あるセンサー範囲に入ってるのは連続で1回だけなので、入るタイミングでだけカウントすればよい。imos

D,人々が嘘を言いまくっていたが、僕とDiv君がほぼ同時に独立に解法出してておもろかった。こういう時よほどでなければ実装奪うようにしてるので実装する。

E,ずっと安定集合が云々って言ってた。終了30分前ぐらいにDiv君が2-SATって言ってふぇりんが通してた。助かる～

F,Eの裏でこっそり考えてた(は？)回転と展開図からの復元が出来れば良くて、回転は楽だったからいけるな！って言ってたけど復元が地獄方針引いて死んだ。

G,考えてない。

H,考えてない。

ととりにゃあたちに勝って笑顔になった。ありがとうととりにゃあ。

2円の共通接線

中心がにあって、半径がである円1と、中心がにあって、半径がである円2の共通接線を求めたい。

 原点を中心に回転させて、回転後において接線が常にx軸と平行になるようにしたい。またその時、接線があるとすれば、である。

更に、円2は接線の上側にある場合と下側にある場合があって、回転後の円2のy座標はである。

回転して、円2のy座標の条件を満たせる場合常に接線は存在していて、を回転させたものが回転前の円1と円2の共通接線となる。

ACPC2020day1準備

農工大セットを作りました。

やったこと

立命館の人に枠頂戴って言った。くれた。

日程決めるのに会津の人と北大の人と話した。

原案はgoogle スプレッドシートとhackMDで管理して、データセットとか問題文はgithubで管理した。 こういう技術的なやつ何もわからんかったんだけど、くれそんとかふぇりんが(準備して/教えて)くれて助かった。

セットについて

A:合宿のA問題っぽくなって好き。

B:これ正直かなり難しいと思ってるんだけど、解法聞いてたまげた。

C:writerした。結構コーナーケースがあると思っていて、testerが七転八倒していた。これテストケース作るとこまでかなり昔に終わっていて、直前に解きなおしたらはまってキレた。

D:い つ も の

E:TLEめっちゃ出ててウケた。

F:フローの押し戻しめんどくさいらしいけど、二部グラフなので簡単にかけて楽しい。

G:時間経つにつれてなんでここに置いたのかわからなくなってきたけど適切っぽくて良かった。

H:writerした。設定が変わりまくって大変だった。読みにくかったのはごめん。コーナーケース6個ぐらいあったり、片方のルールだけやるTLE解書くのしんどかった。(先に(MLE/RE)になるので)

途中Gまでしかない状態で(Hは設定変わりまくってる途中)hecさんにテスト頼んだら4時間半で全完されたので、90分で7完するチームもそこそこいるであろうことが予想されてかなり焦った。(実際に2チーム(？)がやった)

校正について

堅い文章書けなくてごめんって言いながらねちねちミスだけ指摘してた。