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チーム(？)がやった)
校正について
堅い文章書けなくてごめんって言いながらねちねちミスだけ指摘してた。
Japan Alumni Group Summer Camp 2015 Day 3
Japan Alumni Group Summer Camp 2015 Day 3のバチャをやった。6完57011ペナ
B:
シフトの仕方は以下の4通り
・右シフトのみ
・左シフトのみ
・右シフトした後左シフト
・左シフトした後右シフト
各位置について自分より右にある1の中で一番左にある1の位置を持っておくと良い。
D:
和が10^nより大きくなる場合と、小さくなる場合に分けて考える。
大きくなる時
和が9より大きいペアを1個選ぶ。->和が9となるペアを先頭に置けるだけ置く。->残りを昇順にペアにして後ろに置くことで。最初に決めたペアに対して最小な和が作れる。
小さくなる時
和が9より小さいペアを1個選ぶ。->和が9となるペアを先頭に置けるだけ置く。->残りを降順にペアにして後ろに置くことで。最初に決めたペアに対して最大な和が作れる。
ペアの数は高々100個なので十分全探索できる。
E:
gcd(a,b)でcが割り切れなかったら-1
cがaかbと等しいなら1
a,b,cをgcd(a,b)で割っておく。
aからbに注いでいくことを考える。
操作を(a+b)*2+1回行うと1周し、aもbも空になる。
逆の操作をしても同じ。
拡張ユークリッドの互除法などでどのタイミングでcが登場するか調べる。
F:
角度の制約を考えると、N角形のときに直角にできる角の数kは
k<(2n+4)/3
となる。また、実際に上限が達成できる。
J:
自分の約数kについて、(N-k)/kの約数の数が分かれば良い。
AGC044-C Strange Dance
ある桁は自分より小さい桁に対して影響を及ぼさないので、操作後の下i桁目について、操作前の下i桁の数によってのみ決まる。
サルサが流れると、すべての桁が変わる。(0のときは変わらないが、変わると考えても困らないので変わると考える。)
サルサが2回流れると元に戻るので、圧縮できる場合がある。
ルンバが流れると、一番下の桁は変わる。また、下i桁目で繰り上がりが発生したときに下i+1桁目が変わる。
p(i,A)を、下i桁がAであって、ルンバによって下i桁目で繰り上がりが発生した時間の集合 と定義する。
操作前の下i桁がAで、操作後の下i桁目がどうなるかを考える。
ルンバによって下i桁目が変わるタイミングは、p(i-1,A % 3^(i-1))が分かっていると分かる。それらの間にあるサルサの数は累積和などで分かるので、シミュレーションにはp(i-1,A % 3^(i-1))回ぐらいかかる。
pのサイズの総和はO(N*|T|)なので間に合う。
第二回 アルゴリズム実技検定 解説記事
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位を独走する文明に対しての他の文明同士での連合を参加者同士の外交でできたり、たまには裏切りもあったりします。
・感想戦もできるので、自分には理解できなかった行動の秘密を探れて良いです。
僕は航空機が登場したころの、全ユニットがそこそこ強い時代の戦争が好きです。
