くろたんく雑記帳

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

MENU

Python3で解く AtCoder Beginner Contest 151 C - Welcome to AtCoder

AtCoder 競プロ ABC-C 数え上げ

単純な数え上げ。問題ごとにACがでるまでWAのカウントをする。

目次

概要

問題

  • 問題は{\displaystyle n}問ある。
  • {\displaystyle m}回提出。
  • 成功すれば{\displaystyle AC}失敗すれば{\displaystyle WA}となる。
  • 1度でも{\displaystyle AC}したらその問題の{\displaystyle AC}の回数は1回。
  • {\displaystyle WA}の回数は問題ごとに{\displaystyle AC}するまでに{\displaystyle WA}した回数である。
  • この時、提出したものの{\displaystyle AC,\ WA}のそれぞれの回数は？

追記：条件にペナルティ数は、高橋君が AC を 1回以上出した各問題において、初めて AC を出すまでに出した WA の数の総和って書いてあった。

解くときに考えた内容

  • {\displaystyle AC}しているかどうかが要なので、問題ごとにTrue, Falseでパターン分け。
    • 問題ごとにboolをリストで持つ
    • {\displaystyle p}問目がまだ{\displaystyle AC}していない状態で {\displaystyle WA}ならインクリメントしていく。

結果的に疑問だったのは、 {\displaystyle p}問目がTrueがでたら、 {\displaystyle p}問目の {\displaystyle WA}の数を足していかないと一部通らなかった。
別に最後に、全部足しても結果変わらないと思うんだけど、どういう例の時に想定と異なることが起きるのかはわからずじまい。

追記： 条件を見落としていた。WAのカウントはACが出ているのが前提なので、ACが出た時点でカウントしなくてはならない。つまり、ACがでていないものはWAがいくらあっても0ってことね。問題はちゃんと読みましょう・・・

コード

n, m = map(int, input().split())
P = [0] * m
S = [0] * m
for i in range(m):
    P[i], S[i] = map(str , input().split())
# 問題によってカウントしたい
WA = [0] * (n+1)
# 全体として何個かがわかればいい
AC = [False] * (n+1)
wa = 0
for i in range(m):
    p = int(P[i])
    # 一度ACになったらその問題は無視
    if AC[p]:
        continue
    # ACになっていない問題の処理
    else:
        # ACになったか判定
        if S[i] == 'AC':
            AC[p] = True
            # ACが通った時のWAのカウントを都度行う必要があるっぽい。違いはわからん
            # 条件でACが出たものに関してWAのカウントをするってなっていた。（条件落としていた。）
            wa += WA[p]
        # ACじゃなかったらWAなので+1していく
        if AC[p] != True:
            WA[p] += 1
# 最後に合計使用するとダメな時がある（条件落としてた）
# wa = sum(WA)（これだとAC出てないものをカウントしちゃう。条件落としてた。）
ac = sum(AC)
print(ac, wa)

Python3で解く AtCoder Beginner Contest 179 C - A x B + C

AtCoder 競プロ ABC-C 約数の個数

ある数の約数を数える場合は素因数分解を使えばいいが、今回は制約が大きいので、素因数分解して、全てのパターンを計算すると間に合わない。{\displaystyle N=i}から{\displaystyle N=N}までの約数の個数をカウントするなら定数倍的に考える方がいい。

目次

概要

問題

  • 正整数{\displaystyle n}が与えられる。
  • {\displaystyle a \times b + c = n}を満たす正整数の組{\displaystyle (a, b, c)}はいくつある？

解くときに考えた内容

  • 約数の個数のカウントだからと言って素因数分解の素数が何回かけられているかっていう風に考えると計算量でダメ。
  • 全パターンのをカウントするので定数倍的に考える。
  • {\displaystyle a \times b}だけに着目すればいい。
  • なぜなら、{\displaystyle c}と{\displaystyle a \times b}は1対1対応するので、
    • 例えば{\displaystyle n=4}の時
    • {\displaystyle c=1}, {\displaystyle a \times b = 3}
    • {\displaystyle c=2}, {\displaystyle a \times b = 2}
    • {\displaystyle c=3}, {\displaystyle a \times b = 1}
  • ここで、
    • {\displaystyle a = 1}の時{\displaystyle a \times b \leq n-1}となるような{\displaystyle b}はいくつあるか
    • {\displaystyle a = 2}の時{\displaystyle a \times b \leq n-1}となるような{\displaystyle b}はいくつあるか
    • のように{\displaystyle a = n-1}の時までを考えると、その値は{\displaystyle \frac{n-1}{a}}の整数部分である。 図を示すと以下のようになる
      f:id:black_tank_top:20200920002252j:plain
      約数の数のカウントを定数倍で考えた時と、素因数分解で考えた時の図

