Blog

はじめて競技プログラミングっぽい事をやってみた結果

こんにちは、cocone connectでクライアントエンジニアをしているSと申します。

10年近く業務でプログラミングを行ってきたのですが、この間初めて競技プログラミングみたいな事をやりました。

そこで気付いたことを書いてみます。

お題

お題は以下の通りです。

あるランダムな自然数の文字列が渡されます。 各桁を足して 7 になる組みを返してください

■例

  • 12345 の文字列が与えられたら
    • ⇨[(2, 5), (3, 4)] と出力する
  • 22896 の文字列が与えられたら
    • ⇨[] と出力する

 

■与えられる文字列 N の桁数

  • 0 ≦ N ≦ 100000

 

■期待する出力

  • すべての組み合わせ(同じ組み合わせは不要)
  • 組み合わせ前後[(1, 2), (2, 1)]は問いません
  • 出力の順番[(1, 2), (3, 4)], [(3, 4), (1, 2)]は問いません

 

■ポイント

  • 出力までにかかる時間を計測します
  • 正しい組み合わせが出ることを期待します

自分の考え

競技プログラミング経験者の方であればサクッと思いつくのかもしれませんが、自分の場合は馬鹿正直に

「2重for文でi番目の数字+j番目の数字がX(この場合は7)になるかチェックすればええやん、jの初期値はi+1にすれば被りも減らせるな」

と考えていました。

そして、使用言語がC#だった(指定は特になかったのですが、普段業務で使ってた)ので、

「結果表示用の文字列の結合は+じゃなくてStringBuilderでやればヨシ!あとはi番目の数字が8以上の数値だったらcontinueして…

でも8以上って8と9しかないし枝刈りとしては微妙か…?いやnが大きければ大きいほど効果あるか」

とか考えてゴチャゴチャやってプログラムを書きました。

他の方の回答

その後、他の方の回答を見る事に。

大体似たような人が多かったのですが、

「i番目の数字をチェックする際にペアとなる数字(仮にi番目の数字が2だったら5)を別の配列に入れておき、既に入っていればペアとして出力する」

というものがあって
「それだと2重for文じゃなくて済むか…なるほど」と思ったりしました。

また、あくまで速度だけ重視して拡張性等を無視したやり方として

「出てきた数字をチェックして7までの数字が全部出てきたらそこで探索を終了、探索が終わったら(0,7)、(1,6)、(2,5)、(3,4)のペアのうち存在するものを表示する」

いうものがあってなるほど(笑)となりました。

感想

学生時代とかにアルゴリズムの授業で色々考えたりしたのを思い出して懐かしい気持ちになりました。

仕様変更の多いモバイルアプリ開発などを行っていると、拡張性や保守性の方に意識が行きがちなので、こういった視点も大事だなと改めて気付かされました。(組み込みエンジニアの方等は普段から意識されてるのかなと思いますが)

それと同時に自分の体たらくっぷりにも気付かされ…ちょっと競技プログラミングをやってみようかなと思ったりしたのでした。

 


cocone connectでは一緒に働く仲間を募集中です。

ご興味のある方は、こちらのリンクからぜひご応募ください。

 

cocone connect株式会社 採用情報

https://recruit.jobcan.jp/coconeconnect

 

cocone connect株式会社 公式サイト

https://connect.cocone.co.jp/

 

また、ココネでも一緒に働く仲間を募集中です。

ご興味のある方は、ぜひこちらの採用特設サイトをご覧ください。

https://www.cocone.co.jp/recruit/contents/

Popular posts

Category

Tag

Category

Tag

%d人のブロガーが「いいね」をつけました。