olpheの競プロ帖

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

AtCoderで灰色になりすますまでにやったこと

AtCoderで灰色になりすました!!!!!!!!!!!!!!!

f:id:olphe:20200226165733j:plain

沢山コンテストに参加してようやく灰色になりすませたのでとてもうれしいです!

これから競技プログラミングを頑張っていきたいです!

 

 

 

 

参考にしたツイート

 

チーム練(2016バンコク)

寝坊した。完

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 Lが自明っぽいらしいので聞くと、自明っぽい。ちょっと細かい条件とかいろいろあってやだなあって言いながら書くと通る。(0:14)

Bも自明っぽいらしいので聞くと、TLEしないか心配になるが、満点が同じものをまとめてやると良さそうなので書く。TLEする。コードをよく読むとオーバーフローしていたり、実はまとめていなかったりしてペナを重ねる。

Iも自明っぽいらしいので書いてもらうとバグる。めっちゃペナ生えてる。実家のような安心感。

Bを直しつつ投げて、めっちゃペナを生やす。

Iが通る。(2:00)

ごちゃごちゃいじってたらなんかBも通る。(2:03)

Dは自明!って言って書くと落ちる。よく考えると嘘だった。

でぃぶくんがGを蟻本から見つけてきたのでフェリンに書いてもらう。バグる。

よく読むと他の問題から引っ張ってきた出力形式が違うらしい。同じセットで出力形式違うとかある?通る。(3:17)

Hもよく考えると自明らしいので書いてもらう。バグる。

毒は負になり得るのでは?とか言ってた。

Fはみんなでこれ見たって叫んでた。

Dは

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1375

なので書くと通る。(4:29)

Hは入力の受け取り方が間違っていたらしく、直すと通る。(4:55)

 

6完1258ペナ

当時だと13位

 

B:dp[使った人の数][得点]=通り数 を満点ごとにやる

D:元の直線に一番近い直線を2本選ぶ。拡張ユークリッドの互除法とかでできる。

F:D - Game on Tree

G:蟻本p185

H:dp[体力][毒][ポーションの使用状況]

I:LCAとダブリングらしい。

L:作った後ずらす

CivilizationV紹介

この記事は

プログラマーのオススメのゲームの話をする Advent Calendar 2019 - Adventar

の5日目の記事です。

昨日の記事は

"お手軽オートバトル" ハースストーン バトルグラウンドの話 & 「激闘!ドラゴン大決戦」まで1週間 - fal_rnd_log

明日の記事は isk_tkns さんの Carnage Heartシリーズについて です。

 

 

CivilizationVは太古の時代から情報時代まで文明の指導者になって、強い文明をつくるゲームです。いくつか勝利条件が決まっていて、いずれかの勝利条件(4+1種類ある)を満たした文明が勝ちます。

このゲームはシングルプレイとマルチプレイがあります。ぜひマルチプレイをやりましょう!

 

勝利条件

制覇勝利…全文明の首都を征服します。勝者が歴史です。

f:id:olphe:20191201042601j:plain

戦争をする前はたくさんユニットを作ろう。

f:id:olphe:20191205033115j:plain

都市を占領した!この調子でどんどん都市を占領しよう!

科学勝利…地球から脱出する宇宙船を作り、地球から脱出します。

 

f:id:olphe:20191205033318j:plain

ロケットのパーツを作ろう!

文化勝利…全世界に自国の文化を浸透させます。現代日本でいうと、世界の多くの人がマンガやアニメのファンみたいなものでしょうか。

f:id:olphe:20191201042613j:plain

相手国に対して文化が浸透したようです。

外交勝利…世界議会で世界の指導者として認められます。

f:id:olphe:20191201042619j:plain

世界議会の票をたくさん集めよう

また、誰も以上の条件を満たさずに一定期間が過ぎると、強そうな文明が勝ちます。

 

文明

歴史上存在(した/している)文明の一部の指導者になることができます。

文明によって、固有のユニットや、建造物が与えられているので、それらを活用して強い文明を築きましょう。

 

文明の礎

文明には都市が必要です。

都市において色々な生産活動ができます。戦争のためのユニットをつくったり、科学や文化、宗教等の活動のための建造物を建てたりできます。また、世界で一つしか建てられない、強力な効果を持つ遺産を建てることもできます!遺産は早い者勝ちです!ほかの文明に取られる前に、いち早く建造しましょう!マルチプレイだと遺産の恨みで戦争になることも

また、都市ごとに人口があって、人口が増えるほどあらゆる活動が活発になります。