{\displaystyle a}の1-12の列のマス目の値は{\displaystyle b}の値。

{\displaystyle n = 13}とすると、{\displaystyle a \times b \leq 12}になる場合を考えると、{\displaystyle a = 1}の時、{\displaystyle b}は{\displaystyle 12}個取りうる。{\displaystyle a = 2}の時、{\displaystyle b}は{\displaystyle 6}個取りうる。といったように、図で言うと、縦方向に約数の候補を見ていくイメージにで考える。そうすると、計算量は{\displaystyle O(n)}でおさまる。

ちなみにこの図で言うと、横方向に見ると、素因数分解で約数を数えて、組み合わせ数を出しているイメージになる。

コード

n = int(input())
cnt = 0
# aが1からn-1まで動くと考える
for a in range(1, n):
    # a*bがn-1以下であると考える
    cnt += (n-1) // a
print(cnt)

書籍

アルゴリズムの参考書籍
  • 問題解決力を鍛える!アルゴリズムとデータ構造
    けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも結構読みやすいのではないかと期待。（というのもけんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているので）
    投稿時点では、まだ発売前だけど、すでにベストセラー。予約しておかないとすぐ手元に来ないかも!?と思って速攻ポチった。

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

  • 作者:大槻 兼資
  • 発売日: 2020/10/02
  • メディア: 単行本（ソフトカバー）

drken1215.hatenablog.com

いわゆる、螺旋本。Aizu Online Judgeの問題を題材に解説されている。自分としては、 Aizu Online Judgeは最近はβ版運用中で、構成がアルゴリズムの項目ごとに問題がタグ付けされているようなイメージで、ここら辺弱いから集中的にやってみようっていう感じでできるので、いいと思っている。（AtCoderもそんな感じのリスト作って欲しい） ただ、この書籍はC++で書かれているのでPythonでやる場合はあくまでもその過程の考え方を参考にし自分で実装する必要がある。（AOJも解いているので、記事にしていこうかなぁ）

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

AtCoder Beginner Contest 179 参加ログ・感想

AtCoder 競プロ 参加ログ 約数の個数 文字列indexアクセス

約数の数をカウントする方法素因数分解以外思いつかずC解けずOrz

内容

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

結果

AB完。Cは約数列挙はだめだから素因数分解だろと思ったけど計算量{\displaystyle O(N\sqrt{N})}になっちゃうのでダメ。全パターンの約数出すなら定数倍的に考えればよかった。

どう考えたか + α

A - Plural Form

問題タイプ：条件分岐 ・文字列操作

文字列の最後を取得するにはs[-1]とすればいいので、それで条件分岐。

s = input()
if s[-1] == 's':
    ans = s + 'es'
elif s[-1] != 's':
    ans = s + 's'
print(ans)
B - Go to Jail

問題タイプ：条件記述 ヒントで条件が書いてある。実装は、リストの3つめから考えて、2つ前、1つ前、今が全てゾロ目かを満たしていれば、Yesとする。

n = int(input())
D = [list(map(int, input().split())) for i in range(n)]
for i in range(2, n):
    if D[i-2][0] == D[i-2][1] and \
        D[i-1][0] == D[i-1][1] and \
            D[i][0] == D[i][1]:
                print('Yes')
                exit()
print('No')
A x B + C

問題タイプ：約数の個数のカウント

ある数の約数を数える場合は素因数分解を使えばいいが、今回は制約が大きいので、素因数分解して、全てのパターンを計算すると間に合わない。{\displaystyle N=i~N}なら定数倍的に考える方がいい。別記事にする。

D - Leaping Tak

問題タイプ：DP

動的計画法で解くが単純にやると、計算量が{\displaystyle O(N^2)}なので、移動方法が少ない区間の和を利用する必要がある。別記事にする。

おわりに

ABはできたが、Cも図表をかけば規則に気づけたと思うが、瞬間的に理解できないとまだまだだと思う。まだまだ問題を解く量が少ない。別の仕事も多くなかなか精進できないが、やれるだけやろう。

