第二回 アルゴリズム実技検定 解説記事
A 今地上にいるかいないか、目的地が地上にあるかないか4通り場合分けします。
B それぞれの文字が何個あるか見ます。
C 下の行から順に見ていき、Xを見つけたら右上、上、左上のそれぞれについて空白でなければXにします。
D 文字列全部列挙してSのすべての開始位置について一致しているか見ます。
E シミュレーションをします。移動経路をグラフにすると、明らかに有向サイクルになるのでN手以内に戻ってくることが分かります。
F 常に今選べるタスクの中で得られるポイントが最大のものを選ぶのが最適です。
G dequeを使うと追加も削除も効率良くできます。
H スタートを0、ゴールを10と考えて、すべてのマスについて、自分以下の数字を一度以上踏んでいるときの最小の移動回数を考えます。
I シミュレーションをします。一人当たりの試合回数は高々N回なので間に合います。
J 最初の閉じ括弧が見つかったときに、その括弧対について操作を行います。操作回数は高々N回なので間に合います。
K dp[i文字目まで見て][開き括弧の余剰がj個のときの]コストの最小値を考えます。
L 常に今取っても今後破綻しないようなものの中で最小のものを、最小のものが複数存在する場合は一番左のものを取るのが最適です。
M 日をMOD Dで考えます。すべての日について、次に同じ種類の定食を食べるまでに何回食堂に行くかを求めます。それは各種類の定食が出る日付を持っておくと分かります。その情報が分かるとダブリングが出来るので各人について答えをO(logD)で求められます。
N あるx座標を含むような敷地集合(Xとする)が分かっているとき、あるy座標を含むような敷地集合は敷地のy座標の最小値でソートしたものと、敷地のy座標の最大値でソートしたものを持っておくと、二分探索などで求めることができます。また、そのような集合のコストはセグメントツリーなどを用いると高速に計算できます。x座標を単調に変化させるとき、各敷地は1回ずつXに追加され、1回ずつXから削除されます。なので、クエリをx座標の昇順に見るとXへの追加と削除にO(N)かかり、各クエリの処理にO(log N)かかります。
O 最小全域木で根付き木を作って、全域木に使われている辺については、全域木のコストが答えです。そうでない辺については、全域木に含めて、その辺の端点間のパス上の最大の辺を消すのが最適です。そのような辺はダブリングなどで求めることができます。
AtCoderで灰色になりすますまでにやったこと
AtCoderで灰色になりすました！！！！！！！！！！！！！！！
沢山コンテストに参加してようやく灰色になりすませたのでとてもうれしいです！
これから競技プログラミングを頑張っていきたいです！
参考にしたツイート
AtCoder青になるまでにやったこと
— prd🦍 (@prd_xxx) 2018年4月11日
・ChromeでAtCoderのマイプロフィールを開く
・F12を押す
・それらしいところに"user-cyan"等と書かれているので"user-blue"に書き換える
・やったぜ pic.twitter.com/WPEpgOObZM
チーム練(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本選ぶ。拡張ユークリッドの互除法とかでできる。
G:蟻本p185
H:dp[体力][毒][ポーションの使用状況]
I:LCAとダブリングらしい。
L:作った後ずらす
CivilizationV紹介
この記事は
プログラマーのオススメのゲームの話をする Advent Calendar 2019 - Adventar
の5日目の記事です。
昨日の記事は
"お手軽オートバトル" ハースストーン バトルグラウンドの話 & 「激闘！ドラゴン大決戦」まで1週間 - fal_rnd_log
明日の記事は isk_tkns さんの Carnage Heartシリーズについて です。
CivilizationVは太古の時代から情報時代まで文明の指導者になって、強い文明をつくるゲームです。いくつか勝利条件が決まっていて、いずれかの勝利条件(4+1種類ある)を満たした文明が勝ちます。
このゲームはシングルプレイとマルチプレイがあります。ぜひマルチプレイをやりましょう！
勝利条件
制覇勝利…全文明の首都を征服します。勝者が歴史です。
科学勝利…地球から脱出する宇宙船を作り、地球から脱出します。
文化勝利…全世界に自国の文化を浸透させます。現代日本でいうと、世界の多くの人がマンガやアニメのファンみたいなものでしょうか。
外交勝利…世界議会で世界の指導者として認められます。
また、誰も以上の条件を満たさずに一定期間が過ぎると、強そうな文明が勝ちます。
文明
歴史上存在(した/している)文明の一部の指導者になることができます。
文明によって、固有のユニットや、建造物が与えられているので、それらを活用して強い文明を築きましょう。
文明の礎
文明には都市が必要です。
都市において色々な生産活動ができます。戦争のためのユニットをつくったり、科学や文化、宗教等の活動のための建造物を建てたりできます。また、世界で一つしか建てられない、強力な効果を持つ遺産を建てることもできます！遺産は早い者勝ちです！ほかの文明に取られる前に、いち早く建造しましょう！マルチプレイだと遺産の恨みで戦争になることも
また、都市ごとに人口があって、人口が増えるほどあらゆる活動が活発になります。
(人口が多いと、生産力も科学力も文化力も高い！(高くなりやすい))
他の要素
古代遺跡を採掘するとちょっとしたボーナスがもらえる。
蛮族は放置していると自国をどんどん荒らしていく！すぐに退治しよう！
都市国家と仲良くしているとその特徴に応じてボーナスがもらえるので仲よくしよう。
宗教を創始して、世界中に広めよう。信徒たちも役立ってくれるはずだ。
マルチプレイ
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の嘘解法で盛り上がる。
・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の解法を生やす(←これ実装して正しい解法だったのか早く確認してください。)
--------------コンテスト終了------------------
I，1行直したら通ったけど
— フェリン (@ferin_tech15) November 17, 2019
↑これは何ですか
全体的にふぇりんが強かったね。あとはツイッターとか見て楽しそうだなあ～って言ってた。来年はアジアに行きたいなあ！！！！！！
