くろたんく雑記帳

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

MENU

HHKB プログラミングコンテスト 2020 参加ログ・感想

久しぶりの企業のコンテスト。 最近諸事情により全然精進していないので結果的にはいまいちだったが、久しぶりだったので楽しかった。


内容

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

結果

AB完。 Cはもうちょい柔軟に考えないとだった。元のリストの[0, 1, 2, ... n-1, n]に着目しすぎた。何方かと言えば、既出のPに着目するように考えないとだめ。


どう考えたか + α

A - Keyboard

問題タイプ:条件分岐・文字列操作 Sの値が'Y'ならYを大文字に Sの値が'N'ならYをそのままに

s = input()
y = input()
if s == 'Y':
    print(y.upper())
else:
    print(y)

B - Futon

問題タイプ:隣合わせの条件

要するに、以下をカウント 1. 行方向に見たときに'.'が連続しているかどうか。 1. 列方向に見たときに'.'が連続しているかどうか。 入力から読み込んだ時は行方向にlistになるので、まずは行方向からカウント、終わったら転置して(trans(x)が転置の自作関数)、同じやり方で列方向をカウント。

# 多重リストの転置関数
def trans(x):
    return ([list(i) for i in zip(*x)])

h, w = map(int, input().split())
S = [[v for v in input()] for _ in range(h)]
cnt = 0
# まずは行方向の'.'の連続
for s in S:
    for i in range(1, w):
        if s[i-1] == '.' and s[i] == '.':
            cnt += 1
# 次に列方向の'.'の連続
ST = trans(S)
for s in ST:
    for i in range(1, h):
        if s[i-1] == '.' and s[i] == '.':
            cnt += 1
print(cnt)

C - Neq Min

問題タイプ:集合

{\displaystyle P}を一つずつ取り出して、set()して、その集合に前の時に答えた値(最初は0)が含まれるなら+1するをしてから値をprint()すればいい。 リストをremoveとかでやろうとすると{\displaystyle O(N^2)}でアウト

別記事にする。


おすすめの書籍

アルゴリズムの参考書籍

とうとう発売された。現在読み中なのである程度読み込んだら感想を書く予定。
けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!(実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい)どのようなステータスの人にもおすすめの一冊になっている。

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

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

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

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

最近ポチった書籍

アルゴリズムとは関係ないが、一応機械学習も生業としているので、関連書籍は目を通すようにしている。 強いていうならば、第3章の数学のおさらいの最適化・確率あたりは関連がある。その他、回帰分析・分類・ニューラルネットワーク強化学習教師なし学習とかなり幅広く、初学者が一通り学ぶには良さそうである。

blacktanktop.hatenablog.com

書評は書いてある。本家にはnotebookがなかったので、一番簡易的に試せるJupyter notebookも以下のrepositoryに置いたのですぐ試せる。

github.com