ICPC2018国内予選 参加記
とりあえずチーム紹介
おみかんより梨が好き!!この記事の作者!!mkan!!
最年長!!最年長!!hmさん!!!
チームの紅一点!!実質友利奈緒!!chocobo君!!!
あとチーム名はodanでした
ICPCはmkan_0141,chocobo,hm05とチームodanで出ます
— おみかん (@mkan_0141) 2018年7月5日
俺たちがodanです
開始よりn時間前の話
避難勧告のアラートで6時に起床.通学経路のJRが全滅してる中で近鉄電車が動いてたので気合いで大学に向かう.
とりあえずマスコットは忘れず持っていく.
マスコットぞい! pic.twitter.com/TP9ayCBRV5
— おみかん (@mkan_0141) 2018年7月5日
開始まで5時間くらい時間があったので,研究室の大きいディスプレイといい感じのスピーカーがあるので,アニメ見ながらAOJで拡張ダイクストラの問題を解いてたけどサンプルが通らず辛かった.ACはできてない.
開始の2時間前くらい
チームメンバーが到着する.
集まったのでとりあえず環境を整えるのとライブラリの印刷と,本番環境で使えない関数があったのでその対処法を考えてた.この辺りでchocobo君が友利奈緒になる.何が起こったのか分からないけど僕にも分からなかった.
練習用の問題をとりあえず解いてたけどsampleが合わずに辛くなる.cinの後にgetlineするとgetlineが改行を拾ってしまってダメだったみたい. そんなこんなでコンテストが始まる.
予選開始
Aをmkan,Bをhmさん, Cをchocobo君でD以降をみんなで解いていこうという方針でした.
0:00
問題を刷ってA問題を読む.
A問題を読むとやるだけだったのでやって見るとsampleが通る.けどオーバーフローとか怖かったのでchocobo君に制約を確認してもらってから提出する.
0:08
A問題AC!ヤッタネ!!
0:09 ~
chocobo君とhmさんがBとCを解く.chocobo君は速攻で解法を見つけて実装するも計算量が厳しいことに気づいてhmさんとPCをswapする. B問題は実装がつらそうだった.
0:59 C問題AC!!
B問題はもう少し実装に時間がかかりそうだったのでD問題をchocoboと考察.
1:52 B問題AC!!
D問題をみんなで考察するもダメでした.
結果3完83位でした
AOJ1136 Polygonal Line Search ~ 座標を90度回転させたくなったので ~
問題
方針
・比較対象を90度ずつ回転させて始点を元の図に合わせてひたすら判定を繰り返す.
・後ろから比較しないと一致しない場合があるのでそれを考慮する.
計算量的に泥臭く書いてもTLEしないと思うので実装を頑張る.
座標の90度回転
自分はcmathのsinとかcon関数を使ってよしなにする方法を真っ先に思いついたけど,よくよく考えてみると90度時計回りの回転なので
x = y y = -x
で実現できる.証明とかはググれば出てくると思う.
回答コード
bool check(vector<pi> comp, vector<pi> target){ if(comp.size()!=target.size())return false; for(int z=0;z<2;z++){ for(int i=0;i<4;i++){ bool ok=true; int x=target[0].first-comp[0].first; int y=target[0].second-comp[0].second; for(int j=0;j<(int)comp.size();j++){ if(comp[j].first+x!=target[j].first||comp[j].second+y!=target[j].second){ ok=false; } int tmp=-target[j].first; target[j].first=target[j].second; target[j].second=tmp; } if(ok)return true; } reverse(all(target)); } return false; } void solve(int n){ int m; cin>>m; vector<pi> comp(m); for(int i=0;i<m;i++){ cin>>comp[i].first>>comp[i].second; } for(int i=0;i<n;i++){ cin>>m; vector<pi> diff(m); for(int j=0;j<m;j++){ cin>>diff[j].first>>diff[j].second; } if(check(comp,diff))cout<<i+1<<endl; } } int main(){ int n; while(cin>>n){ if(n==0)break; solve(n); cout<<"+++++"<<endl; } return 0; }
終わりに
色々解説見たけど,この解法が一番シンプルでバグを埋め込みにくい気がする.
それから,実はこの問題は半年前に挑戦してWA出しまくって解けなかった問題だったりする.
以前は90度回転解法ではなくて,「どの向きにどれだけ移動しているか」みたいな方針で解いていたので,割と複雑なコードになってバグを埋め込みまくった挙句リタイアしていたなぁ...
ARC098 D - Xor Sum2
問題概要
長さNの整数列Aがある.
二点l, r ( l < r )を決めて, ~ を全て足した値と全て xor した値が等しい l と r の組みの個数を求めろ.
解法
制約が2*105なので0(n2)解は無理っぽそうなので,O(n)かO(nlog(n))ぐらいかなぁって気持ちになれるけど,コンテスト中は解法は降ってこなかった. 結論を言うと ~ の整数のうち, 各bitの立っている整数の個数が1個以下だと 和 と xor が等しくなる. と言うこと.
例えば, 2 と 10 だと, 2進数にすると 0010 と 1010 となる. これの和は 1100 , xor は1000になる. ここで等しくならない原因は,同じ場所のbitが2つ以上立っていると, 和では繰り上がらなければいけないところが xor では繰り上がらず0になってしまうので和と xor は等しくならなくなってしまうことだ.
これをどうやって数えるかと言うとしゃくとり法を使えばいいみたい . しゃくとり法は0(n)なのでACできる.
ソースコード
int main(){ long long n,ans=0; int a[2000005]; cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; } long long xsum=0,sum=0; int r=0; for(int l=0;l<n;l++){ while(r<n){ if((xsum ^ a[r])!=(sum + a[r]))break; xsum=(a[r] ^ xsum); sum+=a[r]; r++; } ans+=(r-l); xsum^=a[l]; sum-=a[l]; } cout<<ans<<endl; return 0; }
tourist解
これは解説のO(n)解なのかな?
各bitが最後に立っていたのはいつかを記録する配列を用意しておき,更新するタイミングでその時間のmaxをとってあげればi-max+1でiまでの題意をみたす個数がもとまる.
正直これ書いてて自分で何言ってるのかわからなくなったので,ソースコードを見れば一瞬でわかると思います.感動しました.
一言
解説ブログを書きまくって解説するのうまくなってやるぞい!!
ARC097 D-Equals
問題概要
1 ~ Nの順列p1,p2,p3, ... ,pnが与えられる.次にm個の1 ~ Nの整数のペア(a, b)が与えられる.このペアは与えられた順列の整数aと整数b( a,b は添字のことではない )の場所をswapさせることができる. これらの操作を好きな数だけ繰り返してPi = iとなるiの数として考えうる最大値を答えよ.
解法
連結成分内なら好きなように移動することができる.つまり,移動可能な場所のグループを作ってpi と i は同じグループに属しているかを判定すれば良い.このようなグループ分けはUnion-Find木を使えば高速に処理ができるのでそれを使う.
Union-Find木はAtCoderが説明スライドを公開しているのでそちらを参照されたし.
Union-Findの説明スライド
ソースコード
class Union_Find{ private: vector<int> par, rank; int find(int x){ if(par[x] == x){ return x; }else{ return par[x] = find(par[x]); } } public: Union_Find(int Max_Node){ par.resize(Max_Node); rank.resize(Max_Node); } void init(int n) { for(int i = 0; i < n; i++){ par[i] = i; rank[i] = 0; } } void unite(int x, int y){ x = find(x); y = find(y); if(x == y)return ; if(rank[x] < rank[y]){ par[x] = y; }else{ par[y] = x; if(rank[x] == rank[y])rank[x]++; } } bool same(int x, int y){ return (find(x) == find(y)); } }; int main(){ int n, m; cin >> n >> m; vector<int> in(n); for(int i = 0; i < n; i++)cin >> in[i]; Union_Find uf(n + 10); uf.init(n + 1); for(int i = 0; i < m; i++){ int a, b; cin >> a >> b; uf.unite(a, b); uf.unite(b, a); } ll ans = 0; for(int i = 0; i < n; i++){ if(uf.same(in[i], i+1)){ ans++; } } cout << ans << endl; return 0; }
感想
考察実装込みでだいたい10分くらいで解けたので大満足. Union-Findを使う問題をあまり見たことがないのでいい練習になった.
あと,こういう記事書くの難しいよね
RUPC2018 参加記
RUPC参加前
twitterで今年もあるよとのことだったので参戦。 atnd.org
1日目-立命館大学セット
怒髪さん、masumiさん、ksawさんの4人でdmkmというチームで参加しました。
自分はC問題を担当していましたが、解法が舞い降りてこなかったのですぐ助けてした。弱いね。
結局解法を教えてもらったが実装できそうになかったので怒髪さんに投げた。
E問題はksawさんが6通り辺をはってダイクストラやるだけ、と解法を教えてくれたので実装するもWA。
初期化の値が小さかったみたい。見事な戦犯をかます。
自分の仕事は以上で、チームとしては全完を成し遂げた。
チームメンバープロすぎる。
1日目-懇親会
twitterでよく見かける人々と喋ったりした。
去年のようにキャベツが大量に残っていたわけじゃなく平和だった。
みかんは完食されていました
— 🍊みかん🍊 (@mkan_0141) 2018年3月26日
嬉しいみかんー >< pic.twitter.com/JMkAb93PH7
2日目-会津大学セット
2日目はtuki_remonさんとkeiさんでkankitukeiというチームで参加した。
由来はレモンとみかんで柑橘、keiさんなので系、で柑橘系( 個人的にめっちゃ好きなチーム名 )
自分はB問題を解いて、あとはFとG問題の考察をした。
Fは移動パターンが数通りしかないから筋肉で殴れそう。
実装バグらせそうだったのでtuki_remonさんに実装を任せる。
Gは1つのペアで条件が成り立つなら優先的に消していき、それ以外のもので一般マッチングすればいいのでは?みたいな気持ちになった。
一般マッチングをどう実装すればいいのかわからなかったのでkeiさんに実装を任せる。
二人ともAC。はいプロ。
考察を他人に教えるということに慣れてなかったので、つたない日本語で考察を二人に言って申し訳なかった...。
この日は6完で、個人的にRUPC史上最も活躍した日だと思ってます。(ほんまか)
I問題作問者にI問題のタイトルを叫びながらりんご潰して欲しい
— 🍊みかん🍊 (@mkan_0141) 2018年3月27日
2日目-懇親会
初めて酎ハイをジョッキ2杯飲んだけど全く酔った感じがしなかった
お前らレモン残すんじゃねえぞ
— 🍊みかん🍊 (@mkan_0141) 2018年3月27日
みかんとの約束だからな!
#rupc2018 pic.twitter.com/rwfnUpRgvI
レモン完食🍋🍋🍋🍋
— 🍊みかん🍊 (@mkan_0141) 2018年3月27日
#rupc2018 pic.twitter.com/xLQaMGIfnm
どっからどう見ても酔ってますね。はい。
3日目-北海道大学セット
3日目はjimmyさんとわたあめさんとでjwmというチームで参加。
A問題は、はいという感じだったので実装AC B問題はいつのまにかACされていた。
C問題はわたあめさんから解法を聞くも実装方法がピンと思いつかず、ひどいソースコードになってしまった。その上ガバガバ実装だったので助けてもらいながらコードを修正する。これでいけるだろうということで提出するもWA。コンテスト中にはACできず。
D問題はラスト1分を切っている状態でjimmyさんが通してた。プロ。
結局この日は3完。知識不足というか実装力のなさを痛感した。
終わってから番兵さんとTreeoneさんにC問題のコーナーケースを聞いて辛い気持ちになった。
C問題ゆるせん
— 🍊みかん🍊 (@mkan_0141) 2018年3月28日
その後
RUPC参加者とにぼ二郎食べに行くぞー!!と思ったら定休日だったらしく別のラーメン屋に行った。
RUPC参加者とラ pic.twitter.com/GfQGIY5MPR
— 🍊みかん🍊 (@mkan_0141) 2018年3月28日
最後に
チームを組んで競プロするのはやっぱり楽しかったし、自分よりはるかにできる人の考察を聞いたりするのはすごくタメになる。 それに競プロのモチベーションも高まったので参加してよかったと思う。
次に参加するときには青くなっていたいなぁ
webpackで「Module not found: Error: Can't resolve 'fs'」と出てきた時の対処法
エラーいっぱいでつらい
reactを使っていた時に踏んだエラーで、npm webpack
したら大量のエラーが出てきて、その大半がModule not found: Error: Can't resolve 'fs' ( ここの'fs' が 'net' とか 'tls' と表示されていたのもあった)。
とりあえず、
yarn add fs
でnot foundなモジュールをインストールしたり、エラーが出ているモジュールを別のバージョンでインストールしたり試行錯誤してもダメだった。
ググってみたりしたけど、ググり力が低いため見つけるのに時間がかかった。
対処法
webpack.config.jsonに「target: 'node'」を追加すればいい。 たったこれだけでした。
原因
node.jsが使われている時は「target: 'node'」を記入しないといけなくて、自分はAPIを叩くライブラリを使っていたのでこのエラーが起きていたみたいですね。 自分はjavascriptしか書いてないと思っててもライブラリでnode.jsが使われていると言う落とし穴があるんですね。
詳しくはこのサイトに書いてます。
https://jlongster.com/Backend-Apps-with-Webpack--Part-I
ABC088 の話
タイポとか色々やらかして辛いコンテストでした
A - Infinite Coins
https://beta.atcoder.jp/contests/abc088/tasks/abc088_a
(N % 500 <= A)が成り立てばYesを出力すればよいよい
int main(){ int n, a; cin >> n >> a; n %= 500; if(n <= a)cout << "Yes" <<endl; else cout << "No" << endl; return 0; }
B - Card Game for Two
https://beta.atcoder.jp/contests/abc088/tasks/abc088_b
両者とも最大になるようにカードを取っていくのだから当然数字が大きいカードから取っていくのでそれをシュミレーションする。
int main(){ int n; int a[105]; cin >> n; int aa = 0, b = 0; rep(i, n)cin >> a[i]; sort(a, a + n, greater<int>()); rep(i, n){ if(i % 2 == 0)aa += a[i]; else b += a[i]; } cout << abs(aa - b) << endl; return 0; }
C - Takahashi's Information
https://beta.atcoder.jp/contests/abc088/tasks/abc088_c
a1, a2, a3の値が決まったとすると、b1, b2, b3がどんな値を取っても a1 と a2 を使ったマスの差はどの行を見ても同じで、同じく a2 と a3 を使ったマスの差もどの行を見ても同じである規則性(?)がある。
int main(){ int c[4][4]; rep(i, 3){ rep(j, 3){ cin >> c[i][j]; } } if(c[0][0] - c[0][1] == c[1][0] - c[1][1] && c[1][0] - c[1][1] == c[2][0] - c[2][1] && c[0][1] - c[0][2] == c[1][1] - c[1][2] && c[1][1] - c[1][2] == c[2][1] - c[2][2]){ cout << "Yes" << endl; }else{ cout << "No" << endl; } return 0; }
if文が長くなってすっごい見づらいな...
D - Grid Repainting
https://beta.atcoder.jp/contests/abc088/tasks/abc088_d
自分の大好きなアルゴリズムはBFSなのででてきたときは興奮した:dohentai:
や、BFSって真面目にコツコツとする感じが可愛いでしょ?可愛いですね。
BFSでスタートからゴールまでの最短距離を計算して、(' . 'の数 - 最短距離 - 1)が最大スコアになる。 最後の -1 はゴールの部分は' . 'にしておく必要があるからです。
int h, w; int d[55][55]; char s[55][55]; void BFS(){ rep(i, 55)rep(j, 55)d[i][j] = INF; d[0][0] = 0; queue<int> q; q.push(0);q.push(0); while(q.size()){ int x = q.front(); q.pop(); int y = q.front(); q.pop(); for(int i = 0;i < 4; i++){ int xx = x + dx[i]; int yy = y + dy[i]; if(0 <= xx && xx <= w && 0 <= yy && yy <= h && s[yy][xx] == '.'){ s[yy][xx] = '#'; d[yy][xx] = min(d[yy][xx], d[y][x] + 1); q.push(xx);q.push(yy); } } } } int main(){ int cnt = 0; cin >> h >> w; rep(i, h)rep(j, w){ cin >> s[i][j]; if(s[i][j] == '.')cnt++; } h--; w--; BFS(); if(d[h][w] == INF)cout << -1 << endl; else cout << max(0, cnt - d[h][w] - 1)<< endl; return 0; }