ICPC 2013 会津大会 チーム紹介スライド 0perasan
以下の通りです．ご確認下さい．
情報オリンピック夏季セミナー 2013 小学生並の参加記
後になるほど失速します
8月26日(月曜日)
やる気に満ち溢れている．
8月27日(火曜日)
まだちゃんとやる気がある．
8月28日(水曜日)
突然やる気がなくなって，文章とりあえず半分まで書けばいいみたいな感じになる．
8月29日(木曜日)
やる気のかけらもない．
8月30日(金曜日)
もうどうにでもなれ．
Google Code Jam 2013 Qual
長く苦しい戦いだった……．ソースを載せます．
A (LOLCODE)
一番苦労した．言語の公式サイトにつながらないし，WebArchiveからSpecificationを探してきて頑張って書いた．特に超不便な連想配列しか用意されていない点や，文字列の i 番目にアクセスすることができない点は辛かった．後者は特にどうしようもなかったので Python で input を改行区切りに変換するスクリプトを書くことで対処した．
HAI 1.3
I HAS A CSN ITZ A NUMBR
GIMMEH CSN
I HAS A CURCS ITZ 0
IM IN YR LOOP UPPIN YR CURCS WILE DIFFRINT CURCS AN BIGGR OF CURCS AN CSN
I HAS A BRD ITZ A BUKKIT
I HAS A ROW ITZ 0
I HAS A COL ITZ 0
IM IN YR RDLPR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN 4
COL R 0
I HAS A LNE ITZ A BUKKIT
IM IN YR RDLPC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN 4
LNE HAS A SRS COL
GIMMEH LNE'Z SRS COL
IM OUTTA YR RDLPC
BRD HAS A SRS ROW ITZ LNE
IM OUTTA YR RDLPR
VISIBLE "Case #" AN SUM OF 1 AN CURCS AN ": "!
I HAS A DTRMND ITZ FAIL
ROW R 0
IM IN YR RLPR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN 4
I HAS A XC ITZ 0
I HAS A OC ITZ 0
I HAS A TC ITZ 0
COL R 0
IM IN YR RLPC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN 4
I HAS A TML ITZ BRD'Z SRS ROW, TML'Z SRS COL, WTF?
OMG "X", XC R SUM OF 1 AN XC, GTFO
OMG "O", OC R SUM OF 1 AN OC, GTFO
OMG "T", TC R SUM OF 1 AN TC, GTFO
OIC
IM OUTTA YR RLPC
NOT DTRMND, O RLY?
YA RLY, BOTH OF BOTH SAEM XC AN BIGGR OF XC AN 3 AN BOTH SAEM SUM OF XC AN TC AN 4, O RLY?
YA RLY, VISIBLE "X won", DTRMND R WIN
MEBBE BOTH OF BOTH SAEM OC AN BIGGR OF OC AN 3 AN BOTH SAEM SUM OF OC AN TC AN 4
VISIBLE "O won", DTRMND R WIN
OIC
OIC
IM OUTTA YR RLPR
COL R 0
IM IN YR CLPC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN 4
I HAS A XC ITZ 0
I HAS A OC ITZ 0
I HAS A TC ITZ 0
ROW R 0
IM IN YR CLPR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN 4
I HAS A TML ITZ BRD'Z SRS ROW, TML'Z SRS COL, WTF?
OMG "X", XC R SUM OF 1 AN XC, GTFO
OMG "O", OC R SUM OF 1 AN OC, GTFO
OMG "T", TC R SUM OF 1 AN TC, GTFO
OIC
IM OUTTA YR CLPR
NOT DTRMND, O RLY?
YA RLY, BOTH OF BOTH SAEM XC AN BIGGR OF XC AN 3 AN BOTH SAEM SUM OF XC AN TC AN 4, O RLY?
YA RLY, VISIBLE "X won", DTRMND R WIN
MEBBE BOTH OF BOTH SAEM OC AN BIGGR OF OC AN 3 AN BOTH SAEM SUM OF OC AN TC AN 4
VISIBLE "O won", DTRMND R WIN
OIC
OIC
IM OUTTA YR CLPC
I HAS A XCDA ITZ 0
I HAS A OCDA ITZ 0
I HAS A TCDA ITZ 0
ROW R 0
IM IN YR DIAGA UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN 4
I HAS A TML ITZ BRD'Z SRS ROW, TML'Z SRS ROW, WTF?
OMG "X", XCDA R SUM OF 1 AN XCDA, GTFO
OMG "O", OCDA R SUM OF 1 AN OCDA, GTFO
OMG "T", TCDA R SUM OF 1 AN TCDA, GTFO
OIC
IM OUTTA YR DIAGA
NOT DTRMND, O RLY?
YA RLY, BOTH OF BOTH SAEM XCDA AN BIGGR OF XCDA AN 3 AN BOTH SAEM SUM OF XCDA AN TCDA AN 4, O RLY?
YA RLY, VISIBLE "X won", DTRMND R WIN
MEBBE BOTH OF BOTH SAEM OCDA AN BIGGR OF OCDA AN 3 AN BOTH SAEM SUM OF OCDA AN TCDA AN 4
VISIBLE "O won", DTRMND R WIN
OIC
OIC
I HAS A XCDB ITZ 0
I HAS A OCDB ITZ 0
I HAS A TCDB ITZ 0
COL R 0
IM IN YR DIAGB UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN 4
I HAS A TML ITZ BRD'Z SRS COL, TML'Z SRS DIFF OF 3 AN COL, WTF?
OMG "X", XCDB R SUM OF 1 AN XCDB, GTFO
OMG "O", OCDB R SUM OF 1 AN OCDB, GTFO
OMG "T", TCDB R SUM OF 1 AN TCDB, GTFO
OIC
IM OUTTA YR DIAGB
NOT DTRMND, O RLY?
YA RLY, BOTH OF BOTH SAEM XCDB AN BIGGR OF XCDB AN 3 AN BOTH SAEM SUM OF XCDB AN TCDB AN 4, O RLY?
YA RLY, VISIBLE "X won", DTRMND R WIN
MEBBE BOTH OF BOTH SAEM OCDB AN BIGGR OF OCDB AN 3 AN BOTH SAEM SUM OF OCDB AN TCDB AN 4
VISIBLE "O won", DTRMND R WIN
OIC
OIC
I HAS A DC ITZ 0
ROW R 0
IM IN YR DCNTLR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN 4
COL R 0
IM IN YR DCNTLC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN 4
I HAS A TML ITZ BRD'Z SRS ROW, BOTH SAEM TML'Z SRS COL AN ".", O RLY?
YA RLY, DC R SUM OF 1 AN DC
OIC
IM OUTTA YR DCNTLC
IM OUTTA YR DCNTLR
BOTH OF NOT DTRMND AN BOTH SAEM DC AN 0, O RLY?
YA RLY, VISIBLE "Draw", DTRMND R WIN
OIC
NOT DTRMND, O RLY?
YA RLY, VISIBLE "Game has not completed"
OIC
IM OUTTA YR LOOP
KTHXBYE
B (LOLCOCDE)
内容的にも慣れ的にも明らかに A より楽だった．
HAI 1.3
I HAS A CSN ITZ A NUMBR
GIMMEH CSN
I HAS A CURCS ITZ 0
IM IN YR LOOP UPPIN YR CURCS WILE DIFFRINT CURCS AN BIGGR OF CURCS AN CSN
I HAS A RWS
I HAS A CLS
GIMMEH RWS
GIMMEH CLS
RWS IS NOW A NUMBR
CLS IS NOW A NUMBR
I HAS A FLD ITZ A BUKKIT
I HAS A ROW ITZ A NUMBR
I HAS A COL ITZ A NUMBR
ROW R 0
IM IN YR RDLPR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN RWS
COL R 0
I HAS A LNE ITZ A BUKKIT
IM IN YR RDLPC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN CLS
LNE HAS A SRS COL
GIMMEH LNE'Z SRS COL
LNE'Z SRS COL IS NOW A NUMBR
IM OUTTA YR RDLPC
FLD HAS A SRS ROW ITZ LNE
IM OUTTA YR RDLPR
I HAS A HGHT ITZ 1
IM IN YR CTLP UPPIN YR HGHT WILE BOTH SAEM HGHT AN SMALLR OF HGHT AN 100
ROW R 0
IM IN YR CTLPR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN RWS
COL R 0
IM IN YR CTLPC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN CLS
I HAS A TML ITZ FLD'Z SRS ROW, BOTH SAEM TML'Z SRS COL AN HGHT, O RLY?
YA RLY
I HAS A RC ITZ 0
I HAS A CC ITZ 0
I HAS A TR ITZ 0
I HAS A TC ITZ 0
IM IN YR CNTLPR UPPIN YR TR WILE DIFFRINT TR AN BIGGR OF TR AN RWS
I HAS A TTML ITZ FLD'Z SRS TR
EITHER OF BOTH SAEM TTML'Z SRS COL AN HGHT AN BOTH SAEM TTML'Z SRS COL AN 0, O RLY?
YA RLY, RC R SUM OF 1 AN RC
OIC
IM OUTTA YR CNTLPR
IM IN YR CNTLPC UPPIN YR TC WILE DIFFRINT TC AN BIGGR OF TC AN CLS
I HAS A TTML ITZ FLD'Z SRS ROW
EITHER OF BOTH SAEM TTML'Z SRS TC AN HGHT AN BOTH SAEM TTML'Z SRS TC AN 0, O RLY?
YA RLY, CC R SUM OF 1 AN CC
OIC
IM OUTTA YR CNTLPC
BOTH SAEM RC AN RWS, O RLY?
YA RLY
TR R 0
IM IN YR FLDLPR UPPIN YR TR WILE DIFFRINT TR AN BIGGR OF TR AN RWS
I HAS A TTML ITZ FLD'Z SRS TR, TTML'Z SRS COL R 0
IM OUTTA YR FLDLPR
OIC
BOTH SAEM CC AN CLS, O RLY?
YA RLY
TC R 0
IM IN YR FLDLPC UPPIN YR TC WILE DIFFRINT TC AN BIGGR OF TR AN CLS
I HAS A TTML ITZ FLD'Z SRS ROW, TTML'Z SRS TC R 0
IM OUTTA YR FLDLPC
OIC
OIC
IM OUTTA YR CTLPC
IM OUTTA YR CTLPR
IM OUTTA YR CTLP
I HAS A K ITZ WIN
ROW R 0
IM IN YR CHKLPR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN RWS
COL R 0
IM IN YR CHKLPC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN CLS
I HAS A TML ITZ FLD'Z SRS ROW
K R BOTH OF K AN BOTH SAEM TML'Z SRS COL AN 0
IM OUTTA YR CHKLPC
IM OUTTA YR CHKLPR
VISIBLE "Case #" AN SUM OF 1 AN CURCS AN ": "!
K, O RLY?
YA RLY, VISIBLE "YES"
NO WAI, VISIBLE "NO"
OIC
IM OUTTA YR LOOP
KTHXBYE
C (J言語)
J言語は書きやすい言語です．これだけははっきりと真実を伝えたかった．
load'printf'
OUT =: 'C:\GCJ\qual2013\c.out'
S =. 1!:1 <'C:\GCJ\qual2013\c.in'
states =. 3 : 0
0 10 #: <. 10 * > -.&a: <@".;._2] 0 :0
)
splitWord =. 0;(states'');a.e.CRLF,LF
1.1 0
1 0.3
)
input =: splitWord ;: S
T =: ".>{.input
input =: }.input
largeSqrt =: 3 : 0
'lo hi' =. 0; y + 1
while. 1<hi-lo do.
mid =. <.-:hi+lo
if. y>:*:mid do. lo=.mid else. hi=.mid end.
end.
lo
)
comb=: 4 : 0
if. x e. 0 1 do. z=.<((x!y),x)$ i.y
else. t=. |.(<.@-:)^:(i.<. 2^.x)x
z=.({.t) ([:(,.&.><@;\.)/ >:@-~[\i.@]) ({.t)+y-x
for_j. 2[\t do.
z=.([ ;@:(<"1@[ (,"1 ({.j)+])&.> ])&.> <@;\.({&.><)~ (1+({.j)-~{:"1)&.>) z
if. 2|{:j do. z=.(i.1+y-x)(,.>:)&.> <@;\.z end.
end.
end.
;z
)
palindrome =: (=|.)@":
solveL =: 3 : 0
if. y=1 do. 4 return. end.
ks =. 1,(i.4)!<:<.-:y
+/ks*>(2|y){1 1 1 1 1;2 3 3 2 2
:
if. y=1 do. 4<.>:x return. end.
res =. 0
if. (t<:x)*.palindrome t=.2+2*10x^<:y do. res =. res+1 end.
if. (1=2|y)*.(t<:x)*.palindrome t=.t+10x^<.-:y do. res =. res+1 end.
for_p. i.4<.>:d=.<:<.-:y do.
res =. res + +/x>:s=.(>:10x^<:y)+((10x^>:d+2|y)*(+/"1)10x^cs-~<:d)+10x*(+/"1)10x^cs=.p comb d
res =. res + (2|y)*+/x>:s+10x^<.-:y
res =. res + (2|y)*(2>p)*+/x>:s+2*10x^<.-:y
end.
res
)
solve2 =: 3 : 0
N =. largeSqrt y
res =. 0
for_d. >:i.#":N do.
if. d=#":N do. res =. res + N solveL d
else. res =. res + solveL d end.
end.
res
)
solve1 =: 3 : 0
'A B' =: y
-/solve2"0 B,<:A
)
replace=: 4 : 0
'p q'=. y
j=. p nosindx x
if. ''-:j do. x return. end.
d=. p-&#q
k=. (j+(0>.-d)*i.#j)+/i.#q
select. *d
case. 1 do. (0 (j+/(#q)+i.d)}1$~#x) # q k}x
case. 0 do. q k}x
case. _1 do. q k} (0 (d{."1 k)}1$~(#x)+(#j)*|d) #^:_1 x
end.
)
nosindx=: 4 : 0
s=. x I.@E. y
i=. s I. s+#x
(i.&_1 {. ]) (s,_1) {~ (i,_1) {~^:a: 0
)
solve =: 3 : 0
'' 1!:2 <OUT
for_n. >:i.T do.
ps =. 'x',~(>(<:n){input) replace ' ';'x '
('%d\n' sprintf n) 1!:2 <2
('Case #%d: %d\n' sprintf (n,solve1".ps)) 1!:3 <OUT
end.
)
solve''
20歳になりました
2013年です．0〜20まで数えて感慨深い思いに浸りましょう．
/: 2013
# 2013
{. 2 013
{: 201 3
# 2 0 1 3
p: {. 2 013
+/ 2 01 3
p: {: 201 3
2 ^ {: 01 3
2 ^~ {: 01 3
+/ }. p: 2 01 3
2 0 1 p. 3
+: +/ 2 01 3
}. 2 013
2 * {: p: 01 3
+/ p: 2 01 3
2 ^ +/ 01 3
p: +/ 2 01 3
<. o. +/ 2 01 3
p: p: {: 201 3
{. 20 13
【「『JOI 2011年春合宿 Day1 の問題『Dragon』は強実装』はウソ」はウソ】はウソ
http://tozangezan.hatenablog.com/entry/2013/03/29/004026
upper_bound や lower_bound を使いまくったり， -1, -2 を乱発したりしない Dragon の実装が求められているそうなので書きました．
#include <iostream> #include <vector> #include <set> #include <algorithm> using namespace std; typedef long long Int; int H, W, N; struct dragon { int x, y; } D[100050]; bool cmpx(const dragon& a, const dragon& b) { return a.x != b.x ? a.x < b.x : a.y < b.y; } bool cmpy(const dragon& a, const dragon& b) { return a.y != b.y ? a.y < b.y : a.x < b.x; } struct event { int x, y; bool query; event(int x, int y, bool q) : x(x), y(y), query(q) { } }; bool operator < (const event& e, const event& f) { return e.y < f.y; } int solve() { int res = 0; vector<int> xr, yd; for (int i = 0; i < N; ++i) { xr.push_back(D[i].x); yd.push_back(D[i].y); } sort(xr.begin(), xr.end()); sort(yd.begin(), yd.end()); xr.erase(unique(xr.begin(), xr.end()), xr.end()); yd.erase(unique(yd.begin(), yd.end()), yd.end()); vector<event> es; sort(D, D + N, cmpx); for (int i = 0, j; i < N; i = j) { for (j = i; j < N && D[i].x == D[j].x; ++j) ; es.push_back(event(D[j - 1].x, D[j - 1].y, false)); } sort(D, D + N, cmpy); for (int i = 0, j; i < N; i = j) { for (j = i; j < N && D[i].y == D[j].y; ++j) ; es.push_back(event(D[j - 1].x, D[j - 1].y, true)); } sort(es.begin(), es.end()); set<int> xs; for (int i = 0; i < (int)es.size(); ++i) { if (es[i].query) { int rr, dd; dd = yd.end() - upper_bound(yd.begin(), yd.end(), es[i].y); set<int>::iterator it = xs.upper_bound(es[i].x); if (it != xs.end()) { rr = xr.end() - upper_bound(xr.begin(), xr.end(), *it); res = max(res, (H - es[i].y - 1) + (W - *it - 1) - rr - dd); } rr = xr.end() - upper_bound(xr.begin(), xr.end(), es[i].x + 1); res = max(res, W - (es[i].x + 1) - 1 - rr); } else { xs.insert(es[i].x); } } return res; } int main() { cin >> H >> W >> N; for (int i = 0; i < N; ++i) { cin >> D[i].y >> D[i].x; --D[i].x; --D[i].y; } set<int> xs, ys; for (int i = 0; i < N; ++i) { xs.insert(D[i].x); ys.insert(D[i].y); } Int sol = (Int)H * W - (Int)H * xs.size() - (Int)W * ys.size() + (Int)xs.size() * ys.size(); int M = 0; for (int rot = 0; rot < 4; ++rot) { for (int flip = 0; flip < 2; ++flip) { M = max(M, solve()); for (int i = 0; i < N; ++i) { D[i].y = H - D[i].y - 1; } } swap(H, W); for (int i = 0; i < N; ++i) { int x = D[i].x, y = D[i].y; D[i].x = y; D[i].y = H - x - 1; } } cout << sol + M << endl; return 0; }
例によって main は回転などをしているだけ，solve も大半は座標圧縮などの造作も無い処理です．問題の箇所がこちら．
int rr, dd; dd = yd.end() - upper_bound(yd.begin(), yd.end(), es[i].y); set<int>::iterator it = xs.upper_bound(es[i].x); if (it != xs.end()) { rr = xr.end() - upper_bound(xr.begin(), xr.end(), *it); res = max(res, (H - es[i].y - 1) + (W - *it - 1) - rr - dd); } rr = xr.end() - upper_bound(xr.begin(), xr.end(), es[i].x + 1); res = max(res, W - (es[i].x + 1) - 1 - rr);
upper_bound のみ 4 回使用，いずれも単純な呼び出しにとどまっていると思います．また +1, -1 などについては
res = max(res, (H - es[i].y - 1) + (W - *it - 1) - rr - dd);
これは逆順に走査するときなどによく見る N - i - 1 の形です．また
rr = xr.end() - upper_bound(xr.begin(), xr.end(), es[i].x + 1);
こちらはドラゴンのいる x 座標(es[i].x) の隣に M 理事長が居る場合を考えるので +1 をつけています．そして
res = max(res, W - (es[i].x + 1) - 1 - rr);
これは上ふたつの複合です．
少なくとも「人が死ぬレベル」「複雑すぎる」といった形容は必要ない程度にはシンプルにまとまったと思います．
「強実装は多実装ではありません。『手ごわい』実装なのです。」という理解は正しいと思います．「強実装」という概念には単に記述量が多いだけでなく，正しく書きづらい，複雑な記述になってしまう，デバッグ時に動作を追いづらいなどの要素が含まれているでしょう．
さて，ぼくはこの問題を解くのは 3 度目ですが，この問題はとても良い問題だと思います．そして，決して簡単な問題ではないとも思います．しかし，「強実装である」という点に関してだけはそうではないと思います．
この問題の良い点，そして同時に難しい点というのは「解法の詰め方」と「適切な実装方法の選択」であります．この問題の解法自体がそこまで難しいかといえば，少なくともJOI春合宿で出題された問題の中ではそうでもないでしょう．では実装が難しいのかといえば，それも難しいとは限らない(少なくとも今回載せた実装はそこまで難しいわけではない)のがポイントです．
「他の人のソースコードを見ても、このような1や2といった数字が多数混在しています。」とあることからも分かるように，多くの人は(そしてぼくも初めて解いたときには)複雑怪奇，とても人間のデバッグするようなものではないソースを書いてしまうようです．これはこの問題が決して簡単ではないことを示しているでしょう．
今回載せた実装を最初から書くことができれば，この問題は難しいものではありません．しかし，その実装方法を選択すること，あるいはその実装方法へ至るまで正しく解法を詰められるかということ，これはとても難しいと思います．事実，ぼくも 2 度目に解いたときに比べ，さらによい実装方法を選択することができました．
パッとでてきた解法ですぐに勝負すると大変になってしまうことこそ多いが，じっくり解法を詰め，できるだけシンプルで書きやすくてバグを埋め込みにくくて動作を追いやすい，という実装方法へ至ることでスッと解けてしまう．そんな問題がぼくはとても好きであり，その点を見事に体現しているこの Dragon という問題は解くたびに新たな発見のある，非常に楽しくて良い問題なのだと，またひとつ確信させて頂きました．
天下一プログラマーコンテスト 2012 本戦
9月15日に KLab オフィスで行われた天下一プログラマーコンテスト 2012に参加しました。
まとめ
3位でした。やったー。
詳細
A
A問題なのでやるだけに違いない。そこそこの早さでAC。
B
B問題なので簡単に違いない、と思っていたらむずかった。
点の座標が不自然に小さいので自然に直線を全列挙した。直線に沿って累積和をとっていくとヨサゲだった。
ちょっと時間使ったが特にハマることなくAC。
C
B問題が結構頭使ったのでC問題は難しいに違いない、と思っていたら簡単だった。
単なるBFSで、連続する B の個数は 100 まで考えればいいという考察はいるけれどもわりと自明だった。
多少バグらせたりはしたが特にハマらずAC。
D
C問題が簡単だったのでD問題これもう(どんな問題が出るか)わかんねえな、と思っていたらほんとに見たことない問題が出た。おもしろかった。
どうみてもマラソン勢の wata さんとか瞬殺しそうだなあという感じで、逆にマラソンガチ苦手勢のぼくとかはどうしようもなさそうな感じだった。
しかし E が満点は激ムズそうで、部分点も頑張って実装したらボーナス点あげますぐらいの感じだったのでせっかくだから面白い問題を楽しんだほうがよいと思って E は無視して D に全力を尽くすことにした。
まず最初に N <= 18 の DP を書いて送ってみたりした。ここでバグらせて WA を積んだりしていて悲しかった。
DPで得られた厳密解を観察していると、(左下隅の点, 右下隅の点, 上真ん中の点) みたいな三角形がたくさん作られていたので、そういう三角形をたくさん作ることにした。四隅の点を O(N) で探してきて、 左下と右下を決め打ったときに三角形を最大にする3個目の点を普通に O(N) で求めるのを N/3 回繰り返すとちょうど O(N^2) でよさそうだったので書いた。
さすがにサンプル(格子状に並んでいるだけ)ではそこそこの解が得られるが、あんまり点がたくさんあるときにいい解が出せる自信がなかった(外側の点を無限に消費していくので最後のほうは小さい三角形ばっかりになりそう)。しかし送ってみたら通った。
E
読んで、実装を確実にやって確実に点を拾うならこっちで、100点を狙うなら D だなあと思った。
全体
- A よい
- B もっと早く解けてもよかった
- C そこそこ
- D 運
- E さて
各問題だけ見るともう少し改善できそうだが、全体で見るとわりと良かった。WAはそこそこ出してしまったがそもそも最後に点が更新されたときの時間がペナルティなのであまり影響はなく、ドハマリして時間を無駄に消費することもあまりなかった。順番もA->B->C->Dと順調に解いていくことができ、しかもDを通したのが終了4分前ぐらいだったので全体を通して充実感があってチョー楽しかった。
戦略的には D, E が残った際に E を忘れて D に全力を傾けようという決断がよかった。どんなコンテストでも問題間を右往左往して解けるものが解けなくなってしまうとかありがちなので、うまい選択が出来たのは強かった。もちろんこれで選択する方を間違えてしまうと悲惨だが、しかしぶっちゃけ選択を間違えるのと右往左往するのとか大して変わんない気がするし、どの問題を解くべきか判断する力はとても重要だと思うので積極的に選択していくほうがよさそう。
ソース
A
はい
#include<cstdio> typedef long long Int; int main() { Int X; scanf("%lld", &X); Int F[60]; F[0] = 0; F[1] = 1; for(int i=2; i<60; ++i) F[i] = F[i-1] + F[i-2]; int res = 0; while(X > 0) { int x = 0; while(F[x] <= X) x++; X -= F[x-1]; res++; } printf("%d\n", res); return 0; }
B
ちょっと実装頭わるい感じでよくない。実際のコンテスト中でも思いついたら即書き始めてアホなことするより、実装をある程度練ってから書いたほうが全体のコストは小さくできると思うので気をつけたい。
#include<cstdio> #include<set> using namespace std; typedef long long Int; int P[100][100]; const Int MO = 1000000007; int gcd(int m, int n) { return n ? gcd(n, m%n) : m; } int main() { int N; scanf("%d", &N); for(int i=0; i<N; ++i) { int x, y; scanf("%d%d", &x, &y); P[y][x]++; } Int sub = 0; for(int dx=1; dx<=99; ++dx) { for(int dy=-99; dy<=99; ++dy) { if(dy == 0) continue; if(gcd(dx, dy<0 ? -dy : dy) == 1) { Int C[100][100] = {}, R[100][100] = {}; for(int y=dy>0 ? 99 : 0; ; ) { if(dy > 0 && y < 0) break; if(dy < 0 && y >= 100) break; for(int x=0; x<100; ++x) { C[y][x] = P[y][x]; int ny = y+dy, nx = x+dx; if(0<=nx && nx<=99 && 0<=ny && ny<=99) { C[y][x] += C[ny][nx]; R[ny][nx] = 1; } } if(dy > 0) y--; if(dy < 0) y++; } for(int y=0; y<100; ++y) { for(int x=0; x<100; ++x) { if(!R[y][x] && C[y][x] >= 3) { sub += C[y][x]*(C[y][x]-1)*(C[y][x]-2)/6LL*(N-C[y][x]) % MO; if(sub >= MO) sub -= MO; sub += C[y][x]*(C[y][x]-1)*(C[y][x]-2)*(C[y][x]-3)/24 % MO; if(sub >= MO) sub -= MO; } } } } } } for(int y=0; y<100; ++y) { Int s = 0; for(int x=0; x<100; ++x) s += P[y][x]; if(s >= 3) { sub += s*(s-1)*(s-2)/6LL*(N-s) % MO; if(sub >= MO) sub -= MO; sub += s*(s-1)*(s-2)*(s-3)/24LL % MO; if(sub >= MO) sub -= MO; } } for(int x=0; x<100; ++x) { Int s = 0; for(int y=0; y<100; ++y) s += P[y][x]; if(s >= 3) { sub += s*(s-1)*(s-2)/6LL*(N-s) % MO; if(sub >= MO) sub -= MO; sub += s*(s-1)*(s-2)*(s-3)/24LL % MO; if(sub >= MO) sub -= MO; } } Int all = (Int)N*(N-1)*(N-2)*(N-3)/24 % MO; all -= sub; if(all < 0) all += MO; printf("%lld\n", all); return 0; }
C
WA はあったものの細かい条件のミスとかがなかったのは良かった
#include<cstdio> #include<algorithm> #include<queue> using namespace std; int N, A[32], B[32], C[32]; int dp[31][101][101][101]; struct st { int id, ehp, shp, cb; st(int a, int b, int c, int d) : id(a), ehp(b), shp(c), cb(d) { if(cb > 100) cb = 100; } }; const int INF = 1001001001; inline void checkmin(int& a, int b) { if(a>b) a=b; } inline void check(queue<st>& q, st x, int f) { if(dp[x.id][x.ehp][x.shp][x.cb] > f) { dp[x.id][x.ehp][x.shp][x.cb] = f; q.push(x); } } int main() { scanf("%d", &N); for(int i=0; i<N; ++i) scanf("%d%d%d", &A[i], &B[i], &C[i]); A[N] = 0; for(int i=0; i<=N; ++i) for(int j=0; j<=100; ++j) for(int k=0; k<=100; ++k) for(int x=0; x<=100; ++x) dp[i][j][k][x] = INF; dp[0][A[0]][100][0] = 0; queue<st> q; q.push(st(0, A[0], 100, 0)); while(!q.empty()) { st s = q.front(); q.pop(); if(s.id == N) { printf("%d\n", dp[s.id][s.ehp][s.shp][s.cb]); return 0; } int damaged = s.shp - B[s.id]; if(damaged <= 0) continue; int f = dp[s.id][s.ehp][s.shp][s.cb] + 1; if(s.ehp <= 5) { check(q, st(s.id + 1, A[s.id + 1], damaged, 0), f); } else { check(q, st(s.id, min(A[s.id], s.ehp - 5 + C[s.id]), damaged, 0), f); } check(q, st(s.id, min(A[s.id], s.ehp + C[s.id]), min(100, damaged+50), 0), f); int k = s.cb + 1; if(s.ehp <= k) { check(q, st(s.id + 1, A[s.id + 1], damaged, s.cb + 1), f); } else { check(q, st(s.id, min(A[s.id], s.ehp - k + C[s.id]), damaged, s.cb + 1), f); } } puts("-1"); return 0; }
D
終了5分前ぐらいに超焦って書いてたのでひどい。
#include<cstdio> #include<algorithm> #include<cstdlib> using namespace std; typedef long long Int; int x[3030], y[3030], oid[3030]; Int dp[1<<18]; int prev[1<<18], used[3030]; int N; int search_left(int a, int b, Int& M) { Int mx = -1; int mxc = -1; if(a == b) { M = -1; return -1; } for(int i=0; i<N; ++i) { if(a==i || b==i || used[i]) continue; Int x1 = x[a]-x[i], y1 = y[a]-y[i]; Int x2 = x[b]-x[i], y2 = y[b]-y[i]; Int A = x1*y2 - x2*y1; if(A < 0) A *= -1; if(mx < A) { mx = A; mxc = i; } } M = mx; return mxc; } int main() { scanf("%d", &N); for(int i=0; i<N; ++i) scanf("%d%d", &x[i], &y[i]); if(N <= 18) { dp[0] = 0; Int area[18][18][18]; for(int i=0; i<N; ++i) { for(int j=i+1; j<N; ++j) { for(int k=j+1; k<N; ++k) { Int x1 = x[j]-x[i], x2 = x[k]-x[i]; Int y1 = y[j]-y[i], y2 = y[k]-y[i]; area[i][j][k] = x1*y2 - x2*y1; if(area[i][j][k] < 0) area[i][j][k] *= -1; } } } for(int i=1; i<(1<<N); ++i) { int pc = 0; for(int j=0; j<N; ++j) if(i & (1<<j)) pc++; if(pc % 3 == 0) { int ps[18], k = 0; dp[i] = -1; for(int j=0; j<N; ++j) if(i & (1<<j)) ps[k++] = j; for(int p=0; p<k; ++p) { for(int q=p+1; q<k; ++q) { for(int r=q+1; r<k; ++r) { int sel = (1<<ps[p])|(1<<ps[q])|(1<<ps[r]); Int A = area[ps[p]][ps[q]][ps[r]] + dp[i ^ sel]; if(dp[i] < A) { dp[i] = A; prev[i] = sel; } } } } } } for(int i=(1<<N)-1, t=0; t<N/3; t++, i^=prev[i]) { for(int j=0, k=0; j<N; ++j) if(prev[i] & (1<<j)) printf("%d%c", j, ++k == 3 ? '\n' : ' '); } } else { for(int i=0; i<N/3; ++i) { int tl, tr, bl, br; for(int j=0; j<N; ++j) { if(!used[j]) { tl = tr = bl = br = j; break; } } for(int j=0; j<N; ++j) { if(!used[j]) { if(y[tl] - x[tl] < y[j] - x[j]) tl = j; if(y[tr] + x[tr] < y[j] + x[j]) tr = j; if(-y[bl] - x[bl] < -y[j] - x[j]) bl = j; if(-y[br] + x[br] < -y[j] + x[j]) br = j; } } Int M[4] = {0}; int C[4]; C[0] = search_left(tl, tr, M[0]); C[1] = search_left(tr, br, M[1]); C[2] = search_left(br, bl, M[2]); C[3] = search_left(bl, tl, M[3]); Int mx = -1; int mxc = -1; for(int j=0; j<4; ++j) { if(mx < M[j]) { mx = M[j]; mxc = j; } } if(mx >= 0) { if(mxc == 0) printf("%d %d %d\n", tl, tr, C[0]), used[tl] = used[tr] = used[C[0]] = 1; if(mxc == 1) printf("%d %d %d\n", br, tr, C[1]), used[br] = used[tr] = used[C[1]] = 1; if(mxc == 2) printf("%d %d %d\n", br, bl, C[2]), used[br] = used[bl] = used[C[2]] = 1; if(mxc == 3) printf("%d %d %d\n", tl, bl, C[3]), used[tl] = used[bl] = used[C[3]] = 1; } else { int found = 0; for(int j=0; j<N; ++j) { if(!used[j]) { printf("%d%c", j, found==2 ? '\n' : ' '); found++; used[j] = 1; } } } } } return 0; }
