olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

civ6マルチ プレイレポ

RaF持ってない人がいたので無しでやる。以前そのような状況でマルチをやった人がいるらしく、その場合はプレイできなかったらしい。

 

1日目(1~80ぐらい)
首都に隣接している6マスのうち5マスは川沿いでラッキー。
序盤にベトナムが異常な時代スコアを出している。自然遺産を見つけたのかもしれない。
他の国家の科学力が5とかの時代にベトナム、マヤが20も科学力を出している。どうやらヨセミテを取り込んでいたらしい。
この頃日本やベトナムと遭遇している。どうやらハンガリーパンゲアの西側に生まれたようだ。
ベトナムが都市数、人口、科学力で優れていることからヴォイ・チェンラッシュに警戒するという名目で日本と有効を結ぶ。
ハンガリーは山沿いに生まれたのもあって科学力が結構出ていて1日目終了時点ではベトナム、マヤが100ちょっと、ハンガリーが80程度、日本、ドイツが50程度科学力が出ていた。配置も概ねわかってきていて、北西部にハンガリー、南西部にドイツ、中央西に日本、中央東にベトナム、東にマヤがいるらしい。(途中に世界の様子が分かるスクショを貼っている)
ヴォイ・チェンラッシュ対策に日本には全力で兵営と防壁を作ってもらい、ハンガリーは黒軍を量産しておき、いつでも介入できる状態にしておく。
この辺りまでで日本、ハンガリーベトナムが宗教を創始している。ハンガリーは食料が出る証と都市からゴールドが出る証を選んだ。

 

2日目(81~110ぐらい)
予想に反してベトナムは日本を殴ることなく進行し、内政状況も大きな動きもなく進んでいく。我がハンガリーは日本、ドイツ、マヤと同盟を結んでおり、安心して内政できる状態になっている。
ここで突然ベトナムベトナム-マヤ国境にある都市国家のヴォリンに宣戦布告する。マヤはヴォリン防衛のためにベトナムに宣戦をし、マヤとの軍事同盟のボーナスを乗せるため及びベトナムの拡大を恐れたハンガリーベトナムに宣戦する。
各国の戦争序盤の主力は
ベトナム:射石砲、ヴォイ・チェン(野戦砲の技術はある)
マヤ:野戦砲、胸甲騎兵(らしい)
ハンガリー:フッサー、弩兵、射石砲、騎士
南の方でベトナムと国境が近いハンガリーは南からベトナム西部、中部に進軍する。同盟3つと軍事同盟の乗ったフッサーがヴォイ・チェンを撃破していきハンガリー優勢で2日目を終える。
戦前の科学力はベトナム、マヤが200程度、ハンガリーが150程度、日本が130程度、ドイツが100程度

 

3日目(111~120ぐらい)
ハンガリーベトナム西部の都市を1都市焼くのとほぼ同時期にベトナムに戦車が登場し始めハンガリー軍は撤退し特に何もない状況が続く。どうやらマヤとベトナムは小競り合いのようなことしかしておらず、ベトナム軍の大部分がハンガリー軍と戦っていたらしい。また、マヤとベトナムが和平を結ぶ。
この時期の各軍の主力
ベトナム:野戦砲、戦車、大砲
マヤ:野戦砲
ハンガリー:野戦砲、射石砲、フッサー、胸甲騎兵
また、この日終了頃に科学力はマヤが280程度、日本が250程度、ハンガリーベトナムが180程度、ドイツが100程度になっている。
ここで日本、ハンガリーベトナムの3国で会談が発生し、ハンガリー、日本の説得、交渉の結果、ヴォリンを含めたマヤ西部の3都市をベトナムが所有して良いという条件で3国で対マヤ連合を組むことになる。またこの頃、マヤやベトナムで航空機が実用化される。

 

4日目(121~140ぐらい)
開始後しばらくしてベトナムがヴォリンに宣戦、その後ハンガリー日本がマヤに、遅れてベトナムもマヤに宣戦する。ベトナムの大砲、爆撃機の活躍が大きく、3都市占領の戦争目標を達成する。
この頃日本やハンガリーの外交勝利ポイントは10ポイント近く溜まっており、我がハンガリーも外交勝利を目指すべく戦略を練っていたのだが、なんとRaFがないので自由の女神がないことに気がつく。マハーボディー寺院、世界会議と合わせて140ターンの会議で19ポイントになるはずだったがあてが外れてしまう。
また、この頃日本が科学力を大きく伸ばしており、日本が410程度、ハンガリーが310程度、ベトナムが250程度、ドイツが200程度、マヤが70程度の科学力を出している。
ここでベトナムと会談が発生し、マヤをベトナムが吸収、日本を2国で分割する条件で対日本戦を行うことになる。現在軍事力は日本がベトナムハンガリーの1.4倍ぐらいあるが、日本にはアルミが湧いておらず、アルミユニットが主役である時期に決戦をすることで有利になるはずである。ドイツはベトナムとかなり仲良くしており、アルミが日本に渡ることはないらしい。ベトナムに強く敵意を抱いていそうなマヤの動きがあまりにも読めなくて不安である。ここでユニットのゴールドでの購入コストが半分になり、現金所持量、毎ターン収入の両方でトップであるハンガリーも軍事的に優位に立てるかもしれない。

 

