1. TOP
  2. BLOG
  3. EVENT
  4. 競技プログラミングに入門しました // 第63回社内勉強会 #sa_study

競技プログラミングに入門しました // 第63回社内勉強会 #sa_study

2020.09.18


いやー夏ももう終わりですねー。
どうも!古橋です。

今回の勉強会では、競技プログラミングの問題をチームを組んで解いてもらうという試みをしましたのでご紹介させていただければと思います。

私自身、たまに競技プログラミングの問題を解いたりしていまして、そこで感じたことなどを共有させていただければといった次第です。

目的としては大きく2つあります

  • 競技プログラミングがどんなものなのかを知ってもらう
  • 計算量を意識してプログラミングをするきっかけを作る

前者に関しては、普段やらないことだったり知らない世界に触れてもらうことの良さを知ってもらったり、これがきっかけで競技プログラミングが好きになってくれる人いたら嬉しいなという想いがあります。

後者に関しては普段の開発に活かせるものだと思っていて、「なんかこの処理は遅そうなのでもう少し考えよう」といった感覚的なものでもいいので何かそういったことを考えるためのコツを掴んでもらえたら良いなという想いがあります。

 

 

実際に取り組んでもらった問題がこちらになります。

スクリーンショット 2020-09-11 20.52.43

 

実施方法としましてはまずは各チームで考えてもらい、最後に代表者の方に発表していただくという方法を取りました。

以下に各チームの回答結果を載せておきます

Aチームの回答です

スクリーンショット 2020-08-27 21.28.06

各単語を分解して、単語に含まれるアルファベットが何回出てきたかを数えてグルーピングしようとしてたらタイムアップになってしまった感じですかね!

頑張って考えている感じがめちゃくちゃ伝わってきてますね〜!

 

 

次はBチームの回答です


$inputs = ["eat","tea","tan","ate","nat","bat"];$result = [];
foreach($inputs as $input){
    $char = str_split($input);
    sort($char);
    $sorted = implode($char);
    $result[$sorted][] = $input; 
}foreach($result as $key => $value){
    echo(implode($value));
    echo PHP_EOL;
}


各単語のアルファベットをソートしてそれをキーにした配列を用意してその配列に元の単語を格納していく感じですかね!

王道っぽくていい感じです!!

 

Cチームの回答です


const sortString = str => str.split(‘’).sort().join(‘’);
const isAnagramBy = a => b => a === sortString(b);
const unique = arr => Array.from(new Set(arr));
const groupByAnagram = words => {
  return unique(words.map(sortString))
    .map(target => words.filter(isAnagramBy(target)));
};
const input = [‘abc’, ‘bca’, ‘qwe’, ‘wqe’, ‘cba’, ‘jkl’];
console.log(groupByAnagram(input));

関数型っぽくてとてもいい感じですね!!
こちらは実装を担当して遠藤さんからコメントを頂いていますので転載します。

自分が実装した方法は、まずは文字列の配列をソートしたうえで、重複した要素を削除して、ユニークな配列を生成します。
次に、ユニークにした文字列を使ってアナグラムか否かを判定する関数の配列を生成します。
最後に、その関数の配列を使って、全ての文字列の配列にフィルターをかけることで、
アナグラムな文字列をグルーピングするという方法です。

フィルタリングした文字列はwordsから取り除けるともっと早くなりそう!といった議論もあり考えさせられる回答だったと思います!

 

さて実際に取り組んでみての感想ですが、どのチームも熱心に議論しておりかつ、楽しんでくれていたようで開催してよかったなと思いました。

(余談ですが、チーム編成に関しては普段の開発メンバーとなるべく被らないようにしてあります。)

私自身もチームに加わって議論に参加していたのですが、「正攻法ではなく少し変わった方法で解いてみたい」といった意見があったりすごく楽しめました(笑)

また議論の方法もホワイトボードを使用しまずは図で書いてみるチームがあったり、最初から実装して少しずつ動かしていくチームもあったりしてその辺も各チームの工夫があって面白かったです!

 

次回があるかはわかりませんが、たまにはこんな感じで普段あまり関わらない人と一緒に何かを取り組む場があるとより社内のコミュニケーションもよりスムーズにいくのかなと思いました。

(ちなみに普段がギスギスしているといったわけではないです笑)

以上です。ありがとうございました!