苦行 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)
ループ
ここで、要素数n
のint型
sliceを宣言しています。
goは、配列的なものとして、array
とslice
がある。イメージとしてはarray
が固定長配列で、slice
が可変長配列なのかな?
内部的にはarray
をslice
がラップしている感じらしい。納得。
for i := range a { fmt.Scan(&a[i]) }
このforは、pythonで言うfor in
の感じに似ている。と言うかそのまんま。いわゆるforeach ループ
。
ただし、特徴的なのはfor変数(仮名)
に渡される値。以下のように変数1
にIndex
、変数2
にValue
が渡される。
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日目で得た教訓は「標準入力周りは言語によってはあんまり重要視されてないのかも」ということでした。
以上、また明日!