5日目(141~160ぐらい)
日本が信仰の守護者持ちの宗教を持っていたのでエレバンパワーで塗り替え始める。ベトナム、日本が宗教勝利に気づいていないことに期待してそれとなくベトナムにも使徒を向かわせてみるが、防衛されたのでベトナムを塗り替えるのはあきらめて、マヤの方に使徒を連れていくことにする。
この辺りで日本が異常に高圧的な態度で交渉をかけてくる。焦っているのだとは思うが、高圧的なので何かあるのかもしれないと思い、内心ではかなり恐れていたが攻めないことには勝ちはないので強い気持ちで突っぱねる。
ハンガリーと日本の同盟が切れたタイミングでハンガリーベトナムが日本に宣戦。(マヤだけ若干ベトナムに削られているが、左下の地図で各国の領土が大体分かる。)

f:id:olphe:20210403000328j:plain

ハンガリー日本国境

日本はジェット戦闘機の優位で序盤は戦争を優位に進めるも、徐々に物量の差に押され始め、ちょうど5日目終了のタイミングで日本が滅びる。
終戦直前に事前の分割案をベトナムが無視し、ウランのある都市を占領する。すでにベトナムにはウランが2タイル湧いていて、それに対しハンガリーは占領した日本の都市にしかウランが湧いていない状態で、ベトナムがウランの数で圧倒的優位を築く。
またこの辺りで同意のもとマヤがAIになる。

 

6日目(161~???ぐらい)
会議で核分裂兵器が作りにくくなった。この時点でハンガリーには核兵器はなく、ベトナムには核兵器が1,2発ぐらいしかないと思っており、核分裂兵器が作りにくくなればウランの優位を生かしにくくなると考えた。
同盟が切れる直前の国境の様子はこんな感じでチャーキエウの飛行場にいるジェット爆撃機ハンガリーの首都であるブダを核攻撃できるので視界が取れるようになるまでに(おそらく1ターン)飛行場を潰せるようにジェット戦闘機を寄せる。ベトナムのジェット戦闘機もかなりあることが分かる。
技術的にはロケット砲、近代的対戦車砲、近代的機甲部隊が出せるが陸軍がどれほど役に立つだろうか。
また、巨大戦闘ロボットのアップグレードで対空攻撃+100のアップグレードが近くなってきて、ロボットによる核の迎撃を考え始める。

 

f:id:olphe:20210403000231j:plain

ハンガリーベトナム国境(旧日本領)



 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

マヤの方に宗教が広まっていて塗り替えられていないのを見てちょっと頑張れば宗教で勝てるのでは?となる。エレバンパワーで75%カットの使徒と3倍の使徒を量産しまくると勝った。(166ターン目、画像では勝ってないけどあと1ターンした後の画像)

f:id:olphe:20210403000626j:plain

モグラ

f:id:olphe:20210403002917j:plain

f:id:olphe:20210403002919j:plain

f:id:olphe:20210403002922j:plain

f:id:olphe:20210403002924j:plain 

その他

区域の生産力アップ、徴用、フッサーをかなり役に立てることができて、文明の強みに沿ったプレイングをある程度出来て良かった。

また、先進国というほどではないが周りの国よりは強いという時期が長かったので、いろんな争いに首を突っ込むことができて楽しかった。地域大国プレイも悪くない。

ちなみにベトナムは核を4発も持っていたらしい。

(最初書くつもりなかったので)序盤のスクショなくて、ごめん。

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連続同じの使うは判定できないけど、大幅には変わらんやろ!w(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位には及びませんでしたが農工大記録に迫る好成績でした!アジアでも頑張ります。

 

 

f:id:olphe:20201106213433j:plain

 

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

出ました。

 

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

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

 

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

 

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

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

 

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

 

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

 

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

 

G,考えてない。

H,考えてない。

 

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

 

2円の共通接線

中心が(0,0)にあって、半径がr_1である円1と、中心が(x,y)にあって、半径がr_2である円2の共通接線を求めたい。

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

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

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