Python3で解く AtCoder Beginner Contest 150 C - Count Order

AtCoder 競プロ ABC-C 順列 全探索

順列の全探索をすればいい。

目次

概要

問題

  • {\displaystyle n}を与えられる。
  • {\displaystyle (1, 2, 3, ... n-1, n)}の順列のリストを考える。（{\displaystyle l}とする）
  • ある順列{\displaystyle p}と{\displaystyle q}を与えるので、{\displaystyle l}を辞書順に並べた時に{\displaystyle p}と{\displaystyle q}が何番目かを{\displaystyle a}と{\displaystyle b}とする。
  • {\displaystyle |a - b|}は？

解くときに考えた内容

  1. permutationsで全部リストあげて
  2. ソートして(ソートされているから必要ないかも)
  3. {\displaystyle n \leqq 8}だから{\displaystyle 1 \times 2 \times ... 7 \times 8 = 40320}と大して大きくない。
  4. そのままforで回して{\displaystyle p}と{\displaystyle q}が何番目か調べて、差の絶対値を計算する。

コード

from itertools import permutations

n = int(input())
p = tuple([int(x) for x in input().split()])
q = tuple([int(x) for x in input().split()])
L = sorted(list(permutations(list(range(1, n+1)), n)))
for idx, l in enumerate(L):
    if l == p:
        P = idx
    if l == q:
        Q = idx
ans = abs(Q - P)
print(ans)

書籍

最近買って面白かった本
アルゴリズムの参考書籍
  • 問題解決力を鍛える!アルゴリズムとデータ構造
    けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも結構読みやすいのではないかと期待。（というのもけんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているので）
    もうすぐ手元にくるので楽しみである。

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

  • 作者:大槻 兼資
  • 発売日: 2020/10/02
  • メディア: 単行本（ソフトカバー）

drken1215.hatenablog.com

いわゆる、螺旋本。Aizu Online Judgeの問題を題材に解説されている。自分としては、 Aizu Online Judgeは最近はβ版運用中で、構成がアルゴリズムの項目ごとに問題がタグ付けされているようなイメージで、ここら辺弱いから集中的にやってみようっていう感じでできるので、いいと思っている。（AtCoderもそんな感じのリスト作って欲しい） ただ、この書籍はC++で書かれているのでPythonでやる場合はあくまでもその過程の考え方を参考にし自分で実装する必要がある。（AOJも解いているので、記事にしていこうかなぁ）

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

【書評】機械学習の炊いたん３

書籍紹介 機械学習 tech

技術書典９でサークルml-titansさんの機械学習の炊いたん３を読んだので、感想を書く。
こんな感じのパッケージ。

f:id:black_tank_top:20200914103459p:plain

techbookfest.org

いろんな内容が盛りだくさん。一つでも興味があれば、ポチってみるといいと思う。

感想

sonodanoさん、emergentさん、kirikeiさん、 tomo_makesさん、timさんの5名による作品。個人的には、emergentさんの「Spleeter と音声認識を使って空耳検出器をつくる」、データサイエンティスト観点から、kirikeiさんの「データで見てみるプロ野球 −スクレイピングから可視化まで」tomo_makesさんの「データサイエンティスト、AI エンジニアのための経営学‧ソフトウェア工学」が特に気になって購入した。全体的に非常に面白い内容で、実際に手を動かしながらやることで、さらにその面白さを体感できる一冊だった。

本書の概要と感想

各章についてそれぞれ書く。

1 ファイル強化学習

内容としては、筆者の方針で、わかりやすさを重視して、Classはなるべく使わず、GPU対応も省略、理論もそこそこにという形で、実際に本章と以下用意されているipynbを実行しながら、強化学習を体感できる。一部、Ｐｙｔｈｏｎで学ぶ強化学習　［改訂第２版］　入門から実践までのfrozen_lake_util.pyを使っているので、見慣れた図があった。 github.com アルゴリズムとしては、以下が紹介されている。
• SARSA
• Q-Learning
• Deep Q-Learning
• Vanilla Policy Gradient
• Vanilla Actor Critic
• Deep Deterministic Policy Gradient
実際にコードを実行しながら体感できるのだが、強いて言えば、これらの違いが図や表でまとまっていると、初学者にはよりわかり良いのではないかと思った。（一通りさらっている人には問題ないとは思う。）

