少ないリソースを酷使する

低レイヤーとレトロPC(PC98,MSX)が好きな情報学生

競プロの過去問をPython, Go, Rust 使って黙々と解く_Day2

苦行 2日目

「競プロの過去問をPython, Go, Rust 使って黙々と解く」 という、1人アドベントカレンダーの2日目です!(遅刻)🎉
このアドカレを始めた理由や、ルールは1日目の記事をみてください。

問題2 Shift only

AtCoder Beginner Contest 081」
B - Shift only

今回は新たに配列的な物ループを意識した問題を選びました。

Python

自分の回答

def how_many_divided(a_val):
    cnt = 0
    while a_val>0 and a_val % 2 == 0:
        a_val = a_val//2
        cnt+=1
    return cnt


n = int(input())
a_lst = list(map(int, input().split() ))

ans = min(map(how_many_divided, a_lst))

print(ans)

map()の使い方を学んでからというもの、map()を活用したコードを書くのが楽しくなってきました。
さて、解き方はそんなに変な解き方はしてないと思います。(後から解説をみましたがだいたい合ってた)
各値が、0奇数になるまで割り続け、割った回数の最小値を答えとする。といった単純明快なコードです。
今回新たにwhile()min()を使いましたが、特に深く考えたところはありません。何も考えず無心で書きました。
ポイントがあるとすればa_val//2のとこで書いてる//ぐらいです。
python/で割り算すると0.0のように実数で答えが返ってくるんですが、//で割ると整数の範囲で答えが返ってきます。

別解

import fractions

N = int(input())
num = list(map(int, input().split()))
ans = num[0]

for i in range(1, N):
    ans = fractions.gcd(ans, num[i])

if ans % 2 == 1:
    print(0)
else:
    cnt = 0
    while ans/2 == int(ans/2):
        ans /= 2
        cnt += 1
    print(cnt)

これが累積GCDの力か・・・! なるほどなと思いました。
ちなみにpython 3.5以上ではgcd()mathに入ってますね。

Go

自分の回答

package main

import "fmt"

func main() {
    n, ans := 0, 0

    fmt.Scan(&n)
    a := make([]int, n)

    for i := range a {
        fmt.Scan(&a[i])
    }

    for i, v := range a {
        cnt := 0
        for v > 0 && v%2 == 0 {
            v = v / 2
            cnt++
        }

        if i == 0 || cnt < ans {
            ans = cnt
        }
    }

    fmt.Println(ans)
}

正直自分ではモヤモヤする仕上がり。スマートなコードではない気がする・・・

入力

今回から入力にfmt.Scan()を使うことにした。すげー使いやすい。

a := make([]int, n)

ループ

ここで、要素数nint型sliceを宣言しています。
goは、配列的なものとして、arraysliceがある。イメージとしてはarrayが固定長配列で、sliceが可変長配列なのかな?
内部的にはarraysliceがラップしている感じらしい。納得。

for i := range a {
        fmt.Scan(&a[i])
    }

このforは、pythonで言うfor inの感じに似ている。と言うかそのまんま。いわゆるforeach ループ
ただし、特徴的なのはfor変数(仮名)に渡される値。以下のように変数1Index変数2Valueが渡される。

for Index, Value := range hoge { ... }

Value用の変数は省略可能なので、値を取り出したくてpythonのようにfor i := range a {}と書くと0 1 2...とIndexしか得られない。
結構個人的にはこの仕様は気に入っています☺️

whileという制御文はgoに存在しない。for 条件式 {}という書き方によってforがwhile的な働きをする。
for{}だけだと無限ループ。なぜwhileを採用しなかったのかはきになるところ🧐

別解

package main

import (
  "fmt"
)

func main() {
  var n, ans int
  fmt.Scan(&n)
  var a = make([]int, n)
  for i := 0; i < n; i++ {
    fmt.Scan(&a[i])
  }

  flag := true
  for flag {
    for i := 0; i < n; i++ {
      if a[i] % 2 == 0 {
        a[i] /= 2
      } else {
        flag = false
      }
    }
    if flag {
      ans++
    }      
  }
  fmt.Println(ans)
}

大体みんな自分と似たり寄ったりな回答でしたが、ちょっと面白かったのがこのコード。
for flag { for hoge { } }の多重forの中でflag = falseすることで多重forを一気に抜けるというもの。賢い。
しかし、Goのbreakはラベル指定でbreakできるので(goto文みたいな感じ)、正直この書き方は好まれないのかも・・・?
結構私は好きですが。

Rust

自分の回答

use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn how_many_divided(mut a_val: usize) -> usize {
    let mut cnt = 0;

    while (a_val > 0) && (a_val % 2 == 0) {
        a_val /= 2;
        cnt+=1;
    }

    return cnt
}

fn main() {
    let n: usize = read();

    // let mut a_vec: Vec<usize> = Vec::with_capacity(n);
    let mut a_vec: Vec<usize> = vec![0; n];

    for i in 0..n {
        a_vec[i] = read();
    }

    let ans = a_vec.into_iter().map(|a| how_many_divided(a)).min().unwrap();

    println!("{}",ans);
}

入力の諸々を関数にまとめました。それだけで昨日の苦労が嘘だったかのように快適にコーディングできました。

vector

// let mut a_vec: Vec<usize> = Vec::with_capacity(n);
let mut a_vec: Vec<usize> = vec![0; n];

素数nで、全ての要素が0で初期化されたベクトルを用意しています。
コメントアウトしている書き方でも同じことができますが、マクロを使った方が個人的に見やすい感がある。

for

for i in 0..n { }

0からnまでのループです。」と、言わなくてもすぐに理解できる。
この書き方は非常に好き(段々ここすきポイントの紹介になってきている)

mapあたり

a_vec.into_iter() //イテレータを生成
    .map(|a| how_many_divided(a)) //割れる回数をカウント
    .min() //最小値を取得
    .unwrap();

コメントの通りです。
pythonと似たような組み方ができたので、昨日の苦労が嘘のようにスラスラと書けました。楽しい。

概念を理解するのはまだまだ難しそうだが、書くことに関してはそこまで苦無くできそうな気がしてきた。(標準入力以外は)

別解

use std::io;

fn read_line() -> String {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line).unwrap();
    return String::from(line.trim());
}

fn main() {
    let n: i64 = read_line().parse().unwrap();
    let ans: u32 = read_line().split_whitespace().map(|s| s.parse::<u32>().unwrap().trailing_zeros()).min().unwrap();
    println!("{}", ans);

}

天 才 か 。

問題の2で割れる回数という条件と、二進数の特徴を使った非常に賢くて、スマートな解き方です。

let ans: u32 = read_line().split_whitespace() //空白区切の数字を読み込み
    .map(|s| s.parse::<u32>().unwrap() //キャスト
        .trailing_zeros()) //2進数で「下のビットから0が続く数」を取得
        .min() //最小値を取得
        .unwrap();

2進数で偶数を表した時、「下のビットから0が続く数」で割れる回数がわかるということですね!
4 -> 100 -> 0は下から2個 -> 2回割れる
しかも奇数がきた場合必ず「下のビットから0が続く数」は0になります。
5 -> 101 -> 0は下から0個

まとめ

1日目に比べると、驚くほどスラスラ書けて全体的に楽しかったです!
もしかしてここで扱っている言語は標準入力についてあまり優しくないのかも・・・
そもそもそんなに必要ないしね。 2日目で得た教訓は「標準入力周りは言語によってはあんまり重要視されてないのかも」ということでした。
以上、また明日!