AOJ0525: おせんべい

おせんべい | Aizu Online Judge

蟻本初級の練習問題にあったので解いた。

解き方

  • どの行をひっくり返すかは、全部で2^R通りなので、これについてはすべて試すことができる。
  • ひっくり返す行を決めて、ひっくり返した後は、各列で裏と表のうち、多い方の数の和が、最大値となる
  • ひっくり返す行の場合それぞれについて、上記のように最大値を求めて、それらすべての最大値の答え

github.com

AOJ0121: 7パズル

7 パズル | Aizu Online Judge

蟻本初級の練習問題にあったので解いた。

解き方

  • 終了時点(綺麗に整列した状態)から幅優先探索を行い、各状態から終了状態までの最小回数を求める
    • 状態の個数はたかだか8!個程度なので、この前計算は十分間に合う
  • 各クエリについて、上記で求めた最小回数を表示

ハマったところ

  • 状態遷移をミス(右上←→左下の移動を禁止できていなかった)
  • 開始状態から幅優先探索しようとして、TLEを繰り返した

github.com

ABC070 D: Transit Tree Path

D - Transit Tree Path

解き方

  • aからKへの距離とKからbへの距離の和を出力する
  • Kから各頂点への最短距離は、木なので、DFSすればO(n)で求まる。

ハマったところ

  • 0-indexと1-index混ぜてた
    • 読み込み時に変えておくべきという話はありそう
  • 最初全頂点から全頂点を求めようとして、O(n^2)になって困ってた。

github.com

ABC070 C: Multiple Clocks

C - Multiple Clocks

解き方

最小公倍数を求めるだけ。場合によってはオーバーフローに気をつけないといけないのかな。

github.com

ABC070 B: Two Switches

B - Two Switches

解き方

区間[A:B][C:D]の重複区間を求める。[max(A, C):min(B, D)]

github.com

ABC070 A: Palindromic Number

A - Palindromic Number

解き方

先頭から確認するだけ

github.com

活動記録(2017/8/7-8/13)

競技プログラミング

ARC 80

結果 204th, レート変更なし

順当に全完できた。 Dでなんか複雑に考えすぎて時間かけてしまった。あと、AtCoderのサイトが変わったことによるテストケース手動取得は時間削減の意味では対処しないといけない。

マイクロマウス

PiCo3のはんだ付けをしようとしたが、はんだ付け技術から道具から足りてないものがあるようなので、ハードウェアはもう一台買うことにした。 それまでにとりあえずマイコンへのプログラム書き込みをLinuxからできるようにしたい。

その他

ChainerMNによる分散学習を試してみて、結果をQiitaに載せた。

qiita.com