AtCoder Beginner Contest 139 A,B,C,D 反省会

提出一覧へのリンク

f:id:aximov:20190901232856p:plain
やっと緑色になれました

今回の 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分でした。なおプランクは以下の動画を参照しました。

youtu.be

AtCoder Beginner Contest 119 A - Still TBD

問題へのリンク

解説で学びがあった。 2019/04/30 というような、数字の桁数とセパレータまでフォーマットが決まっているような文字列が入力される場合には、セパレータを char で受けることで stoi などの関数を使わなくても数字部分を直接 int などで受けることができる。

int y,m,d;
char c1,c2;
cin >> y >> c1 >> m >> c2 >> d;
cout << (m <= 4 ? "Heisei" : "TBD") << endl;

あと3項演算子のこういう使い方初めて知りました。


イカは最近ガチヤグラが A+ になりました。

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> になるらしい。参考:

cpprefjp.github.io


最近イカはちょびちょびやってます。ガチホコが 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 はソート済みである必要がある。