2010-10-27
SRM486
| 
とりあえずregisterしたものの疲れたしあーもういいや寝ちゃおう寝ちゃおうと思って不参加を決め込んだつもりが0:02過ぎて部屋覗いたらcafelierさんとかsemiexpさんが跋扈していらっしゃったので参戦することにしたRoom11
総括
300: 90.0/passed system test
450: 321.07/passed system test
1000: Opened
411.07p + 0p
- 1000点問題をちょっと考えてあと10分強では書ききれないと悟り300+450を確実に取りに行こうと考えた。
- 300で(1,4)で"/+*"を返すような間抜けな落とし穴があったので終了15秒前ぐらいにresubmitして塞ぐなどした。
Room: #9/20
DivI: #192/774
Rating: 1582→1649 自己ベスト更新キター
脳内解説
珍しく3問開いたので3問分書かねば…
コメント
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20101027
2010-08-27
SRM480
| 
x x - 0pt
ケアレスすぎて死にたい（特にMedium！）ので、通すためのdiffをまず晒す。黄色にとどまるための課題はハッキリ見えている。
経験則：再提出がちらほら見られる問題は自分も再提出しないと多分死ぬ。
- 問題よく読め
- あちこちでassertしたほうがよさげ
- if文には必ずブロックを使うオレオレコーディング規約とか
Easy(250): InternetSecurity
- 問題がなかなか頭に入ってこないけど
- 多分やるだけぽ
- 170.05 → challenged.
- 辞書逆順で書いてたけどそんな問題と違った。これは早とちり
@@ -94,8 +94,8 @@
if (sz(ss)==sn) break;
}
- vector<string> ans_(all(ans));
- sort(all(ans_)); reverse(all(ans_));
+ vector<string> ans_;
+ rep(i,N) if(found(ans,address[i])) ans_.pb(address[i]);
return ans_;
}
};
Medium(450): NetworkSecurity
- サーバ１台ずつ別々に考えてよさそう
- クライアントをトポロジカルソートして逆に見ていけばいいよね
- 211.26 → failed system test...おや？
- トポロジカルソートした結果の長さがN以上とか何それバグってる、と思ったら…orz
@@ -30,7 +30,7 @@
set<int> s;
rep(o,N){
bool hi=false;
- rep(i,N){if(clientCable[i][o]=='Y')hi=true;break;}
+ rep(i,N) if(clientCable[i][o]=='Y'){hi=true;break;}
if(!hi) s.insert(o);
}
while(!s.empty()){
提出全コード
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20100827
2010-08-23
MAPS API
| 
しりとり
| 
- 一応プログラムで
- けどlevel 3のグラフ構造は読み切れないのでlevel3のグラフは手書き
- level 1, 2 は適当にやっても勝てるけど、level 3は向こうも勝ちに来るので
- これまでの履歴と、相手が出してきた手から最善手を教えてくれるっぽいプログラムを書いた
- level 3 はなんというかステージ１、ステージ２があって、ステージ１から先に抜けた方が負け、な感じ
- ステージ1: d,e,f,g,i,j,q,s,w の中での移動
- なのでステージ１の語だけ拾いだして上のプログラムを適用
- （ステージ２に行ったら同じ文字に追い込めば勝てる！）
//...
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<string> vs;
typedef vector<long long> vll;
#define sz(a) int((a).size())
#define pb push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n) for(int var=0;var<(n);var++)
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e) ((s).find(e)!=(s).end())
#define mset(arr,val) memset(arr,val,sizeof(arr))
#define remove_(c,val) (c).erase(remove((c).begin(),(c).end(),(val)),(c).end())
#define lastc(str) (*((str).end()-1))
#define RFOR(var,from,to) for(int var=(to);var>=(from);var--)
//#include "cout.h"
typedef pair<char,char> cc;
int arc[26][26];
long long trial=0LL;
typedef pair<int,int> ii;
#define LIM 5000000LL
int sub(int now, vector<int>& route)
{
trial++; //if (trial%5000000LL == 0) printf("[%lld]\n", trial);
if (trial >= LIM) {
if (trial == LIM) printf("too deep. break.\n");
return 0;
}
int way=0, res=0;
rep(next,26){
if (arc[now][next]){
way++;
arc[now][next]--;
res = sub(next, route);
arc[now][next]++;
if (res < 0) {
route.pb(-1);
route.pb(now); return next;
}
}
}
if (way==0) {
route.clear(); route.pb(now);
return -1;
}
route.pb(now);
return res ? -1 : 0;
}
void dump(int last)
{
printf("\n%c.. ", 'a'+last);
rep(c,26) printf(" %c", 'a'+c);
printf("\n");
rep(r,26){
printf("%c ->", 'a'+r);
rep(c,26){
if (arc[r][c])
printf(" %d", arc[r][c]);
else
printf(" -");
}
printf("\n");
}
printf("\n");
}
main(int argc, char **argv)
{
rep(i,26) rep(j,26) arc[i][j]=0;
int wn=0;
if (argc != 2) {
printf("usage: %s <word-list>\n", argv[0]);
return 0;
}
FILE *fp = fopen(argv[1], "r"); if (!fp) return 0;
char buf[256], first_str[256];
while (fgets(buf,256,fp) != NULL) {
//string s; cin >> s;
int len = strlen(buf);
while (len>0 && buf[len-1]<' ') buf[--len]=0;
int b=buf[0]-'a', e=buf[len-1]-'a';
if (wn == 0) strcpy(first_str, buf);
arc[b][e]++; wn++;
}
fclose(fp);
set<int> candidates;
int last = 0, b, e;
for (int wi=wn; wi>0; wi-=2) {
if (wi < wn) {
candidates.clear();
rep(i,26) if (arc[last][i]) candidates.insert(i);
if (candidates.empty()) {
printf("YOU WIN!!\n"); break;
}
}
printf("[%d] Which word did Google consume? ", wi);
if (wi == wn) {
printf("(%s) ", first_str);
} else {
printf("%c..[", 'a'+last);
tr(candidates,it) printf("%c,", 'a'+*it);
printf("] : "); fflush(NULL);
}
fflush(NULL);
string s; cin >> s;
switch (sz(s)) {
case 0:
b=last;
rep(i,26) if (arc[last][i]) { e=i; break; }
break;
case 1:
b=last; e=s[0]-'a'; break;
case 2: default:
b=s[0]-'a', e=lastc(s)-'a'; break;
}
arc[b][e]--;
dump(last=e);
vector<int> route; trial = 0LL;
int res = sub(last, route);
if (res) {
if (sz(route)>0) route.pop_back();
reverse(all(route));
tr(route,it) printf(" -> %c", 'a' + *it);
}
candidates.clear();
rep(i,26) if (arc[last][i]) candidates.insert(i);
if (candidates.empty()) {
printf("GOOGLE WINS!!\n"); break;
}
printf("\n[%d] Your choice (input last char): %c..[", wi-1, 'a'+last);
tr(candidates,it) printf("%c,", 'a'+*it);
printf("] : "); fflush(NULL);
cin >> s;
b = last, e = s[0]-'a'; arc[b][e]--;
dump(last=e);
}
}
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20100823