名もなき未知

エンジニアリングとか、日常とかそういうのをまとめる場所。

ABC105解いてみた(が全然解けなかった話)

うーん、一ヶ月ぶりくらいに競技プログラミング問題をちゃんと解いている気がするが、あまりに勘が働かなすぎたのでメモをする。 復習なのでコンテストには出ていません。

A, B問題

覚えがないが、Aは分岐するだけ、Bは総当たりだった気がする。

C問題

https://beta.atcoder.jp/contests/abc105/tasks/abc105_c

−2進数 という概念を求める。ちなみに被ることがないので表現能力的には2進数と変わらないらしい。頭おかしくなる。

スモールケースで求めようとしたけど、全然見えてこなかった。このページを少しだけ参考にした。だいたい今回求めるものと一緒のはず・・・。

http://sky.geocities.jp/bunryu1011/mainasu2.html

結局一部ケースではうまくいくけど、駄目なケースが多発して答えを見た。結果として普通に2進数求めるのとそう変わらんやんけ。となり、コレはもう少し手を動かしてシミュレーションするプログラム書かないとあかんのうと言う気持ちになった。まる。

Submission #3004106 - AtCoder Beginner Contest 105

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def solve():
    n = int(input())
    ans, m = "", 1
    while n != 0:
        m *= (-2)
        if abs(n) % abs(m) > 0:
            ans += "1"
            n -= m // (-2)
        else:
            ans += "0"
    print(ans[::-1] if ans else 0)

if __name__=="__main__":
    solve()

D問題

https://beta.atcoder.jp/contests/abc105/tasks/abc105_d

結論から言うとコレも正確な回答を求められなかった。差分を求めてごにょごにょすればいいよなー(想定解と発想は一緒だった)が、何を思ったかこの計算じゃオーダー的に間に合わないよな・・・ とかずっと考えていて、答え見てそれでよかったのか・・・(困惑)となった。本番だったら何も考えずにとりあえず投げてみて通ればラッキーだなとかやってそう。

あと0のケースだけ気をつける必要があって、最初それに気づかずにサンプルの数値が合わず混乱した。割とわかりやすいサンプルなんだから、冷静になろうね。

方針としては差分の積み上げをMODして、Dictに保存してぶつけるだけ。0のケースだけ数が変わるので、考慮。 DefaultDict使えば割ときれいに書けるし、コレでいいかとなった。

Submission #3004319 - AtCoder Beginner Contest 105

from collections import defaultdict

n, m = map(int, input().split())
al = [int(i) for i in input().split()]
d, t = defaultdict(int), 0
for i in range(n):
    t = (al[i] + t) % m
    d[t] += 1
ans = 0
d[0] += 1
for k, v in d.items():
    ans += v * (v - 1) // 2
print(ans) 

解いてみて

コレ本番だった間違いなく2問完だったなと思うので、練習でホッとしている。しかし、コンテスト中ではない気の抜けたタイミングで解いても、これくらいの点数の問題はササッと解けるくらいの実力は身につけておかないとレーティング向上出来ないよなーとか思った。

がんばりましょう。

余談

他の人のPythonのコードを見たときに、うーん、PythonなのにすごいJavaっぽいとか、C++っぽいなと感じることがあって(具体的にはリストの内包表記とか、スライスをあまり使ってない)、なんとも言えない気持ちになり、自分が普段競技で書いてるようなコードを拙作ながらわかりやすい形で公開することにしました。

せっかくPythonで解いているのだから、Pythonっぽい強力でで短いコードを使っていこうよという気持ちはあるので、普段書いているようなコードをどこかでまとめるような機会を作りたいですね。

終わり。