みんなのプロコン 2019 F - Pass
問題概要
n人のすぬけ君が1列に並んでいて，両手にボールを持っている．両手のボールの色は青2つ，赤2つ，赤青1つずつのいずれかのである．
以下の操作を2n回繰り返した際にできるボール色の列のパターン数を998244353で割った値を求める．
操作: n人のすぬけ君それぞれが，自分の持つ2つのボールのうち1つを1つ前のすぬけ君に渡す．ただし先頭のすぬけ君は高橋君にボールを渡す．高橋君はもらったボールを順番に並べてボールの列を作る．
解法概要
実は「列のi番目のボールは，前からi番目以内のすぬけ君が持っているボールならどれにでもなりうる」． これはすぬけ君の人数に対する帰納法で証明できる． すぬけ君が0人の時は明らか． すぬけ君が(k-1)人で成り立つと仮定した時，すぬけ君がk人の時は先頭のすぬけ君のボールのうち一方が1番目のボールになる．先頭のすぬけ君のもう片方のボールは(k-1)人のすぬけ君で作った列のうち2番目以降どこにでも挿入できる． よって，
$ dp_{n,r} $= n個ボールを並べていて，そのうち赤いボールはr個のときの並べ方の数
として，DPで計算できる．
DPの初期値は，$ dp_{0,0} = 1 $．0個のものを並べるやり方は1通りなので． DPの遷移は， 先頭(i+1)人のすぬけ君が持つ赤いボールを並べきっていなければ $ dp_{n+1,r+1} += dp_{n,r} $，並べきってしまっていたら$ dp_{n+1,r+1} = 0 $． 同様に，先頭 (i+1) 人のすぬけ君が持つ青いボールを並べきっていなければ$ dp_{n+1,r} += dp_{n,r} $，並べきってしまっていたら$ dp_{n+1,r} = 0 $．
(ちなみに最初はボールがrgbの3色あると誤読していたが，実は2色だった．)
ソースコード
#include <iostream> #include <string> using namespace std; typedef long long ll; const ll MOD = 998244353LL; ll dp[4001][4001]; int main() { string s; cin >> s; int n = s.length(); dp[0][0] = 1LL; int red = 0, r = 0; for(int i=0;i<2*n;++i) { if(i < n) { r = 2 - int(s[i] - '0'); red += r; } for(int j=0;j<=min(i,red);++j) { if(j < red) { dp[i+1][j+1] += dp[i][j]; } else { dp[i+1][j+1] = 0; } dp[i+1][j+1] %= MOD; if(i-j < min(i+1,n)*2-red) { dp[i+1][j] += dp[i][j]; } else { dp[i+1][j] = 0; } dp[i+1][j] %= MOD; } } cout << dp[2*n][red] << endl; }
所感
最近基礎的なDPなら理解できるようになってる気がする．
Mujin Programming Challenge 2018 E - 迷路
問題概要
N行M列 ($ N, M \leq 1000$) のグリッド上をロボットがSからGまで移動するのに最短何秒かかるか求める． ただし，1マス上下左右に動くのにかかる時間は1秒で，毎秒動ける方向が決まっている．動ける方向は長さk ($ k \leq 100000$) の文字列dによって与えられる．いま，ロボットが動き出してからt秒後とすると，ロボットが動ける方向はdのt%k文字目 (0-indexed) で表される．
解法概要
「ロボットが動き出してからt秒のとき，次にロボットが1マス上 (下・左・右) に動けるのは何秒後か」をあらかじめ計算しておくことで，ダイクストラ法によって最短時間を求めることができる．ロボットの動ける方向はk秒周期で決まるので0秒目からk-1秒目までの「次にロボットが1マス上 (下・左・右) に動けるのは何秒後か」を保持しておけばよく，事前計算の最悪時間計算量は$ O \left( k \right)$ ．ただし，d = UDRRLでt=4のときの "次に上に動ける時間" など，次に指定の方向に動くまでに t%k = 0 をまたぐ場合があるので，プログラムでは2k秒ぶんのループを回している．
この事前計算の結果をグラフの辺のコストとし，上下左右に隣接しているマス同士にエッジが張られていると考え，ダイクストラ法を適用する．ダイクストラ法の最悪時間計算量は$ O \left( \left(V+E\right) \log V \right)$ (V,Eはそれぞれ頂点，辺の数) なので，制限時間の2秒には間に合う．
ソースコード
#include <iostream> #include <queue> #include <string> #include <utility> using namespace std; typedef pair<int, int> Pii; typedef long long ll; const int dyx[4][2] = { { 0, 1}, {-1, 0}, {0,-1}, {1, 0} }; const char dyx_chars[4] = {'R', 'U', 'L', 'D'}; const ll INF = (1LL << 60); int n,m,k; string s[1001],d; ll shortest[1001][1001], times[100000][4]; struct State { ll t, y, x; State(ll t, int y, int x): t(t), y(y), x(x) {} bool operator>(const State& s) const{ return t > s.t; } }; void calc_times() { fill(times[0], times[k-1]+4, -1); for(int j=0;j<4;++j) { if(d[k-1] == dyx_chars[j]) times[k-1][j] = 1; } for(int i=2*k-2;i>=0;--i) { for(int j=0;j<4;++j) { if(d[i%k] == dyx_chars[j]) { times[i%k][j] = 1; } else { if(times[(i+1)%k][j] == -1) { times[i%k][j] = -1; } else { times[i%k][j] = times[(i+1)%k][j] + 1; } } } } } void dijkstra(Pii start) { priority_queue<State, vector<State>, greater<State> > que; que.push(State(0LL, start.first, start.second)); while(!que.empty()) { State st = que.top(); que.pop(); if(shortest[st.y][st.x] < st.t) continue; for(int i=0;i<4;++i) { int yy = st.y + dyx[i][0], xx = st.x + dyx[i][1]; if(yy < 0 || n <= yy || xx < 0 || m <= xx || s[yy][xx] == '#' || times[st.t%k][i] == -1) continue; if(shortest[yy][xx] > shortest[st.y][st.x] + times[st.t%k][i]) { shortest[yy][xx] = shortest[st.y][st.x] + times[st.t%k][i]; que.push(State(shortest[yy][xx], yy, xx)); } } } } int main() { cin >> n >> m >> k; cin >> d; Pii start, goal; fill(shortest[0], shortest[n-1]+m, INF); for(int i=0;i<n;++i) { cin >> s[i]; for(int j=0;j<m;++j) { if(s[i][j] == 'S') { start = Pii(i,j); shortest[i][j] = 0; } else if(s[i][j] == 'G') { goal = Pii(i, j); } } } calc_times(); dijkstra(start); cout << (shortest[goal.first][goal.second] == INF ? -1 : shortest[goal.first][goal.second]) << endl; }
所感
本番ではDで詰まっていてEは見ることもしなかったけど，これは明らかにEの方が得意なタイプだったので見るべきだった．
DISCO presents ディスカバリーチャンネル コードコンテスト2019 (DDCC2019) 本戦 参加記
DDCC2019 本戦に参加してきました．DDCC は2年ぶり2回目．
〜前夜祭
DDCC3日前 (実質2日前？) にこのようなツイートをしたところ，意外に人が集まりました．
DDCC前夜 (今週の金曜夜) に何人かでご飯食べませんかって言ったら興味ある方いませんか？
— Noimin (@noisy_noimin) January 16, 2019
場所は会場付近か参加者が泊まるところの近く
時間はあまり遅くならないようにしたいです
陰性の院生なので皆さんにお誘いをかけるのはかなり緊張しましたが，勇気を出してツイートしてみてよかったです．
当日は本戦参加不参加問わず14人の競プロerが集まりました．こんなにたくさん集まるとは全く思っておらず感激しました．あと前日の夜中にこの人数の，しかも金曜夜の予約を受けてくださったお店にも感激しました．
DDCC前夜祭です pic.twitter.com/bq2hEdPq6c
— Noimin (@noisy_noimin) January 18, 2019
競プロの問題の話，精進の話，人生 (就活) の話から界隈の有名人の話まで，お話が尽きず楽しかったです．
ちなみに2次会のカラオケはなかなかのカオスで，
- 普通のカラオケ (J-POPから懐かしアニソン，全ラテン語詞，早稲田の校歌まで)
- バーチャルコンテスト
- 卒論執筆
が並行で行われていました．
締めは界隈でちょっと前に話題になった「だから慶応は学歴自慢じゃないっつーの。」や「一年かけて茶色になるエンジニア、正直全く信じられない」を合唱しました (これが個人的に1番笑った)．イキりツイートに曲をつける発想の地点でとても好きなんですが，曲としてもとても好きです．カラオケでこれらの曲を歌い出しちゃう展開も好きです．
普段幹事をやることがないのでやや不安でしたが，みなさんのおかげでとても楽しい時間を過ごすことができました．ぜひまたオンサイト前夜祭やりましょう！
当日
寝つきがめっちゃ悪かった上に変な時間に起きたので実質5時間Suiminでちょっときつかった．のでメガシャキをキメた．
コード部門
いつもの形式の部門．目標はABを解くこと．
A問題: AC
問題文の式を見て「ああ，氷マスは連続してた方がはやいね」と気づき，実装．
提出直前に，-->>->>>--の5文字目のような，1マスの雪マスをを氷マスに変えることで左右の氷マスが連続してる部分が繋がる時のことを全く考慮していなくてひやっとしたものの，「S において、- は必ず別の - と隣接して現れる」という親切仕様により命拾いしました．
この日のハイライト．
B問題: AC
目標的にB問題でも満点を取りたいと思っていたが，万が一のことを考えて部分点から考えました．
やったことは大きな数を逆順に並べる部分と小さな数を逆順に並べる部分を最初に作って，そこからswapで大吉数列になるように微調整するみたいな感じです．
大きな数を逆順に並べる部分と小さな数を逆順に並べる部分の計算量を二分探索で落としたものを満点解として提出しました．
これがまたバグらせたり謎メッセージが出たりで時間をかけすぎてしまい，ACした頃には残り3分．
C〜E問題: 未提出
ちょっと3分でACできるとは思えなかったので，後で皆さんと解法についておしゃべりするときに備えて全部の問題を読みました．
明らかにDよりCが難しそうだなあと思いました．Dは懇親会でcamypaperさんから解法をお聞きしたのでちゃんと実装しておきたい．
結果 175位
結果は175位でした．ちなみに62位〜175位がAB2完の人々だったようです．参加者全体でのレート順位が185位だったので，それよりは多少……という感じでしょうか．ただ，2年前のDDCCでは101人中85位であったことを考えると微妙な気持ちになります．ちょっと勘違いをしていて，参加者全体でのレート順位は185位ではなくて150位だったので微妙な気持ちでしかなくなりました．
装置実装部門
いつもと違う形式の部門．詳しくは問題ページを見ていただきたいのですが，一言で言うと2種類の液体から混合液を作って排出するマシンを動作させるためのプログラムを書く問題です．
予選: ☀️
30分しかないので急いで読んで急いで愚直っぽい解を生成してみたけど，色々と解の条件を見落としていてWAとTLEが取れず．
なんと正の点数を取れた人が19人しかいないらしく，終了直後には会場で失笑さえ起きていました．
こう言う時にさっと問題を把握してとりあえず動くものをさっと書けるようになりたい人生だった．
決勝: 見学
上位10人の方が実装・改良したプログラムを実演するイベントがあり，これが非常に面白かったです．
もしビデオが公開されたらそれを見てほしいのですが，特に1位のyosupoさんのプログラムによるマシンの動きは，素人の私が一目見ただけでもすごさがわかりました．
と同時に，これは私のプログラムをマシンで動かしてたらやばいことになってたかもなあと思いました．
来年はまたパワーアップした装置実装部門を考えていらっしゃるようなので，ぜひまた挑戦してみたいです．
ていうか来年参加するには一般枠で本戦に通らないといけないのか…… ．精進します．
懇親会など
1日を通して，会場に来ていたフォロワーさんの3分の2ぐらいとはお話しできた気がします．話してくださった皆さん，ありがとうございました！
特に最後の懇親会ではビールがあったので，酒乱er的にはお酒の力を借りて色々な方に話しかけることができました．できればお酒の力を借りなくても話しかけられるようになりたいですが) ． また，テーブルにあったビールをどんどん空けていく自宅番兵さんや，わりと早い段階から出来上がっていたmonkukuiさんが印象的で，酒乱erとしての格の差を感じました．
この日は月曜日から始まるインターンの前にfuurinくんに会うべく懇親会が終わってすぐ帰りました．
2年前，初めて参加したDDCC以上に楽しむことができて大満足です． オンサイトは楽しいしモチベにもなるので，たくさん精進してどんどんオンサイトに行きたいですね〜． 交流してくださった皆さん，改めましてありがとうございました！
またお会いしましょう！！
