くろたんく雑記帳

日常とか、わんちゃんとか、機械学習とか、競プロとか、

MENU
トップ > 参加ログ > AtCoder Beginner Contest 171 参加ログ・感想

AtCoder Beginner Contest 171 参加ログ・感想

参加ログ AtCoder 競プロ 文字列メソッド Greedy n進法 カウンター 差分更新 クエリ処理

内容

  • Python3でやっている。
  • 参加ログ。
  • 所感。
  • コンテスト中に何を考えたか。
  • コンテスト後に解説をみたり、少し整理したりしたくらいの内容。
  • 問題の詳細で細かく書こうと思うものは別記事とする。
  • E以上はとりあえず現状自力では無理なのでDまで。解けるようになってきたら更新するかも

結果

6分ちょいでAB2完。自分の中では順調。 そこから、Cに取り組んで、できそうなイメージはあったので、イケると思って雑にやったら実装で頭がこんがらがってずっと悶絶して終了。特性には気づけていたのに、うまく実装ができずに悔しい結果。終了後、解説PDFみて、問題を整理しながらやったらできた。単純に問題の落とし込み方を間違えていたOrz

終了後にDを見たら、むしろDの方がパッとみた瞬間にやりやすさを感じたくらいで、こちらも終了後に行ったら、解説見なくても解けたので、１問にこだわりすぎず、ハマったらちょっと頭をリセットするのも重要だと思った。

どう考えたか + α

A - αlphabet

問題タイプ：文字列メソッド

大文字小文字問題なのでstr.lower()でともかく小文字にして元の文字と比較とした。 終わってからドキュメントをよく調べるとstr.islower()っていう、もろな関数があった。こちらで判定する方が素直だった。他にもstr.isXXXX()みたいな関数があるので判定問題用に調査しておく。

B - Mix Juice

問題タイプ：Greedy？

{\displaystyle P_i}を小さいものから{\displaystyle k}個とればいいので {\displaystyle P_i}を昇順にソートして頭からk個分sumするだけ

C - One Quadrillion and One Dalmatians

問題タイプ：n進法

完全にやらかした。ワンちゃんの問題なのに。。。解けそうだったのに。。。

{\displaystyle 26+26^2+26^3+...+26^i}という形をなんとなくイメージすることはできたが、なぜか上から見ていかないといけないと思い込んでしまったのと、上の式のイメージが甘くとりあえず、出てきている数字を26で割ったあまりをa~zに当てはめればいいだけと安直に考えたのが間違いだった。

  • 1文字のパターンの時は、{\displaystyle N}
  • 2文字のパターンの時は、{\displaystyle N - (26)}
  • 3文字のパターンの時は、{\displaystyle N - (26+26^2)}

みたいな感じで、意識すれば解けたと思う

整理すると、

この問題は番号Nから何文字使うの名前なのかを判定する過程とi文字ならばその数値を26進数と考えて、26で割った余りをa~zに割り当てる過程という風に問題を２つに切り分けて考えればよかった。

  1. 何文字使うの名前なのかを判定する過程

    for文の中で{\displaystyle N}が{\displaystyle 26^i}以下かどうかを判定する。そうでないなら、{\displaystyle N - 26^i}をしてさらに回す。

  2. i文字ならばその時のNの数値を26進数に見立てて割った余りをa~zに割り当てる

    26進数として考えればいいだけなので、{\displaystyle N-1}を{\displaystyle N}として26で割ったあまりをa-zに当てはめていく（a:0 ... z:25）。そして、商を{\displaystyle N}とするというのをi回行うだけ。chr(97)が{\displaystyle a}に該当するので、それに26で割った余りを足せばいい。

その他注意点

  • 1つ目の過程ではiは11で十分

    {\displaystyle26+26^2+26^3+...+26^{11}}が{\displaystyle 10^{15}+1}を超えるので

  • 下の桁から計算しているので逆に出力が必要な点も注意

  • よく考えたらわざわざリストじゃなくて文字列のまま+していけばいいということにPDFを見て気づいた。

  • そして、中のfor文もjじゃなくて_の方がいい。

D - Replacing

問題タイプ：カウンター、差分更新、クエリ処理

コンテスト後に行った。 愚直にやると10**10だから当然TLE（提出結果）

そもそも、操作によって生じる元の合計との差分さえわかればいいだけなのでまず先に、どの数字が何個あるかを計算する。辞書で管理して、bのvalueをcのvalueへ足して、差分はbの個数*(c-b)として、bのvalueを0にすればいい。

その他注意点

  • 辞書にcを追加する時に、setdefault()を使って辞書にcが存在しないときの対応をした。
  • bのvalueをcのvalueへ足す時にbのvalueがない場合の対応としてd.get(b, 0)とした。（要するに、bのvalueがない場合cのvalueへ0が足され、bのvalueがある場合はcのvalueへ0が足される）
  • defaultdict()を使うと上記のような面倒な分岐をいちいちやらなくていいということを知った。
  • ちなみに自作CounterだとTLEになったOrz、なのでcollections.Counter()をつかった。

おわりに

参加ログ・感想と思ってラフに書くつもりだったけど、これだけでも結構頭が整理されるので、終わった後にはこれを続けよう。結果的に色々調べるし。