Spleeterと音声認識を使って空耳検出器をつくる

あの「実践 Rust プログラミング入門」の共著者の一人であるemergentさんの章。

Spleeterというのを知らなかったのだが、楽曲音源分離のツールでこれは非常に面白い。 github.com

書籍通りに行えば十分にできるが、GPUがないと少し重いのと、Dockerに明るくないと少し導入が難しいようにも感じた。自分はColabで実行できるように少し書き直しながら試した。

とtweetしたら、すかさずtomo_makesさんがフォローしてくれました。ありがとう！

著作権等の問題があるような気がするので、uploadはしないが、結構綺麗に音源が分離される。空耳についてはあまり面白いのはまだできていないが、引き続き色々試してみたいと思う。

データで見てみるプロ野球 −スクレイピングから可視化まで−

最近だと、u++さんが企画・運営しているSports Analyst Meetupをみていると、スポーツの分析は比較的ホットで、面白い内容が多い。Sports Analyst Meetupの資料を見ればその面白さは伝わってくる。 spoana.connpass.com

本章では、スポーツの分析を行うのに、まず行き詰まるデータの取得を簡単にスクレイピングしてきて、セイバーメトリクスを可視化するという流れだ。正直、野球に疎いので、NPBでやってくれたのはありがたい。海外だとさらによくわからないし。ただ、以前挑戦したことがあるのだが、NPB のページは残念ながら URLの整理が微妙で、結構めんどくさい。しかし、この章に説明があるが、この図がめっちゃわかりやすくてなるほどスクレイピングのコツまでわかりやすかった。

f:id:black_tank_top:20200914090525p:plain

また、セイバーメトリクスと可視化という節でカラムの説明がまとまっており、これは「野球に明るくない私には」非常に助けになった。打者指標のOPS, IsoDや投手指標のWHIPについても細かな説明があり、あーこんな風に考えるのね、っていう形で野球ドメインが低い私にも理解できたし、むしろこんな風に考えると野球が面白いと思い始めた。

また、全体のコードは以下のexampleにnotebookがあるので、ぽちぽちしながら試すことができて楽しい。 github.com

データサイエンティスト‧AI エン ジニアのための経営学‧ソフトウェア工学

AI、データ分析の社会実装の難しさをどうやって解決していくべきかがうまく整理されて書かれている。 これからAI、データ分析を始めて行こうっていう人、もしくは、すでに始まっているけれど、自分がデータサイエンティスト、機械学習エンジニアでプロジェクトリーダーでなんか偉い人に視座が低いとか言われて、うまくいってないんだよなっていう状態の人に読んでほしい章っていう感じ。というのも、データ分析したり、AIを作っても、相手が望む形で使われて、行動変容が起きなければ、正直意味がないと自分は思っている。本章でも述べられているが縦割りが行われていてもそれぞれが「ビジネスからソフトウェア工学までの知識」をもって、適切にうごかないとうまくいかないことが多いのは経験則的に理解できる。さらに現場的には「データサイエンティストだから」「MLエンジニアだから」といって、ビジネスの構成要素や性質・経営戦略について考えたくない、考えるのはビジネスプランナーや経営層であるっていうギャップが現実的によくあって、これで辞めたりする。どちらかというと、アサインされた役割とは無関係に「ビジネスからソフトウェア工学までの知識」をもってしてプロジェクトを進めていってもらいたいっていうのが、プロダクトオーナー的視点になるんだけど、専門家意識というか機械学習だけしたい。与えられた分析だけしたいっていうパターンはよくある話だ。（もしそんな風に働きたいなら、最初に会社と握っておくことが肝心。）

話が逸れたので、話を本章に戻して、 BABOK DMBOK PMBOKについても触れていて、AI・データ分析プロジェクトをリードしていったり、マネージメントする人はこれらにも目を通すことをオススメする。やはり先人の知恵は重要で、そこから自分の会社の方針ややり方に合ったものを組み立てていくのが即効性が高いと思う。

IT システムによる改革‧改善の生まれ方という節に、

  • 経営戦略
  • ビジネスモデル
  • ビジネスプロセス
  • エンジニアリング

のゴール設定についても言及がありこれが非常に整理されていて、自分自身の知識と新たな知識が頭の中で整理されて、どのように進めていくのがいいのかという地図をうまく設計できるようになると感じた。

