なおしのこれまで、これから

学んだこと・感じたこと・やりたいこと

AtCoder始めて1カ月

f:id:vxd-naoshi-19961205-maro:20200314232722p:plain

始めに

約1カ月前からAtCoderをやっております。

そこから、今現在までの経過をここにまとめていこうと思います。

shitakami.hatenablog.com


AtCoder Problemsで練習

AtCoderを初めてから現在までの結果です。

f:id:vxd-naoshi-19961205-maro:20200314231842p:plain


始めはC、D問題をメインで解く練習をしました。しかし、手応えとしてはD問題の正答率が低い(3割程度)と感じたため、一度D問題を解くのをやめてアルゴリズムの勉強にシフトしました。

今現在、理解が乏しい知識もしくは解く経験が少ないものに関しては以下のものがあります。

これからは以上のものを解く練習をしていく予定です。

また、AtCoder ProblemsではRecommendationsという機能があり、そこでレベルにあった問題が出るので少し難しい問題も練習していこうと思います。


参加したコンテストの感想

ABC154

初出場のコンテストです。こちらについては前回のブログに感想を書いています。


ABC155

AtCoderを始めたばかりということで完全に忘れ、焼肉に行った後に1時間遅れで参加しました。

ABC三完までは出来ましたが、1時間遅れということでパフォーマンスは400でした。


ABC157

このコンテストでは、C問題を解くことが出来ませんでした。

一番の原因としてはエッジケースが通らないことでした。

「C問題までは絶対に解く!」という意気込みを完全に折られてしまいました。パフォーマンスは496でした。


ABC158

前回は痛い思いをしたので、逆に「前回よりはひどくならないだろう」の意気込みで参加しました。

ABCまですんなり解けましたが、D問題で少し手間取りました。

これまで別のプログラミングサイトで実装重視の問題を解いたことがあったので、実装はすぐに出来ました。しかし、stringの連結の処理速度が遅いことを見誤り一度TLEを出しました。そこでListで文字を保持する方向にシフトしたところ解くことが出来ました。

パフォーマンスは1242でした。


パナソニックプログラングコンテスト2020

ついさっき出場したコンテスト。なので少し丁寧に書きます。

A問題

解いたけど、覚えていない. . .

B問題

始めは、奇数の行と偶数の行がいくつあるか計算して提出しましたがWA

次に、高さが偶数のときは半分、奇数のときは先ほどの計算みたくやって提出してWA

なんでやねんということで、自分でテキトーに値を入れるとエッジケースが存在することに気が付き提出してWA

なにが悪いねん!ということで、テストケースを見てみると計算結果がintの範囲を超えることがわかりlong longで計算して提出してAC。

テストケースをちゃんと確認しようという教訓を得ました。

C問題

問題を見た感じ、「sqrt関数使えばよくね?でも、そんな簡単なわけないし. . .」と疑心暗鬼になりながらとりあえずsqrt関数で計算して提出。結果はWA

そこから、ノートで不等式から平方根を除くよう計算して一度実装してみましたが、今度はテストケースで通らず。

なんでやねんともう一度数式を確認すると、不等式の両辺に -1 を掛けていることが分かりプログラムを直してAC。

D問題

どうやって求める文字列を全探索するんだろうとずっと悩みました。

途中でいったん考えるのをやめて、再起関数で文字列の生成を行いそこから考えようとして時間切れとなりました。


このコンテストのパフォーマンスは977でした。


個人的に取り上げたい問題

このままブログを終えるのも嫌なので、いくつか勉強になった問題をまとめます。

ABC146 C Buy an Integer / ABC143 D Triangles

Buy an Integerの問題は次のようになります。

高橋くんは整数を 1 つ買いに整数屋さんに行きました。

整数屋さんには 1 以上 109 以下の整数が売られていて、整数 N を買うためには A×N+B×d(N) 円が必要です。ここで、d(N) は N の十進表記での桁数です。

高橋くんの所持金が X 円のとき、高橋くんの買うことのできる最も大きい整数を求めてください。ただし、買うことのできる整数が 1 つもない場合は 0 を出力してください。

私はこの問題を線形探索でやろうとしましたが、あえなくTLEとなりました。

分からず答えを見ると二分探索を使って値を探すアルゴリズムと分かりました。

個人的には何度か本で書いたことがあったのですが、問題を解いているときには思いつかなかったです。

しかし、類題としてABC143 D Triangleでも似たような問題だったのでこの経験を糧にとくことが出来ました。


ABC150 C Count Order

この問題は次のようになります。

大きさ N の順列 ((1, 2, ..., N) を並び替えてできる数列) P, Q があります。大きさ N の順列は N! 通り考えられます。このうち、P が辞書順で a 番目に小さく、Q が辞書順で b 番目に小さいとして、|a−b| を求めてください。


この問題は解くことが出来ましたが、私は再起関数を使ってすべての順列を作りました。

int n;
int count = 1;
map<vector<int>, int> permutationMap;
 
void MakePermutation(int index, set<int> usedNumber, vector<int> permutation) {
 
    if(index == n) {
        permutationMap.emplace(permutation, count++);
        /*
        for(int i = 0; i < n; i++)
            cout << permutation[i] << " ";
        cout << endl;
        */
 
        return;
    }
 
 
    for(int i = 1; i <= n; ++i) {
        if(usedNumber.find(i) != usedNumber.end())
            continue;
 
        usedNumber.insert(i);
        permutation[index] = i;
        MakePermutation(index + 1, usedNumber, permutation);
        usedNumber.erase(i);
    }
 
}


解いた後に結果を見るとnext_permutation関数で辞書順で次の順列を作ってくれるのを知りました。

それ以降、問題を解く際はnext_permutation関数を使うようになりました。


ABC147 C HonestOrUnkind2

この問題は次のようになります。

1 から N までの番号がついた N 人の人がいます。彼らはみな、必ず正しい証言を行う「正直者」か、真偽不明の証言を行う「不親切な人」のいずれかです。

人 i は Ai 個の証言を行っています。人 i の j 個目の証言は 2 つの整数 xij , yij で表され、yij=1 のときは「人 xij は正直者である」という証言であり、yij=0 のときは「人 xij は不親切な人である」という証言です。

この N 人の中には最大で何人の正直者が存在し得るでしょうか?

この問題を最初解いた際はどうすればいいのか分からず、ひどいプログラムを書いていました。

解答を見てみるとbit全探索で解くことが分かり、このサイトを参考に勉強しました。

drken1215.hatenablog.com

これからの目標

1カ月やった感想としてはD問題が壁だと感じました。

また、C問題と言えど侮れないところもあるのでその辺も重点的にやっていく予定です。