(人口が多いと、生産力も科学力も文化力も高い!(高くなりやすい))

 

他の要素

古代遺跡を採掘するとちょっとしたボーナスがもらえる。

蛮族は放置していると自国をどんどん荒らしていく!すぐに退治しよう!

都市国家と仲良くしているとその特徴に応じてボーナスがもらえるので仲よくしよう。 

宗教を創始して、世界中に広めよう。信徒たちも役立ってくれるはずだ。

f:id:olphe:20191201042555j:plain

今回は信徒からお金がもらえるようにした。


 

 

マルチプレイ

CivilizationVはマルチプレイが非常に面白いゲームです。

理由は3点あって、

・参加者が人間なので、AI特有の変な挙動や変なボーナスが無くて、かなり対等な状況で勝負できる。

・外交の展開が面白くて、世界大戦になることや、1位を独走する文明に対しての他の文明同士での連合を参加者同士の外交でできたり、たまには裏切りもあったりします。

感想戦もできるので、自分には理解できなかった行動の秘密を探れて良いです。

 

僕は航空機が登場したころの、全ユニットがそこそこ強い時代の戦争が好きです。

 

 

 

 

 

 

チーム練(2018ソウル)

最初は英語が読めないおるふぇがテンプレを書くことにする。(本番だと多分テンプレ5行だけど(ア)(インフラっぽいこと(?)も出来たいね))

 

 Dがやるだけなので書く。(0:11)

ふぇりんがLがフローっぽいと言っていたので聞いてみたら貪欲でできることが分かるので実装する。コーナーの処理を忘れていて1WA(0:41)

ふぇりんとでぃぶがKが2-SATっぽいと言ってたので任せていると通る。(1:41)

おるふぇがEを解けたと主張して実装するもWAが出たり、TLEを連発する(?)

でぃぶがAを解いて、ふぇりんが実装していた。WAが出る。

でぃぶがBを解いて実装する。サンプルが合わない。今回も地獄の3並列デバッグが始まる。

でぃぶとふぇりんがFを解けたらしいので、実装キューに入る。実装キューの容量がでかすぎるだろ。

Bのしょうもないミスに気づき、通る(3:06)

Eを実数から整数にするとTLEが消える。

でぃぶがFを苦しみながら実装していた。サンプル合わないのが長く続いてたけど、一発ACしててすごい。(4:01)

Eを修正して通す。(4:16)

あとみんなでAのデバッグしていたけど通らず、モノイドが間違っていたらしく、1行修正したものが通ってた。

 

6完961ペナ、当時だと20位相当です。

チーム練(2018ジャカルタ)

でぃぶが一瞬でIを通す。

ふぇりんがからAの概要を聞いた僕が一瞬って言う。WA

でぃぶが一瞬でLを通す。

このへんで、僕が1問読む間にチームメイトは2~3問読んでいることに気が付く。

ふぇりんが昨日K解いたって言ってたので任せる。無限時間かかってたけどAC。

僕がJを解けたと主張して、ふぇりんがDを解けたと主張したので、軽そうなJから実装に入る。サンプルが合わない。交代してDを書いてもらう。WA。WA。Aを考えていたでぃぶからコーナーケースが届いたので実装。WA。度重なるコーナーケースの列挙ののち、DがWAっている。デバッグの結果JもWA。地獄のデバッグ3並列。

落ち着いた当たりで突然DもAもJも通りだす。20分で3問通す人になってしまった。

でぃぶと僕でGの解法を出し、実装するけど一生WA~って言ってる間にふぇりんとでぃぶがHの解法を生やす。交代してもらってWA。2並列デバッグが始まる。

ここも突然通りだして、7分で2問解く人になっていた。

何故かここまでFが読まれていなかったので読んでもらうと、自明であることが分かったので実装。WA。今回は比較的すぐ通る。

Eは見えなくて、Bは解けるとしたらふぇりんなんだけど、やりたくね~って言ってたので、残りは一生Cのパズルをやっていた。

 

9完1434ペナ当時だと6位。

 

A 0と1の数が違うときは少ない方に揃えて、そうでないときは末尾の文字を無視する。

F セグ木

G 最短経路っぽい気持ちになる。

J LIS

 

全部で9回もペナルティ生やした。実装が下手すぎます。実装うまくなりて~~~~~

 

ICPC 2019 Asia Yokohama Regional 不参加記

国内予選(95位)落ちたので参加していませんでした。

学内1位だとしても落ちてるの、弱すぎない?(俺は橙コーダーやぞ)(当時は黄コーダー(俺は黄コーダーやぞ))

 

