あ!!!!!!!!!!!!!!!!!
け><
お^~
め!w
第16回日本情報オリンピック 2016/2017 予選に参加した話
結果
これと比較した感じだと380点でした.
提出ミスしてなければ幸いです.
(追記) 360点で予選通過してました.プロ各位宜しくお願いします.ちなみに5問目の1ケースにinputを投げてしまい,20点を失いました.
1問目
やるだけ.もうちょっとコンパクトなコードを書きたかった.無駄な部分が多い.
// テンプレ省略 signed main() { int a, b, c, d, e; cin >> a >> b >> c >> d >> e; int ans = 0; if (b == a) { print(ans); return 0; } if (a < 0) { ans += c * abs(a); a = 0; } if (a == b) { print(ans); return 0; } if (a == 0) { ans += d; } print(ans + (b - a) * e); return 0; }
2問目
これもやるだけ.b
は使わなくていい.
signed main() { int n, m; cin >> n >> m; int ans = 0; vi a(m); REP(i, m) { int b; cin >> a[i] >> b; } sort(ALL(a)); reverse(ALL(a)); REP(i, m - 1) { if (a[i] < n) { ans += (n - a[i]); } } print(ans); return 0; }
3問目
D
という長さになればいいのである地点から東西南北4方向を見て#
でなければそこからdfsをして,深さがD
になったら答えに1加える.方向を引数でもってやればいい.最終的に出た数は被りがあるので2で割ってやる.別にfor
でやっても良かった.
例年の3問目よりかなり簡単なのでは.多分ここらへんまでで30~40分.
int n, m, d; char s[128][128]; int ans; void dfs(int y, int x, int dep, int ddy, int ddx) { if (dep == d) { ans++; return; } int ny = y + ddy, nx = x + ddx; if (!inside(ny, nx, n, m)) return; if (s[ny][nx] == '#') return; dfs(ny, nx, dep + 1, ddy, ddx); } signed main() { cin >> n >> m >> d; REP(i, n) cin >> s[i]; REP(i, n) REP(j, m) { if (s[i][j] != '#') { REP(k, 4) { int ny = i + dy[k], nx = j + dx[k]; if (!inside(ny, nx, n, m)) continue; if (s[ny][nx] == '#') continue; dfs(i, j, 1, dy[k], dx[k]); } } } print(ans / 2); return 0; }
4問目
テストケース1~3まで通しました.bitDPらしいですね.わかりません.
脳を完全に停止してnext_permutation()
をし,順列を全列挙した.順列は最大でm!
種類あるのでm
が大きい値だと計算量がまずい.このコードだとO(n * m!)になりますかねえ.ひどいなこれ.
順列と元のぬいぐるみと比較して,違う種類だったらカウント.そしてmin
をとる.1時間ぐらいずっと回してた.
signed main() { int n, m; cin >> n >> m; vi a(n), b(m), cnt(n + 1); REP(i, m) b[i] = i + 1; REP(i, n) { cin >> a[i]; cnt[a[i]]++; } int res = INF; do { int c = 0; int idx = 0; REP(i, m) REP(j, cnt[b[i]]) { if (a[idx++] != b[i]) c++; } } chmin(res, c); } while (next_permutation(ALL(b))); print(res); return 0; }
問題5
解法が思いつかず,適当にdfsしたら1ケース目は通った.残りはなんかセグフォが起きたので諦めた.
int h, w; vvi a; int sum = 0; bool vis[1000][1000]; void dfs(int y, int x, bool fi = false) { bool flg = false; REP(i, 4) { int ny = y + dy[i], nx = x + dx[i]; if (!inside(ny, nx, h, w)) continue; if (a[y][x] > a[ny][nx]) { flg = true; dfs(ny, nx); } } if (!flg && !fi && !vis[y][x]) { sum++; vis[y][x] = true; } } signed main() { cin >> h >> w; a = vvi(h, vi(w)); REP(i, h) REP(j, w) cin >> a[i][j]; int res = 0; REP(i, h) REP(j, w) { memset(vis, 0, sizeof(vis)); sum = 0; dfs(i, j); if (sum > 1) res++; } print(res); return 0; }
問題6
拡張dijkstraらしいですね.
「いい感じにするdijkstraやろ!w」
と思ったけど,ぼくはスーパー適当なdijkstraを書いてsampleが通らないけど取り敢えず出しました.全ケース落ちました.コードは載せません.
まぁでも,去年はdijkstraという言葉すら知らかったので成長はしたのかなという感じです.
感想
つらいです.3問目までめっちゃ簡単で「いけるやろ~」と調子に乗ったら,難易度が跳ね上がりました.明らかに精進不足です. もし予選通ってたら,本選までにDPとか克服していきたいです.
あと3問目まで答えを格納する変数名がans
なのに4問目からres
なのウケますね.
あー ねんまつ
JOI予選お疲れ様です
疲れました.僕は多分380点です.
この記事はICT Advent Calender2016 11日目の記事です.
僕が今年出た大会まとめ
- 数学甲子園2016(予選落ち)
- SuperCon2016(本選7位)
- 愛媛大学工学部情報工学科プログラミングコンテスト(優秀賞)
- パソコン甲子園2016プログラミング部門予選(予選落ち)
- パソコン甲子園2016プログラミング部門もう一つの本選(8位)
- 第27回全国高等専門学校プログラミングコンテスト競技部門(準決勝敗退)
- JOI2016/2017予選(まだ結果出てない)
今年は,去年より大会に出たいという気持ちが大きかったからか,多くの大会に出てるような気がします.
この中では,パソコン甲子園2016プログラミング部門もう一つの本選で8位になれたことは印象に残っていて,「工藤忍北条加蓮」というチーム名がPCKのホームページに載っているのが面白かったです.因みに,FirstACも取れてウケてます.来年は本選に行きたいと思います.
覚えた・習得したこと
興味があること
- マラソンマッチ系の大会(まだ出たことないのでCodingameとかやっていきたい)
- CTF(少しだけやって結構面白かったのでやりたい)
- 画像処理(面白そう)
- モバイル系アプリ開発(Androidとかやりたい)
- Python(面白そう)
欲しいもの
- MacBook Pro
- THE IDOLM@STER CINDERELLA GIRLS STARLIGHT MASTER 01 Snow Wings
- THE IDOLM@STER CINDERELLA GIRLS STARLIGHT MASTER 07 サマカニ!!
- THE IDOLM@STER CINDERELLA MASTER Take me☆Take you
- THE IDOLM@STER CINDERELLA MASTER Cute jewelries! 003
- [セクシー モデル]工藤忍
- お金
今年なんかめっちゃオタクになったっぽい
もうちょっとでモバマスのほうもPLvが100超えそうですし,デレステも楽しいですし(絶対特権主張しますっ!がすき),佐々木千枝は心臓が痛くなるほど可愛いし,工藤忍はリンゴの皮を剥くのが上手いです.
CDも結構買ったような気もします.
あと最近は冴島清美ちゃんが僕の中でキテます.
逸れ!w話が逸れ過ぎてシルク・ド・ソレイユになった!w
そんなことはどうでもよくて
来年からどうなるんだろうという不安があります.
何でも出来る人@orisano先輩が卒業されるので,ICT委員会の技術力が著しく低下するのでは,ということがあります.
僕もorisano先輩には色々教わっていますし,他の人もそうだと思います.しかし,来年はいません.今度は僕らが後輩に教えないといけません.特に競技プログラミングは誰が引っ張っていくのでしょうか.今,一番出来る人は@37kt_先輩なので是非とも後輩教育をお願いしたいものです.僕もやりますけど.
来年の目標
この3つの目標を達成するために頑張っていきたいです.
最後に
オクタコアとオタクコアで韻が踏める
— 予選落ちkoji (@kuro__koji__) 2016年11月15日
以上です.
明日は@yagamian_sobaya先輩と@Luzhiledです.
昨日は@manae_manawayでした.