解析力学は伊達じゃない!

ハミルトン力学もHamilton Neural Networkもよく知らない状態で読んだが、導入のニュートン力学やラグランジュ力学に関する、図や式が豊富でめちゃくちゃわかりやすかった。 本章では、実装は本家に任せている状態で、とりあえず以下を試してみた。 github.com 力学系とDeepをうまく組み合わせることによって、物理現象の挙動をうまく表現できているように見える。これは非常に面白いとおもった。この分野に明るくないので、応用先がぱっとは思いつかないが、引き出しの一部が増えるいい内容だった。

終わりに

tomo_makesさんとは、Colabが流行りだすちょい前で、秒速DEEP LEARNINGがでたときからお世話になっていて、そのあとに、図解速習DEEP LEARNINGというColabを解説した商業本も出されて、同人誌から商業本になってすげーっていう感じ。文章もすごくわかりやすいし、たまに困って相談するとものすごく親切に対応してくれていつも助かっている。

今回の機械学習の炊いたん３は、かなり内容が多岐に渡っていた。全体を通して頭が整理されたし、読みながら実装して楽しい本だった。

以前出されたどの本も非常に有益なことが書かれているので、気になる項目があれば、一読してみると良いかと。

techbookfest.org

お願い（欲しい書籍リスト）

ずうずうしいのですが、ブログを続けるのも大変で、基本自分の学習メモのためですが、サポーター募集です。ポチッとしてくれると嬉しいです。

https://www.amazon.jp/hz/wishlist/ls/2EDNNTYRW2BJE?ref_=wl_share

もしくは、レビューなど書くので、献本していただけたらものすごく喜びます（お問い合わせ or TwitterのDMからお問い合わせ下さい。）

Python3で解く AtCoder Beginner Contest 178 C - Ubiquity

AtCoder 競プロ ABC-C 繰り返し二乗法 包括原理

包括原理より、全パターンから条件に合わないものを引く。
計算過程では繰り返し二乗法を使う（ {\displaystyle x^n}という形は愚直に計算すると遅い）

目次

概要

問題

  • 長さ{\displaystyle n}個の整数列{\displaystyle a}が以下の条件に当てはまる個数を{\displaystyle x}とすると{\displaystyle x\ mod (10^9+7)}を求める。
    • 整数列で使えるのは整数は0から9までの10個の整数。
    • 長さ{\displaystyle n}個の整数列{\displaystyle a}に0を含む。
    • 長さ{\displaystyle n}個の整数列{\displaystyle a}に9を含む。

解くときに考えた内容

  • コンテスト中は求めたいものをそのまま求めようとして失敗。
  • 全てのパターンから条件に合わないパターンを引く
  • 全パターンは長さ{\displaystyle n}個の整数列で10文字使えるので、
    • {\displaystyle 10^n}個
  • 0を含まないパターンは、長さ{\displaystyle n}個の整数列で0以外で構成するので9文字使えるので、
    • {\displaystyle 9^n}個
  • 同様に9を含まないパターンは、長さ{\displaystyle n}個の整数列で9以外で構成するので9文字使えるので、
    • {\displaystyle 9^n}個
  • ただ、上記だと0と9をどちらも含まない場合を重複してかぞえているので、その値は、長さ{\displaystyle n}個の整数列で0, 9以外で構成するので8文字使えるので、
    • {\displaystyle 8^n}個
  • よって、求める組み合わせの数は、
  • {\displaystyle 10^n - (2 \times 9^n - 8^n) = 10^n - 2 \times 9^n + 8^n}個
  • 今回は{\displaystyle n}が大きいと、これは巨大な数になるので、{\displaystyle mod (10^9+7)}で考えるが、制約が大きいため愚直にやるとTLEになる。
  • ここで、{\displaystyle x^n}はどう計算するかを考える。繰り返し二乗法と呼ばれる方法を使う。

    繰り返し二乗法
    例えば、{\displaystyle x^{50}}の時、{\displaystyle 50 = 2^5 + 2^4 +2^1}なので、{\displaystyle x^{50} = x^{2^{2^{2^{2^2}}}} \times x^{2^{2^{2^2}}} \times x^2}とかける。
    実装としては以下のようになる。 ただし、Pythonはmathにpowがありこれ自体が繰り返し二乗法で実装されているらしいので自分で実装する必要はないが、勉強のため。

