CODE THANKS FESTIVALに参加してきました。
CODE THANKS FESTIVALは2014/11/8に行われたCODE FESTIVALに参加できなかった人たちのために開催されたオンサイトのプログラミングコンテスト＋懇親会です。
CODE FESTIVAL2014 | RECRUIT HOLDINGS -リクルートホールディングス
最近CODE FESTIVALの様子が動画で公開されたんだけど、想像以上に面白そうでした。
サイトのほうでゲストの方々のトークライブが公開されているのはとても嬉しいですね。
本選はISUCON*1があって参加できなかったんだけど、
ISUCON終わって帰ってきたらTLでCODE FESTIVAL参加勢がTLでめっちゃ楽しそうにしててつらかったです・・・。
そんなわけでTHANKS FESTIVALに参加してきました。
THANKS FESTIVALには、最近競プロはじめたって人がたくさんいました。
私も去年の今頃競プロはじめて謎コンで初めてオンサイトに参加して、たくさんの競技プログラマーさんたちに会えてから一気に競プロが楽しくなったので、THANKS FESTIVALに来た人たちもそれがきっかけで競プロにはまってくれる人がいたら嬉しいなあと思いました。
コンテストでは、最初オープンコンテストの方にでてたり、
コンテスト開始後にID登録されてないことに気づいてコンテストのページに入れなかったりで、参加する前からもう負けてる感じでした(´・ω・`)
結果は散々で悔しい思いをしましたが、この悔しさを忘れずに問題演習に励もうと思います。
Githubに解答は公開してありますが、参加してた方でブログで解答を公開していた方が多かったので私も書いてみようかと思います。
基本全部PythonでEだけC++(っぽい何か)です。
A問題
カメには足が 4 本、ツルには足が 2 本あります。
カメが A 匹、ツルが B 羽いるとき、足は合計で何本あるでしょうか。
n, m = map(int, raw_input().split()) print n * 4 + m * 2
B問題
とりあえずソートする問題
n = int(raw_input()) a = int(raw_input()) b = int(raw_input()) c = int(raw_input()) m = [a,b,c] m.sort(reverse=True) t = 0 nn = 0 while nn < n: nn += m[t % 3] t += 1 print t
C問題
indexが1~なので、間違えないようにする
n, m = map(int, raw_input().split()) score = map(int, raw_input().split()) ans = map(int, raw_input().split()) s = 0 for a in ans: s += score[a - 1] print s
D問題
minとmaxどっちがどっちかわかんなくなったので何も考えずとりあえず条件で分岐させた
N, Q = map(int, raw_input().split()) for i in xrange(Q): a,b,s,t = map(int, raw_input().split()) if s <= a <= t and s <= b <= t: print ((t - s) - (b - a)) * 100 elif a <= s and s <= b <= t: print (t - b) * 100 elif s <= a <= t and t <= b: print (a - s) * 100 elif a <= s and t <= b: print 0 else: print (t - s) * 100
本当はこれでいい
N, Q = map(int, raw_input().split()) max(0, min(b,t) - max(a,s))
E問題
Pythonで適当にかいたらTLE．
ちょっと整理したところで間に合うか自信がなかったのでC++に書き直す。(C++かけない)
めちゃくちゃ汚い。
#includeとかは省略 int main(int argc, const char * argv[]){ int R,C,M,N; cin >> R >> C >> M >> N; int v[R][C]; for (int r = 0; r < R; ++r){ for (int c = 0; c < C; ++c){ v[r][c] = 0; } } int r1,r2,c1,c2; int rc[N][4]; for (int i = 0; i < N; ++i){ cin >> r1 >> r2 >> c1 >> c2; rc[i][0] = r1 - 1; rc[i][1] = r2 - 1; rc[i][2] = c1 - 1; rc[i][3] = c2 - 1; } for (int i = 0; i < N; ++i){ for (int r = rc[i][0]; r <= rc[i][1]; ++r){ for (int c = rc[i][2]; c <= rc[i][3]; ++c){ v[r][c]++; } } } for (int i = 0; i < N; ++i){ int tmp[R][C]; for (int r = 0; r < R; ++r){ for (int c = 0; c < C; ++c){ tmp[r][c] = v[r][c]; } } int count = 0; for (int r = rc[i][0]; r <= rc[i][1]; ++r){ for (int c = rc[i][2]; c <= rc[i][3]; ++c){ tmp[r][c]--; } } for (int r = 0; r < R; ++r){ for (int c = 0; c < C; ++c){ if (tmp[r][c] % 4 == 0){ count ++; } } } if (count == M) { cout << i + 1 << endl; } } return 0; }
帰ってきてから二次元累積和を使った解法で解き直した(in Python)
全方向転換を終わらせた後に、南をむいてる銅像と西をむいてる銅像の累積和を持っておいてうにうにする。
def partial_sum(table, r1, r2, c1, c2): s = table[r2][c2] if r1 > 0: s -= table[r1 - 1][c2] if c1 > 0: s -= table[r2][c1 - 1] if r1 > 0 and c1 > 0: s += table[r1 - 1][c1 - 1] return s R, C, M = map(int, raw_input().split()) N = int(raw_input()) array = [[0 for _ in xrange(C)] for _ in xrange(R)] rcs = [] for i in xrange(N): r1, r2, c1, c2 = map(int, raw_input().split()) rcs.append([r1 - 1, r2 - 1, c1 - 1, c2 - 1]) for r in xrange(r1 - 1, r2): for c in xrange(c1 - 1, c2): array[r][c] += 1 table_0 = [[0 for _ in xrange(C)] for _ in xrange(R)] table_1 = [[0 for _ in xrange(C)] for _ in xrange(R)] for r in xrange(R): for c in xrange(C): total_0 = 0 total_1 = 0 if c != 0: total_0 += table_0[r][c - 1] total_1 += table_1[r][c - 1] if r != 0: total_0 += table_0[r - 1][c] total_1 += table_1[r - 1][c] if c != 0 and r != 0: total_0 -= table_0[r - 1][c - 1] total_1 -= table_1[r - 1][c - 1] table_0[r][c] = total_0 + (1 if array[r][c] % 4 == 0 else 0) table_1[r][c] = total_1 + (1 if array[r][c] % 4 == 1 else 0) base = table_0[R - 1][C - 1] count = 0 for i, rc in enumerate(rcs): if base - partial_sum(table_0, rc[0], rc[1], rc[2], rc[3]) + partial_sum(table_1, rc[0], rc[1], rc[2], rc[3]) == M: print i + 1
コードが汚い。
F問題
この問題よくわからなくて、グラフで考えればよかったのに、
なんか一生懸命ソートしようとして頑張って1時間半溝にすてた。
ソートするには情報が足りないからソートは出来ない。
自分より弱い人リストみたいなのをつくって、そこに0番（高橋くん）を含んでる人が何人いるか数えた。
n, m = map(int, raw_input().split()) win = [set() for i in xrange(n)] for i in xrange(m): a, b = map(int, raw_input().split()) win[a - 1].add(b - 1) for k in xrange(n): for i in xrange(n): w_set = set() for w in win[i]: for ww in win[w]: if ww != i: w_set.add(ww) if w_set: win[i] |= w_set rank = 1 for i in xrange(1, n): if 0 in win[i]: rank += 1 print rank
G問題
F説いた時点であと15分しかなくて、急いで書いたけど間に合わなかった。
ここまでは解きたかった・・・。
典型的なダイナミックプログラミンッな問題。
最初メモ化再帰で書こうとしたけどこの問題はDPで書いたほうが楽だった。
普通に書いたらTLEして、確率が0%の時は何もしないっていうの入れたら通った。
本番中だったらこれは思いつかなかったしやっぱPythonで競プロやってるけど強くなりたい人はもう1言語使えなきゃつらいと思う。
C++早く書けるようになりたいしちゃんと演習しよう。
N, K = map(int, raw_input().split()) pp = [] for i in xrange(N): pp.append(int(raw_input())) dp = [[[0.0 for _ in xrange(K + 1)] for _ in xrange(K + 1)] for _ in xrange(N + 1)] dp[1][1][0] = 1.0 for n in xrange(1, N): for j in xrange(K + 1): for i in xrange(j / 2 + 1): if dp[n][j][i] == 0: # これないとTLE continue #seat p = pp[n] / 100.0 if i > 0: dp[n + 1][j][i - 1] += p * dp[n][j][i] elif j + 1 <= K: dp[n + 1][j + 1][i] += p * dp[n][j][i] #skip if j + 2 <= K: dp[n + 1][j + 2][i + 1] += (1 - p) * dp[n][j][i] else: dp[n + 1][j][i] += (1 - p) * dp[n][j][i] s = 0 for i in xrange(K + 1): for j in xrange(K + 1): p = (i + K - j) * dp[N][j][i] s += p print s
H問題
ロリハっ◟( ˘•ω•˘ )◞
いつか解きたい。
