AtCoderの気になった問題やコードの間違いなどをどこかに書きつけたいと思っていて、Google SpreadsheetやGoogle Documentを使ってみたが、どうもなんか違うなーという気がしたのでこっちに一言だけコメントを付けてまとめてみることにした。markdown形式でまとめてつかっていけるのはなかなかの強みだと思う。

2021-05-01

zone2021 C

C - MAD TEAM

max(min)の形は二分探索、というのが定石らしい。さらに各能力値をある値以上か未満かというのをbool型に落とし込んで二分探索していくというのも(もっと高度な)定石らしい。難しいので今はとりあえずパスしとく。

zone2021 D

D - Message from Aliens

何故か解けなかった、、、かなり悔しい。答えを聞いたらなんてことはなかった。'R'が来たらフラグを反転させてフラグによってdequeの前に足したり後ろに足したりする。ここまでは割と簡単にできた(string型を使ったが)。しかし、その次に(すでにtに文字列を入れていたので、)dequeからstring tに移していきながらt.back()と比較して同じなら消すという発想が思い浮かばなかった、、。

2021-05-03

abc133 B

B - Good Distance

平方数判定のときは、

    for(int i = 1; powdist / i >= i; i++){
        if(powdist % i == 0 && powdist / i == i) return true; 
    }

のようにすると効果的なようだ。sqrtからの丸めでやると誤差が無視できないのでWAとなった。(たぶんちゃんとやればACになるのかも？)

abc157 C

C - Guess The Number

ひどい間違え方をした：

    if(n == 1) ndigmin = 0, ndigmax = 9;
    if(n == 2) ndigmin = 10, ndigmax = 99;
    else ndigmin = 100, ndigmax = 999;

このコードは当然思い通りに動かない。めんどくさがらずに最後までif文を書こう。あとこういう10進数の桁を扱う問題では文字列型に変換するといいっていうの忘れてた。…と思って文字列型でやり直したら平気でこんなコードを書いてしまった。

        string num_s = to_string(num);
        rep(i, m){
            if(num_s.at(s.at(i) - 1) != c.at(i)) possible = false;
        }

当然、桁数の比較のところで、c.at(i) + '0'としなければならない。気をつけよう。

2021-05-04

B - AtCoder Market

初期化のミスをやらかした。ループを回した結果出てくる値の最小値をさらにその外のループで出す際、内側のループで足し上げるための変数の初期化を忘れてサンプルケースと答えが合わなかった。気を付けよう。

    ll entry_to_a = 0LL, b_to_exit = 0LL;
    ll min_sum_a = LONG_LONG_MAX , min_sum_b = LONG_LONG_MAX;
    rep(i, n){
        rep(j, n){
            entry_to_a += abs(a.at(j) - a.at(i)); //初期化忘れてる
            b_to_exit += abs(b.at(j) - b.at(i));
        }
        min_sum_a = min(entry_to_a, min_sum_a);
        min_sum_b = min(b_to_exit, min_sum_b);
    }

C - 100 to 105

これ

    for(int i = 1; i <= 20; i++){
        if(100 * i <= x && x <= 105 * i) possible = true;
        else if(x >= 2100) possible = true;
    }

だけでとけるよな…?こういう算数めいたこともしてACを稼いでいくのも重要だと思った。

2020-05-05

B - Buildings are Colorful!

解けたが、一度WAしてしまったし、デバッグしながらギリギリ解いた感じ。余裕が出てきたらもっと見やすいコードを一発でかけるようにしたい。

C - Many Requirements

解き方、というより題意を満たす単調増加数列が何通りあるかについて、概数を出しておく。このままだとなかなか難しいが、次のように不等号を変換して考えると◯(まる)と｜(仕切り)のみで考えられる：

$\displaystyle{ 1 \leq A_1 \lt A_2 \dots \lt A_n \leq m+n-1 }$

を満たすような数列は何通りか？

当然答えは $\displaystyle{ _ {m+n-1}C _ {n} }$ 通り。今後の概算として使っていくと良いと思われる。それと、再帰関数を考えたりするとき重要になってくるのが引数の扱い。どうしてもグローバル変数を多めに取るほうが楽になってしまう。お行儀は悪いが、そうしたほうが引数を少なくできるのでそのような問題は(競技プログラミングでは)割り切ってグローバル変数を使っていこう。毎回思うけどこういう問題、添え字が0から始まらないのがすごい歯がゆい……適当に読み替えて入力を適宜-1していくのがよさそうかな？

D - String Equivalence

これもしTLEしそうになったらそのプログラムをn = 1から10まで回して予め結果をプログラムにストアしておいてあとは出力するだけ、みたいなこともできるな……(邪道)そういうテクニックもまあ使えないことはないのかな…？

2020-05-06

現在グラフ理論に関する深さ優先探索を学習している。Boost Graph libraryを使えるようになるとめちゃくちゃ捗りそうな予感がする……が、今のうちからそれに頼りっきりなのもよくなさそうなのでまずは実装できるようにしようと思う。（というかそのうちBoost自体をを使えるようにしていきたい…）

A - 深さ優先探索

スタックを用いて実装する方法をいつか学びたい(再帰が深くなりすぎるとスタックオーバーフローを起こすらしい)。

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1160&lang=ja

またchar型にcinしてから比較するときに、