AtCoder Beginner Contest 139 A,B,C,D 反省会
今回の ABC139 でようやく緑色になれました。D までは 20 分くらいで (WA しつつも) ぽんぽん進めた一方、E はグラフっぽさを感じつつも貪欲で TLE を抜けられなかったので、現時点では、知識が備わってきたのではなく、単純な問題を早解きするスキルが上がってきただけだと思います。
次の目標である水色に到達するために、DFS, BFS や DP、グラフ等の実装を息をするようにできるように精進していきたいと思います。
1000日チャレンジ的には、チャレンジ開始から1ヶ月ちょいで茶色から緑になれたので、今後のモチベーションはかなり上がりました。
A
丁寧に3回文字列比較しました。
B
問題文普通に読み間違えて、最初 ceil(b/a)
してました。タップを1個増やすときに口が1個減るのがわかってたのにコードに反映されていないという…
C
左端から見ていって、連続して広義単調減少している区間を数えていきました。
D
いま手元にあるコードには cout << n*(n-1)/2 << endl;
と書いてあるんですが、自分の提出を見直したら FOR(i,1,n+1) ans += i-1;
でした。なんだこいつ。
E
貪欲でやったら最後まで TLE が 1 ケースだけ残ったので、方針がよくないんだろうなとは解いてて思いました。
今解説放送みててちょうど E に差し掛かったところなんですが、解き直しは明日にさせてください。おやすみなさい〜
イカはガチエリアが A --> A+, ガチホコが A- --> A にウデマエアップしました。アサリもそろそろ A 帯に上げたいですねー。
筋トレは腕立て伏せをちょっと狭い姿勢でやってみたら10*3回すらできませんでした。胸筋が皆無。
ソフトウェアエンジニアリングコミュニティの未来をどうしたいのか
昨日あるカンファレンスの前夜祭に行ってきたんですが、そこで首をひねるトークがありました。
聞いていてまず思ったのが「ここはそういうことを話す場ではないだろうな」でした。このカンファレンスは技術的な縛りは何もなく、また前夜祭でのトークは少し短めでお題もカジュアルです。
技術的縛りの一切ないカンファレンスともなれば、日本のソフトウェアエンジニアリングコミュニティに広く影響を与えるだろうと思います。そのような場で、人間の個人差を強調するような話を、さらにそのための技術的支援を作ったという話をすることが、コミュニティを良い方向へ導くでしょうか。
人間同士を結びつけるのではなく、むしろ差を際立たせることを目的とした技術が当たり前のものとして広まることは、社会をより良くはしないのではないでしょうか。
そのような技術が当たり前に受け入れられるコミュニティや社会を私たちは目指すべきでしょうか。最大公約数的な見方をすれば、あらゆる人間が存在を肯定され、人権の衝突ができるだけ不幸の少ないように解決される社会がいいのかなと思います。となれば、これらの課題に対処するコストを下げ、現実化するために技術を発展させていくのがよいのかなと思います。
その過程で、エンジニアリングコミュニティが人間の分断を固定化する技術を何の留保もなく受け入れ、広めることは、社会にとってコミュニティが「よくないもの」として見なされることを促してしまうと思います。
第一回日本最強プログラマー学生選手権-予選- A,B 反省会
実際に時間内に提出したのは A だけでした。
A は全部調べれば良いです。
B は途中までは色々工夫して調べていましたが、高々 2000 個の数列なので
- 数列内での転倒数と、
- 数列を 2 組並べたときの、後ろの数列から見た前の数列に対する転倒数 ×
k*(k-1)/2
を足せば O(N2) ですが間に合うことに気づいて軌道修正しました。
間に合うのですが、コードのどこで % MOD
すれば AC するのか試行錯誤してるうちに終わりました。なんで最後に割るだけじゃだめなん、long long
すらはみ出るのか?と思ったら LLONG_MAX
意外と小さかった。そらはみ出るわ。
最近はイカのウデマエには変化ありません。ガチマッチはちょこちょこやっています。息抜きがてら DbD と Overwatch、マリカーを再開しました。
それと数年ぶりに筋トレしたらすぐ腕がパンパンになり時の流れを感じました。今日は腕立て 13*3 回、プランク色々2分でした。なおプランクは以下の動画を参照しました。
CODE FESTIVAL 2017 Final A - AKIBA
A
を挿入すべき位置を予め調べて決め打ちして挿入し、最終的にできた文字列が AKIHABARA
と一致するか見るコードにした。
余り綺麗ではなく、実際解説を読むと AKIHABARA
から A
を抜いた文字列を全列挙してどれかと一致するか見ればよい。この実装としては特にはむこさんの提出が素晴らしく、簡潔で読みやすくバグりにくいと思う。以下に引用する。
string s; cin >> s; for (auto a : {"", "A"}) for (auto b : {"", "A"}) for (auto c : {"", "A"}) for (auto d : {"", "A"}) { if (s == a + (string)"KIH" + b + (string)"B" + c + (string)"R" + d) { cout << "YES" <<endl; return 0; } } cout << "NO"<<endl;
上記 range-for の中にある initializer list は型どうなるんだろうと思ったら std::initializer_list<string>
になるらしい。参考:
最近イカはちょびちょびやってます。ガチホコが B+ から A- になりました。あとガチヤグラもいつのまにか A- から A になってた。ガチアサリは未だに B+ です。
AtCoder Beginner Contest 106 D - AtCoder Express 2
セグメント木でやろうとして90分くらい使ったらもう眠いしわからんしで解説読んだらシンプルな累積和でよかった。就寝。
歯を磨いてたら解説の図が頭の中でどうも引っかかって、正方形ではなくてその左上半分ではないかという気がする。L_i <= R_i
の制約外せば正方形ではあるが…(制約はずさなくても正方形で描くほうが適切であることに記事の後半で気づいた)
眠くて理解しきれていないので解法を丁寧に書く。
int N,M,Q; cin>>N>>M>>Q; vector<int> L(M_MAX,0),R(M_MAX,0); int X[N_MAX][N_MAX],C[N_MAX][N_MAX]; fill(X[0],X[N_MAX-1],0); fill(C[0],C[N_MAX-1],0); FOR(i,1,M+1) { cin>>L[i]>>R[i]; ++X[L[i]][R[i]]; } FOR(i,1,N+1) FOR(j,1,N+1) C[i][j] = C[i][j-1] + X[i][j]; REP(i,Q) { int p,q; cin>>p>>q; int sum = 0; FOR(j,p,q+1) sum += C[j][q] - C[j][p-1]; cout << sum << endl; }
まず
++X[L[i]][R[i]];
で x_{l,r}
を数えていますよね。次に
C[i][j] = C[i][j-1] + X[i][j];
で x_{l,r}
の累積和を計算しておいている。最後に
FOR(j,p,q+1) sum += C[j][q] - C[j][p-1];
で区間 [p,q] に収まる x_{l,r}
、すなわち x_{p,p}
から x_{q,q}
までの和を数えるために c_{j,q} - c_{j,p-1} = x_{j,p} + ... + x_{j,q}
を j = p
から q
まで走らせている。求める和は x_{i,j}
の i,j
両方を p から q まで走らせたものなのでこういうコードになっている。
x_{p,p} + ... + x_{p,q}
でひとかたまり、次に x_{p+1,p} + ... + x_{p+1,q}
、…、 x_{q,p} + ... + x_{q,q}
というように続いていく。
こうしてみると解説冒頭の図が正方形になっているのはむしろ自然だ。問題の制約上 i > j
であるような x_{i,j}
が 0 であるだけ。
累積和はそのままなら 1 からある要素までの総和が取り出せて、適切な区間で切って引き算すればある部分列の総和が取り出せる。そんな累積和の部分的な和のさらに総和が今回の答え。なんか高校数学みたいな問題だなあ。
累積和含め、今回のように区間がからむものはセグメント木や Binary indexed tree を工夫して用いることで効率的な計算ができるらしい。N が大きかったらセグ木や BIT のほうがいいのかも。
AtCoder Beginner Contest 073 D - joisino's travel
全頂点が最大200個なのでワーシャルフロイド法を使うことができる。立ち寄る頂点の順番についても最大8個なので next_permutation
が使える。便利〜〜〜〜。
ハイライト
warshall_floyd(); int ans = LINF; do { int tmp = 0; REP(i,R-1) tmp += d[r[i]][r[i+1]]; ans = min(ans,tmp); } while (next_permutation(ALL(r)));
ワーシャルフロイド法をスニペット化した。
コスト入力時の無向・有向の区別で一瞬詰まった。
なお next_permutation
はソート済みである必要がある。