Codeforces #279 Div.2 (Virtual participation)
Codeforces過去問解きその2。全６問。#280, #281に比べてかなり難しく感じた問題セット。個人的には非常に勉強になった。用事のため途中離席してしまったが、２時間パソコンの前にいた時点ではA,B,Dが解けた。問題はこちら。
A: Team Olympiad
プログラミング、数学、スポーツのどれか１つが得意な生徒達のリストが与えられる。目的の大会に出るには１チームにプログラミング、数学、スポーツが得意な生徒がそれぞれ１人ずつだけ所属している必要がある。１人の生徒は１つのチームのみに参加できる。編成できるチーム数とそのチームに所属する生徒番号を答える問題。貪欲法でOK。
n = int(raw_input()) child = map(int,raw_input().split()) prog,math,sport = [],[],[] for i in range(n): if child[i] == 1: prog.append(i+1) elif child[i] == 2: math.append(i+1) else : sport.append(i+1) ans = [] while prog and math and sport: ans.append([prog.pop(),math.pop(),sport.pop()]) print len(ans) for line in ans: print " ".join(map(str,line))
B: Queue
食堂に大学生が行列をつくって並んでいる。ランダムな順番で、各学生の前と後ろの学生の学籍番号（１以上、重複なし）が与えられる。先頭の前と最後尾の後ろは0とする。もとの行列の並び順を復元し、学籍番号の並びを１行に出力する問題。
辞書を使えば楽にできる。まず偶数番目にいる学生の番号をたどっていきうめる。次に1番目の学生を探し出し、それをたどって奇数番目にいる学生の番号を埋めていく。配列の大きさが2の場合があるので注意。
n = int(raw_input()) id = [map(int,raw_input().split()) for _ in range(n)] nxt = {a:b for a,b in id} que = [0]*n b = nxt[0] que[1] = b for i in range(3,n,2): b = nxt[b] que[i] = b sa,sb = set(a for a,b in id),set(b for a,b in id) sp = list(sa-sb)[0] if n > 2: a,b = sp,nxt[sp] que[0],que[2] = a,b for i in range(4,n,2): b = nxt[b] que[i] = b else: que[0] = sp print " ".join(map(str,que))
C: Hacking Cypher
３つの数 key, a, bが与えられる。key を左右２つの部分に切り分けた時、左部分 l が a で、右部分 r が b で割り切れるならば、そのときの l, r を答える問題。ただし r の先頭の数字は0であってはいけない。またそういう切り分け方がないときは "NO" と答える。
keyは最大106桁なのでkeyを数としてそのまま扱いたくない。切断ポイントを進むたびに l%a, r%b を計算していると到底間に合わないので、前回の余りを利用してそのポイントでの余りを効率的に計算する。なおpythonだとぎりぎりでTLEになってしまった。
#include <iostream> #include <string> typedef long long i64; using namespace std; int main(void){ bool flag = false; i64 a,b; string key; cin >> key; i64 l = key.size(); cin >> a >> b; i64 ma = 0; i64 mb[l]; mb[l-1] = (key[l-1]-'0')%b; i64 t = 10; for (i64 i = l-2; i > -1; i--){ mb[i] = (mb[i+1]+(key[i]-'0')*t)%b; t = t*10%b; } for (i64 i = 1; i < l; i++){ ma = (10*ma+(key[i-1]-'0'))%a; if (key[i] != '0' && ma == 0 && mb[i] == 0){ cout << "YES" << endl; for (i64 j = 0; j < i; j++) cout << key[j]; cout << endl; for (i64 j = i; j < l; j++) cout << key[j]; cout << endl; flag = true; break; } } if (!flag) cout << "NO" << endl; return 0; }
D: Chocolate
２つの板チョコがある。それぞれ a1×b1、a2×b2 のブロックからなっている。２つの板チョコそれぞれに、以下の操作を繰り返して同じ面積にしたい。
- 板チョコを２つに割って（垂直、水平のどちらか）、片方は食べてしまう。
- 板チョコの1/3を割って（垂直、水平のどちらか）、それは食べてしまう。
ただし、操作ができるのはブロック単位で割れるときである。この操作で2つの板チョコを同じ面積にできるかどうか。できるなら操作数と2つの板チョコの最終的な寸法を答える問題。
方針として次のようになる。まず２つの板チョコの面積の因数3の個数を合わせる。そのつぎに因数2の個数を合わせる。操作後の２つの面積が同じなら操作数と寸法を答え、違うなら "NO" を出力する。
a1,b1 = map(int,raw_input().split()) a2,b2 = map(int,raw_input().split()) ab1,ab2,n,m = a1*b1,a2*b2,0,0 ans = 0 while ab1%3 == 0: ab1 /= 3; n += 1 while ab2%3 == 0: ab2 /= 3; m += 1 ans += abs(n-m) # 片方のループは実行されない for divide in range(n-m): if a1%3 == 0: a1 = 2*a1/3 else: b1 = 2*b1/3 for divide in range(m-n): if a2%3 == 0: a2 = 2*a2/3 else: b2 = 2*b2/3 ab1,ab2,n,m = a1*b1,a2*b2,0,0 while ab1%2 == 0: ab1 /= 2; n += 1 while ab2%2 == 0: ab2 /= 2; m += 1 ans += abs(n-m) for divide in range(n-m): if a1%2 == 0: a1 /= 2 else: b1 /= 2 for divide in range(m-n): if a2%2 == 0: a2 /= 2 else: b2 /= 2 if a1*b1 == a2*b2: print ans print a1,b1 print a2,b2 else: print -1
E: Restoring Increasing Sequence
数列が与えられるが、そのなかのいくつかは一部（または全部）の桁が "?" となっている。この "?" に数字(0~9)を代入した時に、与えられた数列を単調増加数列にすることができるかどうか、できるなら代入後の数列を答えるという問題。
うまい解答を作れず、nwinさんのコードを参考に使わせていただきました。ありがとうございます。わかりやすいコードで大変助かりました。
まず前の数字より桁数が大きいか小さいかチェック。桁数が一緒ならsolveを呼んで、今の数字と前の数字を上の桁から見ていく。solveの中身をまとめると次のようになる。
片方の桁がもう一方より大きければ終わり。
できるだけ小さい桁で前の桁を上回るように"?"に値を代入する。
"?"になにを入れても前の数字より大きくできない時も終わり。
詳しくはコードを追っていって欲しい。
def solve(s,t,i,l): # l = len(s) だから i == lまで来たらFalse if i == l: return False if s[i] == "?": # i 以降の桁でtよりも大きい数字が作れる場合 if solve(s,t,i+1,l): s[i] = t[i] return True # t[i] == 9のときは１つ前の"?"での代入に任せる #１つ前の"?"がなければFalseで終わり elif t[i] == "9": return False s[i] = nxt[t[i]] # それ以降の桁には"0"を代入 for j in xrange(i,l): if s[j] == "?": s[j] = "0" return True # s[i] が t[i] より大きければ以降の"?"に0を代入 elif s[i] > t[i]: for j in xrange(i,l): if s[j] == "?": s[j] = "0" return True # s[i]がt[i]よりも小さければどう頑張ってもｔより大きなｓを作れない elif s[i] < t[i]: return False else: return solve(s,t,i+1,l) n = int(raw_input()) a = [list(raw_input()) for _ in xrange(n)] p = ["0"] nxt = {str(x):str(x+1) for x in range(9)} for i, ai in enumerate(a): # pは1つ前の数字 if len(p) > len(ai): print "NO" break if len(p) < len(ai): if a[i][0] == "?": a[i][0] = "1" for j in xrange(len(ai)): if a[i][j] == "?": a[i][j] = "0" # 単調増加数列にできなかったら"NO"出力 elif not solve(a[i], p, 0, len(ai)): print "NO" break p = a[i] else: print "YES" print "\n".join("".join(line) for line in a)
F: Treeland Tour
problem tags: data structures dfs and similar dp trees
バンド「路上事故」は今度ツリーランドで全国ツアーを行う。ツリーランドには n 個の都市があり、都市間を結ぶ道路は n-1 本ある。すべての都市間は行き来可能なことが保障されている。各都市にはそれぞれ決まった人口が住んでいる。路上事故はある順番でいくつかの都市を回りいくつかのライブを行うが、それには次のような決まりがある。
- 同じ都市は1度以上訪れない。
- コンサートを行えるのは最後にライブを行った都市の人口よりも、その都市の人口が多いとき。
- 好きな都市からツアーをスタートできる。
この条件を満たすとき、ツアーによってコンサートに参加できる人数を最大にしたときのその総参加者数を答える問題。
都市数が n 、道路数が n-1 、すべての都市は行き来可能なことから、グラフは木構造をとることがわかる。したがってどの都市から来たかがわかれば、次に行くべき都市がわかる。次の都市に行くとき、今の都市でコンサートを行う場合と行わない場合の両方について探索を進めていく。深さ優先探索で帰ってきた結果によりdp表を更新していけば、最大値（つまり答え）がわかる。
#include <iostream> #include <algorithm> #include <cstring> #define FOR(i,a,b) for(int i=(a);i<(b);i++) #define REP(i,a) FOR(i,0,a) using namespace std; int n; //max 6000 int pop[6000], fst[6000], nxt[12000], fm[12000], int to[12000], int dp[12000]; int go(int at, int prev, int last){ int res = pop[at] > last? 1:0; for (int x=fst[at]; x!=-1; x=nxt[x]){ if (to[x]==prev) continue; int cur = go(to[x],at,last); res = max(res,cur); if (pop[at] > last){ if(dp[x] == -1) dp[x] = 1+go(to[x],at,pop[at]); res = max(res,dp[x]); } } return res; } void solve(){ memset(fst,-1,sizeof(fst)); cin >> n; REP(i,n) cin >> pop[i]; REP(i,n-1){ int a,b; cin >> a >> b; a--, b--; nxt[2*i+0]=fst[a]; fst[a]=2*i+0; fm[2*i+0]=a; to[2*i+0]=b; nxt[2*i+1]=fst[b]; fst[b]=2*i+1; fm[2*i+1]=b; to[2*i+1]=a; } memset(dp,-1,sizeof(dp)); int ans = 0; REP(i,2*(n-1)){ if (dp[i] == -1) dp[i] = 1+go(to[i],fm[i],pop[fm[i]]); ans = max(ans,dp[i]); } cout << ans << endl; } int main(void){ solve(); return 0; }