ふぇりんとオープンに出ます。

-------------コンテスト開始-----------------

・0:04 ふぇりんがAを書き始める。

・0:07 おるふぇがBを実装キューに投げる。結論から言うとここはPCを奪うべきだった。

・0:22 ふぇりんがAを通す。1完22ペナ

・0:30 おるふぇがBを通す。2完53ペナ

・0:45 Eの嘘解法で盛り上がる。

f:id:olphe:20191119101709j:plain



・0:49 GとHが通されているのに気づく。

・0:51 ふぇりんがHの実装を始める。

・0:58 ふぇりんのHが落ちる。

・1:06 ふぇりんがHの嘘を発見する。

・1:12 おるふぇがGを実装キューに投げる。

・1:23 おるふぇがGの実装を始める。

・1:55 ふぇりんがHの実装を始め、おるふぇが昼食で離脱する。

・2:08 ふぇりんのHが落ちる。

・2:12 おるふぇが復帰

・2:18 デバッグをし嘘を発見する。

・2:23 ふぇりんがHを通す。3完237ペナ

・2:34 おるふぇのGが落ちる。

・2:36 ふぇりんがEの解法を生やす。

・2:40 おるふぇのGが通る。4完417ペナ

・2:53 ふぇりんのEが通る。5完591ペナ

・3:05 ふぇりんがIの解法を生やすもおるふぇが理解しないので質問タイム(は?)

・3:22 ふぇりんがIの実装に入る。

・4:00ぐらい おるふぇがDの解法を生やす(←これ実装して正しい解法だったのか早く確認してください。)

--------------コンテスト終了------------------

 

 ↑これは何ですか

 

全体的にふぇりんが強かったね。あとはツイッターとか見て楽しそうだなあ~って言ってた。来年はアジアに行きたいなあ!!!!!!

ACPC参加記(2019)

 

ACPC1日目

会津合宿鈍行部員なのでこれで来る。

南栗橋以降は人が少なく、席が広いのでかなり快適なんですが、電子マネーが使えない場合があるので、切符を買っておくとかなり無難であるように思います。それ以外は無限に快適でした。春日部からの比較ではありますが、新幹線ルートと比較して1時間で3000円と快適さを買えます。

 

集合が12:30のところ、12時過ぎに会津若松駅に着く。

社会性の無さを発揮してこれらをしていた。

 

 

 コンテストは、てんぷらが強くて優勝してしまった。

 

これはボドゲ

 

ホテルは東横に泊まったんですが、館内着(?)とタオルと歯ブラシと電源と朝食があるのが良くて、壁が異常に薄いのが良くなかった。

ACPC2日目

この日は集合時間に間に合った気がする。偉すぎてびっくりしてしまった。

 

この日のコンテストはかなりいい感じのチーム戦が出来ていて、実力以上の結果だったと思うんだけど、こたつがめに負けてしまった。オンサイト2位。

 

問題の懇親会なんですが、僕個人としてはちょっと飲んだ頃から未成年にかなり警戒されていてすまねぇ~って言っていた。(実は結局1問分も飲んでいないんですよね)

beet君が酔って壊れていたのがかなり面白くて、beet君が人間らしいことをしていると面白いですね。

 下は参加者から参加記での使用許可を得た写真たち。

f:id:olphe:20190920232332j:plain

倒れてもなお酒を飲むbeet(流石に回収されてた気がする)

f:id:olphe:20190920232111j:plain

https://twitter.com/IKyopro/status/1174647251865460736

f:id:olphe:20190920232210j:plain

つぶあんくんに運搬されるbeet



ACPC3日目

今日は9時集合だったけど、社会性の無さを発揮して集合時間より遅く出発するバスに乗る。

 

コンテストは割と温まっていたけどbeet君が暫定1位風船を奪いに来たのでキレてしまった。いや優勝ですではないんだよな。僕らが全完したら逆転やが~って言っていたけど全完ならず。個人としてはBだけ通すマンになってしまった。オンサイト2位。

 

解散後はTAB君わく君と富士の湯に行った。富士グランドホテルに泊まると毎日入浴券がもらえるの良すぎませんか?次参加することがあれば富士グランドホテルに泊まります。

 

帰りはリバティに乗って帰りました。。安くて広くて人が居なくてそこそこ速いので大好きになってしまった。これも注意点として、切符を買うと安心です。

 春日部までの新幹線ルートと比較して、1時間で2000円を買えます。

 

その他

合宿にセットを出したくなってしまった。