dwacon2017
ARC065は忘年会中で参加できず、2週間ぶりのプロコン参加……だが、浴槽内で寝るという失態を犯しまさかの1時間遅れ。 unratedなので素直に出場したが、結局1完という結果に終わる。
A
a+b-n>0 ? a+b-n : 0;
一丁前に三項演算子を使ってみたが、条件式を評価式にまた記載するのは明らかにダサい。
max(a+b-n, 0);
TLに流れてきたこちらの方が圧倒的に綺麗だった。maxとminの存在は忘れがちなので今後の反省点。
B
奇数起点・偶数起点の2パターンに分けられるというのは比較的早く感じ取れたものの、それを?の塊に着目してしまったため必要以上に難しく考えてしまうことに……。
?を埋めた後でニコニコレベルの判定を行うコードを書いている最中、「そもそも?の段階で判定できるのでは」とようやく気づいた。終了直後である。
文字列をTとして、T[0]およびT[1]を起点に25,2?,?5,??のどれかに当てはまるものが連続する回数を数え、大きい方を採用すればよい。
#include <iostream> #include <algorithm> using namespace std; int main() { string s; cin >> s; int len = s.length(); int ans = 0; int tmp = 0; for(int i = 0; i < len/2; i++){ if((s[i*2] == '2' && (s[i*2+1] == '5' || s[i*2+1] == '?')) || (s[i*2] == '?' && ( s[i*2+1] == '5' || s[i*2+1] == '?'))){ tmp += 2; }else{ tmp = 0; } if(tmp > ans) ans = tmp; } tmp = 0; for(int i = 0; i < (len-1)/2; i++){ if((s[i*2+1] == '2' && (s[i*2+2] == '5' || s[i*2+2] == '?')) || (s[i*2+1] == '?' && ( s[i*2+2] == '5' || s[i*2+2] == '?'))){ tmp += 2; }else{ tmp = 0; } if(tmp > ans) ans = tmp; } cout << ans << endl; return 0; }
無駄が多すぎるなんてモノではないぐらいお粗末なコードなので、後で直す。
C
深く考えず貪欲法で実装すればいい気がするが、いまいちコードに落とし込めず……。vectorを使おうとしたものの探索や削除がいまいち使いこなせなかった。明らかにデータ構造の勉強が必要っぽい。
結果
Aのみの1完。終了後16分遅れでBがACになった。
1時間遅れなので実質2完という事にしたいが、間に合っていないものは間に合っていないので仕方ない。
反省
- やるからにはunratedでも定時から参加する
- max,minの存在を忘れない
- 与えられた文字列全体に着目してみる
- STLをある程度使いこなせるようにする
ARC064
AtCoderリニューアル後、初のARC参加となった。前回のプロコン参加が11/12のAGC007という事で、実に3週間ぶりである。
開始直前にgnupackのCygWinが動かないというトラブルが発生。（）PC新調直後でWindowsにgcc,g++も入っていなかったため、急遽ノートPCで参戦した。
エラー自体はこちらの記事に紹介されているものが近かった。コンテスト終了後にPCを再起動したら正常に動いてしまったので、詳細な原因は不明。
C
隣り合う2つの和が重要そうだったので、先に和を算出してからそれぞれxと比較して、xより大きければ右隣も合わせて減らす……という手法を採った。
これでいけると確信したもののWA。しばらく考え直したところ、和の要素数n-1のまま動かすと
3 2 3 0 3
のようなケースで落ちることが分かったので、適当に前後を増やす（元の数列の前後に"0"を追加する）とACになった。
D
各文字が登場する距離(2以上)の和("abcabcbca"であればaの距離は2+4、bの距離は2、cの距離は2)の偶奇から求められそう？と思ったものの、入力例3"abcab"の時点で通らない事に気づき諦めた。
終了後解説を読んで愕然とした。終了状態に着目すれば先頭,末端文字の比較と文字列数の偶奇を調べるだけで済んだという。もう少し紙面上で考えるべきだったと後悔した。
E
パッと見でバリア間の最短距離を求めるのが難しそうと断念。
これも解説を読んで愕然とした。（当たり前といえばそうだが）中心を結べば何の事はなかった。ダイクストラ法の実装が怪しいが、十分歯が立つはずの問題だったっぽい。
結果
Aで2WAした上での1完。レート変動は1214->1209(-5)となった。終了後は1200を割る覚悟だったため、意外にも減らない印象を受けた。次回もARCで頑張りたい。
問題の傾向にはどことなくAGCに近いテクニカルな印象を受けた。writer（問題作者）さんがAGCのwriterとして何度か見覚えのある方だったので、そういう事なのかもしれない。
反省点
- しっかり紙面で考える
- 操作の終了状態に着目する
16/08/24
paiza
勢いで登録してみた
取り敢えず下から1つずつランクを上げていくことにした。
平均レートが高い問題を選んだせいか、やるだけ(でも少ししんどい)問題にやたら当たった。
ランクAの問題で判断ミスにより手間取り結果時間5分オーバーでランクアップならず。
twitterで軽く検索した所、ランクSでもABCのC,D問題ぐらいなので十分視野範囲内っぽい。
とはいえサイトの性質上ネタバレ厳禁なので、競プロみたいに解法身に着けていくサイトではなさそう。
モチベーションがどうしても落ちた時とかで気まぐれに埋めていくのが良さそう？
AOJ
AOJ0203を解いた。動的計画法の応用というイメージ。
メモ化再帰しか使ったことが無いので、漸化式で解くやつも何時かやってみたい。
折角なのでへたれコードを貼ってみる
#include <iostream> #include <sstream> #include <cstdlib> #include <cstdio> using namespace std; #define NONE 0 #define TREE 1 #define JUMP 2 int dp[17][17]; int area_state[17][17]; int h,w; int solve(int y, int x){ if (dp[y][x] != -1) return dp[y][x]; if (x == 0 || x == w+1){ dp[y][x] = 0; return 0; } if (y == h || y == h+1){ dp[y][x] = 1; return 1; } if (area_state[y][x] == TREE){ return 0; }else if (area_state[y][x] == JUMP){ dp[y][x] = (solve(y+2, x)); return dp[y][x]; }else if (area_state[y][x] == NONE){ if(y == h-1){ dp[y][x] = 1; return 1; } int left = 0; int right = 0; if(area_state[y+1][x-1] != JUMP){ left = solve(y+1,x-1); } if(area_state[y+1][x+1] != JUMP){ right = solve(y+1,x+1); } dp[y][x] = left + solve(y+1,x) + right; return dp[y][x]; } } int main() { while (cin >> w >> h && w&&h ){ fill( dp[0], dp[17], -1); fill( area_state[0], area_state[17], 0); for(int i = 0; i < h; i++){ for(int j = 0; j < w; j++){ int zone; cin >> zone; area_state[i][j+1] = zone; } } int ans = 0; for(int i = 1; i < w+1; i++){ ans += solve(0,i); } cout << ans << endl; } return 0; }
16/08/19-23
16/08/19
AOJ0516を解いた。
累積和であっさり。
尺取法およびimos法でも解けそうだが、いまいち理解しきれてないので後で理解する。
16/08/20
覚えていない。
16/08/21
AGC003に出た。2完。
Cは「3つ入れ替える」を「1個飛ばしで入れ替える」に読み替えられる事には気づけたものの、
偶奇に分ける発想には至れなかった。分かれば一発系だったので普通に悔しい。後で解き直す。
今までJava in Eclipseで参加していたが、起動がトロかったりしてどうにも重かった。
今回からC++ in (SublimeText + CygWin(gnupack))に変更。身軽さが断然違った。
16/08/22
覚えていない。
16/08/23
AOJ0545を解いた。
幅優先探索かなと思いウンウン唸るが、問題を解けるコードに落とし込めない。
問題番号でググッて(いいのか？)出てきたワーシャルフロイド法を試してみたら一発。
グラフ問題を隣接行列でしか表したことが無いので、隣接リストでも扱いたいのだが、さっぱり理解できない。
ノード数がデカくなると即死なので、後で何とかする。
TODO
- 朝起きたら12:00とかザラなのでいい加減早く寝る
- 父がパトレイバー見ろとうるさいので見る
16/08/18
とりあえずC++の環境構築を行うことにした。
Windows10にアプデ以降、開発環境がAtCoder用のEclipseぐらいしか無かった。
とりあえずMinGWからgcc,g++を入れようとした……が、ここでまさかのハマりを起こす。
Windows10環境でPathが通らない…… インストール後再起動も掛けたんだけど pic.twitter.com/WjXmoW0dVW
— sb (@_s_bear_) 2016年8月18日
なんとPathが通らない。情報系の学部に3年居たとは思えない事態。
パス末尾に\を入れたりと足掻いてみたが、どうにも解決しなかったので諦めてgnupackを入れて終わりにした。
……が、ブログを書く段階になってやはり諦めきれず、再び試行錯誤していたらなんか動いた。
@_s_bear_ 環境変数から消す→コマンドプロンプト上でgccする（当然できない）→もう一度環境変数に入れる で何故か動きました（？？）
— sb (@_s_bear_) 2016年8月18日
Sublime Text 3にC++対応拡張を入れた……が、cppcheckが動いてくれない。後でなんとかする。 qiita.com
コード貼り付けテスト
#include <iostream> using namespace std; int main() { int n; cout << "num: "; cin >> num; for(int i = 1; i <= n; i++){ if(i % 15 == 0){ cout << "FizzBuzz"<< endl; }else if(i % 3 == 0){ cout << "Fizz" << endl; }else if(i % 5 == 0){ cout << "Buzz" << endl; }else{ cout << i << endl; } } return 0; }
# # ./test num: 15 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz
あとはPythonをこの辺りの記事を参考にしつつ入れた。あとPyCharmも入れてみた。 qiita.com
結局今日は全然コードを書いていない。明日は例の課題を進めたい。