# 繰り返し二乗法の実装例
def modpow(x, n, mod):
    res = 1
    while n:
        if n % 2:
            res *= x % mod
            res %= mod
        x *= x % mod
        n >>= 1
    return res
  • {\displaystyle 10^n - 2 \times 9^n + 8^n}を計算する時に、それぞれの項で繰り返し二乗法をつかって求める。
    （足し引き後もmodを計算するのを忘れずに）

コード

n = int(input())
mod = 10 ** 9 + 7 #素数

# 繰り返し二乗法
def modpow(x, n, mod):
    res = 1
    while n:
        if n % 2:
            res *= x % mod
        x *= x % mod
        n >>= 1
    return res

# 全パターン:10 ** n
all_p = modpow(10, n, mod)
# 0を含まないパタンーン:9 ** n
not_0 = modpow(9, n, mod)
# 9を含まないパターン:9 ** n
not_9 = modpow(9, n, mod)
# 0と９を含まないパターン:8 ** n
not_0_9 = modpow(8, n, mod)
# 条件のパターン
ans = (all_p - not_0 - not_9 + not_0_9) % mod
print(ans)

書籍

アルゴリズムの参考書籍
  • 問題解決力を鍛える!アルゴリズムとデータ構造
    けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも結構読みやすいのではないかと期待。（というのもけんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているので）
    投稿時点では、まだ発売前だけど、すでにベストセラー。予約しておかないとすぐ手元に来ないかも!?と思って速攻ポチった。

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

  • 作者:大槻 兼資
  • 発売日: 2020/10/02
  • メディア: 単行本（ソフトカバー）

drken1215.hatenablog.com

いわゆる、螺旋本。Aizu Online Judgeの問題を題材に解説されている。自分としては、 Aizu Online Judgeは最近はβ版運用中で、構成がアルゴリズムの項目ごとに問題がタグ付けされているようなイメージで、ここら辺弱いから集中的にやってみようっていう感じでできるので、いいと思っている。（AtCoderもそんな感じのリスト作って欲しい） ただ、この書籍はC++で書かれているのでPythonでやる場合はあくまでもその過程の考え方を参考にし自分で実装する必要がある。（AOJも解いているので、記事にしていこうかなぁ）

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

AtCoder Beginner Contest 178 参加ログ・感想

AtCoder 競プロ 参加ログ

初めてAしかできないっていう。本番弱いなぁ。 復習しっかりする。

内容

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

結果

Aのみ。 Bはa, b, c, dの場合分けを全部やろうとして大失敗。掛け算の結果のmaxをとればよかった。Cもまともに数えようとして大失敗。目的外のものを数えるっていうのが結構パターンとしてありえるけど本番でそれができない・・・。Dは目すら通せなかった。

どう考えたか + α

A - Not

問題タイプ：条件分岐

{\displaystyle x}が0か1で条件分岐

x = int(input())
if x == 0:
    print(1)
else:
    print(0)
B - Product Max

問題タイプ：最大値

珍しくfor文使う問題じゃなかった。それは制約から判断できる。場合分けをしようすると、複雑になりすぎる。掛け算のパターンとしてありうるのは{\displaystyle a \times c, a \times d, b \times c, a \times d}なので、その最大値が答え。もう少し具体的に考えると、{\displaystyle a}に{\displaystyle c}か{\displaystyle d}をかけた時に それぞれの正負を考えずに大きい方を選択すればよい。{\displaystyle b}についても同様に考えるので、以下のようになる。

a, b, c, d = map(int, input().split())
ans = max(max(a*c, a*d), max(b*c, b*d))
C - Ubiquity

問題タイプ：順列・数え上げ

そのものを数えようとすると、パターンが多すぎて複雑化してダメ。こういう時は、全パターンから条件外のものを引き算すればいい。たとえば、数列に{\displaystyle 0}が含まれないような数列の数。同じく{\displaystyle 9}も。同時に含まれないものは逆に足す。これは別記事にする。

D - Redistribution

問題タイプ：DP

動的計画法で解く。ちゃんと問題を読めていないので、別記事にする。

おわりに

初めて、Aしかできなかった。Bができなかったのは完全に下手こいた。Cも条件外を数えれば良いだけだったのに気づけなかった。ここら辺も問題を解く量が少ないからかな。まだ200問程度しか解いてないので、もう少し精進を続けよう。