AOJ 1069 - Squid Multiplication -
問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1069&lang=jp
解法
解法1 二分探索
を二分探索で求める。それだけ。
ソースコード
int n, N; vector<int> even_b, odd_b; bool check(double x) { vector<double> a(2); Rep(i, 2) a[i] = (double)even_b[i] / x; if ( a[0]*a[1] > (double)odd_b[0] ) return false; else return true; } signed main() { while ( cin >> n, n ) { N = n * (n+1) / 2; even_b.clear(); odd_b.clear(); Rep(i, N) { int b; cin >> b; if ( b % 2 ) odd_b.pb(b); else even_b.pb(b); } sort(All(even_b)); sort(All(odd_b)); double l = 1.0, r = (1 << 31)-1; int cnt = 100; while ( cnt-- ) { double mid = (r + l) / 2.0; if ( check(mid) ) r = mid; else l = mid; } int ans = (double)r; cout << ans << endl; Rep(i, n) { if ( i ) cout << " "; cout << even_b[i] / ans; } cout << endl; } return 0; }
解法2 式をたてて計算する
数列eをbに含まれる偶数列(昇順)、数列oをbに含まれる奇数列(昇順)とすると、
参考 http://rhodon.u-aizu.ac.jp:8080/arena/submission_log.jsp?no=3810&runID=2645024
反省とか
あまり考えずに二分探索を書いたのはよくなかった。（しかもコンテスト中はばバグらせた）
数式を変形して簡単な解法がないか考えることも必要そう。
UVA 13076 - The traveller squirrel -
概要
N*Mの領域にあるn本の座標(xi, yi)が与えられる。
(x,y)からは与えられた座標のうち(x±K, y±K)の範囲に含まれる座標、または(0, 0)(N, M)に移動できる。
(0, 0)から(N, M)に移動することを考える。
与えられた順番に座標を取り除いていくとき、(0, 0)から(N, M)に移動できなくなったときの座標を求めよ。
問題文
https://uva.onlinejudge.org/external/130/p13076.pdf
解法
解法1 Union Find
座標を要素としたUnion Find。クエリを後ろから見るやつ。
全ての座標が取り除かれた状態を考えて、与えられた逆順に座標を追加していく。 その際に、その座標から半径K以内かつ、与えられた順序が後ろの座標とuniteする。(与えられた順序が前のものはすでに取り除かれていると考えるため) 座標を追加するごとに、(0, 0)と(N, M)が同じグループに属しているか判定し、属していたらそのとき追加した座標を出力する。
ソースコード
struct UnionFind{ vector<int> r, p; UnionFind() {} UnionFind(int size) { init(size); } void init(int size) { r.resize(size, 0); p.resize(size, 0); for ( int i = 0; i < size; i++ ) r[i] = 1,p[i] = i; } int find(int x) { return (x == p[x] ? x : p[x] = find(p[x])); } bool same(int x, int y) { return find(x) == find(y); } void unite(int x, int y) { x = find(x); y = find(y); if ( x == y ) return; if( r[x] < r[y] ) swap(x, y); r[x] += r[y]; p[y] = x; } }; signed main() { int N; while ( cin >> N ) { int M, K, n; Pii t[100010]; map<Pii, int> ord; cin >> M >> K >> n; Rep(i, n) { cin >> t[i].fr >> t[i].sc; ord[t[i]] = i; } t[n].fr = 0; t[n].sc = 0; t[n+1].fr = N; t[n+1].sc = M; ord[t[n]] = n; ord[t[n+1]] = n+1; UnionFind uf(n+2); int flag = -1; for ( int i = n+1; i >= 0; i-- ) { int x = t[i].fr, y = t[i].sc; for ( int nx = x-K; nx <= x+K; nx++ ) { for ( int ny = y-K; ny <= y+K; ny++ ) { if ( ord.count(Pii(nx, ny)) && ord[Pii(nx, ny)] > i && (x-nx)*(x-nx)+(y-ny)*(y-ny) <= K*K ) { uf.unite(i, ord[Pii(nx, ny)]); } } } if ( uf.same(n, n+1) ) { flag = i; break; } } if ( flag != -1 ) cout << t[flag].fr << " " << t[flag].sc << endl; else cout << "Never had the chance" << endl; } return 0; }
解法2 二分探索
求めたい座標を二分探索で決め打ちしてもできるっぽい。
参考(先輩のコード)
http://rhodon.u-aizu.ac.jp:8080/arena/submission_log.jsp?no=3744&runID=20216677
反省とか
コンテスト中は読まなかった気がする。
コンテスト後も問題文をずっと勘違いしていた(最初に与えられた座標から最後に与えられた座標に移動することを考えていた)が、 先輩のコードを読んでようやく理解できた。
ord.count(Pii(nx, ny))を書かなかったらTLEしたので、mapを使うときは注意が必要。(参照すると要素が初期化される仕様らしい)
あと、flagを0で初期化していて、WAをだしてしまったのがアホすぎた。(0も解の一つとして考えられるときは気を付けよう)
CODE FESTIVAL 2017 qual C - D:Yet Another Palindrome Partitioning -
概要
英小文字のみからなる文字列が与えられる。
をいくつかの空でない部分文字列に分割する。
そのとき、部分文字列は以下の条件を満たす。
・の文字を並べ替えて回文が得られる。
文字列の最小の分割数を求めよ。
問題文
D: Yet Another Palindrome Partitioning - CODE FESTIVAL 2017 qual C | AtCoder
解法
まず、並べ替えたら回文になる文字列とは、出現回数が奇数回であるような文字の数が1以下の文字列のことである。
それぞれの文字の登場回数の偶奇は、26bitのビット列で管理できる。
dp[i] : ビット列がiのときの最小の分割数とする。
:= {j | 0 ≤ j < i かつ j xor i は 2 のべき乗または 0 である(回文の条件) } とすると，
dp[i] = { dp[j] } + 1 である。
j xor i が2 のべき乗または 0 であるようなjは、i xor (1 << k)(0 ≤ k < 26)で全て見れる。
これを文字列の最初から最後までbit列を変化させながら行い、dp[最終的なbit列]が答えになる。(これが0になる場合もあるが、その時の答えは1)
公式解説
https://img.atcoder.jp/code-festival-2017-qualc/editorial.pdf
ソースコード
int dp[1 << 26]; signed main() { string s; int n, bit = 0; cin >> s; n = s.size(); fill_n(dp, 1 << 26, INF); dp[0] = 0; Rep(i, n) { bit ^= 1 << (s[i] - 'a'); Rep(j, 26) { dp[bit] = min(dp[bit], dp[bit ^ (1 << j)] + 1); } } cout << max(1, dp[bit]) << endl; return 0; }
反省とか
コンテスト中は、できるだけ長い回文を左から作っていくみたいに考えてしまった。
xorの特性みたいなものは知っておいた方がいいと思った。
int を long long でdefineしてるとTLEするので注意。
会津大学競技プログラミング合宿2017 参加記
9月18日～20日に行われた「会津大学競技プログラミング合宿2017」に参加しました。
Day1：立命館セット
～コンテスト前～
会場の準備や買い出しのため、会津大生は朝9時の集合だった。生活リズムが崩壊していたため2時間ほどしか寝られなかった。
11時を過ぎたあたりから参加者の方々が会場に到着し始め、13時になり大体揃ったところで自己紹介が始まった。自分はトイレに行っていてほとんど聞けなかったけど、うくさんの悪魔的自己紹介を聞けたので満足。
チーム決めは、黄コーダー以上の人がランダムに二人選ぶ形で行われた。(くじ引きのような感じ) その結果、kenkooooさん(RCOの社員の方)、kawabysさん(ヅの先輩)とチームを組むことになった。チーム名は「choco_ball」(自分が好きな食べ物を聞かれてチョコボールと言ったことから)。
～コンテスト～
自分とkawabysさんが実装をして、kenkooooさんはアルゴリズムを考えたり実装のサポートをするという形で進めていった。
まず、Aを読む。やるだけなので数分でACできた。そのあと、kawabysさんがすぐにBの実装に入り、自分はkenkooooさんにCの概要を教えてもらう。シンプルな解法が出てこず悩んでいたが、kenkooooさんに色々ヒントをもらった結果、いい感じの解法がイメージできた。Bが実装中だったので紙コーディングをしていた。kawabysさんがBをACし、Cの実装に入った。添え字ミスをして時間をかけてしまったがなんとかAC。kawabysさんがDの実装に入る。
EFGを読む。Eが一番解きやすそうだったので考察を始める。最小カットで幅が1の辺が削除されていたら-1すればいいということは分かったが、削除される幅1の辺の見つけ方が分からなかった。しばらくしてkawabysさんがDをACしたので、とりあえず蟻本をみながらDinicを写経した。その間、他の二人はFを考察していた。Dinicを書いたものの、アルゴリズムの中身は全く理解していないので困った。
そこでkenkooooさんが最大流アルゴリズムの解説をしてくれた。すごくわかりやすく丁寧に説明してくれたので、僕の頭でもなんとなく理解できた。kenkooooさんの説明を受けながら実装を進めていき、なんとかサンプルに合うコードが完成。提出したがWAで、そのあともしばらくWAの原因が分からず悩む。
終了10分前ぐらいにkenkooooさんが原因に気づき、説明してくれた。それをもとにコードを書き換え提出したが、惜しくもACしたのは終了3分後だった。自分の実装がもう少し早ければACできたと思うので、悔いが残る。
～懇親会～
会場は駅前の黄鶴楼という中華料理屋。美味しかったけど海鮮系の具材が多く使われてたので少しつらかった。先生の話によるとコースで出てくる大皿より、普通に注文して出される料理の方が安くてうまいとのことだった。
～会津セット問題文チェック～
大学に戻り、22時頃から会津セットの問題文のチェックをした。前日にすでにある程度やっていたので1時間ぐらいで終わるだろうと言っていたけど、結局終わったのは24時過ぎだった。前半は自分も意見を出していたけど、後半は眠すぎて意識が飛んでいた。
Day2：会津セット
～コンテスト～
作問はしてないけど、一応テスターをしたのでジャッジ側に。
コンテスト開始からしばらくして、B問題で入力形式にミスがあることが分かった。入力形式のミスは案外気づきにくそうなので次は自分も注意した方がよさそう。
～スポンサーセッション～
コンテストとその解説が終わり、今回の合宿のスポンサーであるRCOのスポンサーセッション(企業説明にようなもの)が始まった。国内企業はマニュアルとかでガチガチに縛られてるイメージだったけど、RCOは自由度がとても高く、社員の意志を尊重している感じで理想的な会社だなあと思った。とても入りたい気持ちになったけど、自分には就職難易度がINF過ぎる。
～懇親会～
会場は作蔵という居酒屋。成人組と未成年(お酒飲まない)組の盛り上がり方の差がやばく、お酒の力を感じられた時間だった(自分は11月生まれなので来年も飲めない…)。未成年組でも、らぴんぽん(いづみつはる)は積極的に他大の人たちに話しかけていてさすがという感じだった。
懇親会が終わり解散となったが、うくさんとc7さんがカラオケに行くと言い出しまじかと思った。自分も誘われたが、眠かったのもありさすがについていけなかった。
Day3：北大セット
～コンテスト前～
この日も初日と同じ方法でチーム決めを行った。kenkooooさん(2度目)、vvataarneさん(立命館の方、今年から競プロ始めたらしいのに強すぎる)とチームを組むことになった。チーム名はwataame(vvataarneさんから)。
vvataarneさんがUS配列のキーボードが使いづらそうにしていて、とても申し訳なかった。
～コンテスト～
今回も、kenkooooさんが他二人のサポートに回るという形で進めていった。
まず、vvataarneさんがAを、自分がBを読んだ。(先に言うと、自分はここからコンテスト終了直前までずっとBを考えていたため、vvataarneさんが他の問題をどうACしていったかよく覚えていない）
Bを考察するが、解法が中々出てこない。すると、kenkooooさんがヒントをくれた。(等差数列の末項を固定する、公差の正負はあとで2倍すればいいので考えなくていいというもの）そして、しばらく考えるがまだわからない。
すると、kenkooooさんがまたヒントをくれた。(直線の内側にある格子点の数を数える問題に帰着できるというもの) 計算をすると等差数列の和のなることに気づく。が、等差数列の和を求める公式を忘れていた(数弱過ぎる)ため、困る。1～100までの総和が5050ということは何となく覚えていたので、そこから何とか公式を導けた。
それをもとに実装をし、提出をするがWA。kenkooooさんが式の間違いを指摘してくれて提出するが、またWA。式の途中でもMODを取らないといけないことに気づき、修正して提出するがまたWA。MODがうまくとれていないんじゃないかと思い、kenkooooさんがpythonでコードを書き直し提出するがまたWA。最後のところで、n=1の例外処理のところでMODをとれていないことに気づきやっとAC。
Bで時間を使いすぎてしまい、結果は4完だった。(vvataarneさんが知らない間にACDを通していた、ガチプロ) MODのとり忘れに気づかないのもあれだけど、自分の数学力がなさすぎるのも問題だったので高校数学(特にAB)を復習したい気持ちになった。
～打ち上げ的ななにか～
コンテストが終わり解散となった。そのあと会津大生10人ぐらいで菜華楼という中華料理屋に行った。自分は、激辛マーボー豆腐を注文した。また、全員で唐揚げを、dohatsuさんと焼きセット(餃子、しそ餃子、しゅうまい)を割り勘して注文した。マーボー豆腐が控えめに言ってうますぎた。(近いうちに一人でまた行くと思う)
感想
他大の競プロerと交流するのは初めてだったので、どんな感じになるのか想像できなかったけど、とても良い経験になったと思うし楽しかったです。知らない人とチームを組むのは気まずくなるんじゃないかという不安があったけど、全くそんなことはなく勉強になることも多かったです。
チームを組んでくれた方、本当にありがとうございました。今後もこういう場には積極的に参加していこうと思うので、そのときはよろしくお願いします。
来年は作問するぞ
競技プログラミングc++テンプレート
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mp make_pair #define fr first #define sc second #define Rep(i,n) for(int i=0;i<(n);i++) #define All(v) v.begin(),v.end() #define Uniq(v) v.erase(unique(All(v)),v.end()) typedef pair<int, int> Pii; typedef pair<int, Pii> Pip; typedef pair<string, int> Psi; const int INF = (1<<30); const int dx[]={1,0,-1,0}, dy[]={0,-1,0,1};
