【AtCoder】ABC004を解いたのでメモ【Python3】
結果と最終提出コード
解答中の心境
【A】
- 最高によゆー
【B】
- 下手な書き方だけど綺麗に書こうと悩むよりはマシ？
【C】
- すぐに規則性を見つけられた！
【D】
- 解説の方法1を使うことには気づけた
- 解説にもある、『赤を跳ね飛ばす〜』の説明箇所を処理するのに苦労した
- 5つだけどうしても通らないケースがある...なんで...
解説やコメント
【A】
- なし
【B】
- 1次元の配列に入れて逆から取り出せば良かったみたい
【C】
- なし
【D】
- 解法が3つ紹介されている
- 私もやったが、広げ方を考えて最後に集計する
- 動的計画法を計算量が減るように工夫して使う
- 最小費用流を使う
解法1の高速化を詰まることなく実装できたのは良かったが、5つ通らないのは納得いかない！コンテスト終わったらテストケースを公開してくれないかな。笑
動的計画法はちょいちょい聞くが、再帰関数に苦手意識がありすぎて実装できない...。どこかのタイミングで克服しなければ...
費用最小流は私には早そうなのでスルーで！笑
得た知識
- 関数外で宣言した値を関数内で変更するには
globalつけようね！1時間ぐらいハマったよ！ - おおまかな計算回数を求めると高速化が必要か判断しやすくなるっぽい
まとめ
- 動的計画法が仲間になりたそうにこっちを見ている。
- 満点は遠かったが部分点取れてるし、落ち込まずやろう。
- AtCoderの中の人に「コンテスト終了後にテストコードを公開しようぜ！」って言えるようにレートガシガシあげなきゃ...笑
追記
AtCoderのテストケースは古すぎないものであれば公開されていました！
【AtCoder】ABC003を解いたのでメモ【Python3】
結果と最終提出コード
解答中の心境
【A】
- テストコードすら実行しない怠慢によって、このレベルを間違ったのは内緒。
【B】
- もっとスッキリ書けそう？
【C】
- 法則に一瞬で気づいた。わーい。
【D】
- 公式を作り出すのに5分程度しかかからなかった。
- なぜ
10^9 + 7の余りなんだろうか。この数字良く見る気がする？ - 後述するが、
/の動作にハマった
解説メモ
【A】
- なし
【B】
- 連想配列で手抜き出来るよう
【C】
- なし
【D】
- オーバーフローの可能性があったっぽい。Pythonだからか気にせず解けてしまった...笑
- 最後の1点は包除原理を用いて計算していくと良かったそう。包除原理っていうのは3グループが重なった時にベン図の真ん中求めたアレのこと。
- なるほど！
10^9 + 7は大きい素数なのか。そりゃそうか。笑
得た知識
for + zip()の使い方map(int, input().split())という格好良い&高速な書き方- でっっっっかい数の除算時に安易に
/を使うと危険！【リンク先工事中...】
まとめ
- テストコードは実行しよう。
- なんと...時間内に全部満点になった。誤答も最初の1回だけ。
- でかい数は慎重に扱おう
【AtCoder】ABC002を解いたのでメモ【Python3】
結果と最終提出コード
解答後の心境
【A】
- これは簡単。入力練習。
【B】
- ワンライナーで脳汁出た。
【C】
- 今回はCが簡単だった。行数の削減により可読性が下がったのは気のせい。
【D】
- 2次元リストで議員同士の関係を...とかやってると死んだ。
- 手も足も出なかった(。´・ω・`)
解説メモ
【A】
- なし
【B】
- なし
【C】
- ヘロンの公式が紹介されていた。大学受験に勉強した記憶が...
【D】
- 最大クリーク問題という有名な問題らしい。残念、初耳です。
- まさかの全パターンチェックのゴリ押し。与えられる数が小さい時はゴリ押せるかもと疑っても良さげ。
- 全パターンのチェックをpythonで綺麗に行なっている方がいたので、リンクをぺたり。《リンク》
- 再起でも出来るっぽいが再起は混乱するので苦手...。
得た知識
join()の使い方abs()の使い方- pythonの組み合わせを出力する関数
combinations()は意外と軽い - setという、順序を持たないlistのような仕組みがある
まとめ
- 時にはゴリ押しが必要
- 高速な処理の解答を出している方々のコードは綺麗
- ここら辺のレベルは結構パターン化されてそう？ほぼ同じ処理をしている人がたくさんいた。
【AtCoder】ABC001を解いたのでメモ【Python3】
結果と最終提出コード
解答後の心境
【A】
- これは簡単。入力の練習レベル。
【B】
- 単位
mをkmに直し忘れのミスがあったが、他は問題なし。
【C】
- デバッグ用の出力を消し忘れた。
Nの扱いを間違えてREを出してしまった。
【D】
雨なし：0, 雨開始：1, 雨終了：2の要素を使って状態を管理するリストを作成した。WAを出しまくっているのは、5の丸め方にミスがあることに気づかなかったから。TLEを解決できず断念。Pythonの処理速度のせいにしようとするも、クリアしている方々を発見してしまう。
解説メモ
【A】
- なし
【B】
- なし
【C】
- 小数対策が考慮出来てなかった。細かい誤差は難しい。
【D】
- 一次元配列で行なっていた。見やすさの観点から二次元にしたのだが、処理時間の増大の原因になったか？
- 『先にソートすると高速化できる』と。なるほど！
- 座標の圧縮？ピンとこない...
- 『いもす法』を使う方法も。自分の方法と比べると色々な問題に応用が利きそう。
得た知識
format()の使い方input()の使い方//はint型に変換されず、floatのまま- python3の
round()は丸めるので、一般的な四捨五入の場合は自前で実装 - いもす法
まとめ
- 久しぶりにPythonを触ったけど、全く書けなくなっていた...。
- 解けても、綺麗に書けているか不安。
- 他の人の提出コードの実行時間が1/10くらいなのでビビっている。笑
- 「この処理は重い！」というテンプレ的なのを覚えないとやばそう。
【AtCoder】ABC010：A - ハンドルネーム【Python3】
提出コードと結果
Submission #3041264 - AtCoder Beginner Contest 010
ひとこと
Pythonの文字列は変更不可なので、新しくオブジェクトを作ってるらしい。
【AtCoder】ABC009：A - 引越し作業【Python3】
提出コードと結果
Submission #3041246 - AtCoder Beginner Contest 009
ひとこと
math.ceilで切り上げ。math.floorで切り捨て。
import mathも忘れずに！
【AtCoder】ABC008：A - アルバム【Python3】
提出コードと結果
Submission #3041224 - AtCoder Beginner Contest 008
ひとこと
x, y = (int(_) for _ in input().split())を脳が覚えてきた！
